For 10 points, name these devices which can theoretically simulate any computation, named after a British computer scientist.
Robert Berger solved the domino problem by translating these things into a Wang tiling. Their "alternating" type switches between "existential" and "universal" states. In an article about the "Problem of Thue," Emil Post used "quadruplets" instead of "quintuplets" to specify these things. C-types of these rely on outside entities to make a choice, like O-types of these structures, which rely on an (*) "oracle." A type of these structures that executes the most possible steps is the "busy beaver." They can be formally defined as a 7-tuple whose transition function outputs a symbol, state, and direction of motion. These structures have an instruction table, a state register, a head that can read and write symbols, and an infinite tape divided into cells. For 10 points, name these devices which can theoretically simulate any computation, named after a British computer scientist.
Robert Berger solved the domino problem by translating these things into a Wang tiling.
Turing machine [or alternating Turing machine]