Contents > Abstract Machines > Turing Machine

Discussion

Since Tm along with data on the tape can emulate any Turing machine, Tetris—with an infinite playfield, controlled by an agent entering input derived from the pseudocode—is a system capable of universal computation. However, because the system depends on a finitely defined yet infinite sequence, it is more accurately described as “weakly universal”. Nonetheless, its universality implies undecidable problems. For instance, the problem of determining if the information encoded on the pile's surface evolves into a particular state is undecidable since it is equivalent to asking if a given program halts.