A machine is considered
Turing complete if it can
emulate any
Turing machine within reasonable limits on number of states and tape length. Likewise, a
Tetris-
complete machine can emulate any
puzzle game within limits on board size and depth. The following are
necessary (but not necessarily
sufficient; perhaps a mathematician could help me strengthen my argument) for a Tetris-complete machine:
- a display with at least 20 rows and 10 columns (for conforming Tetris implementations; other puzzle games need different-sized displays), and enough read/write random access memory to store the current contents of the display,
- a way of repainting one row or column of the display without affecting the others,
- a timer with a resolution of at least 100 milliseconds, as Tetris just isn't Tetris without gently accelerating gameplay,
- a small set of keys whose state can be read without blocking execution, which for Tetris are left, right, clockwise, and anticlockwise (soft and hard drop are also nice), and
- a linear bounded automaton programmed for the particular puzzle game. Here's some Tetris pseudocode to get you started.
Examples of Tetris-complete machines include
TI-82 and more powerful
graphing calculators, any
microcomputer from
Apple II on up, and most
video game consoles. Here are some more
esoteric examples:
- According to m_turner: "some versions of the HP Logic analyzer actualy had a 'tetris mode'... or was it osilliscope?"
- Atari 2600 is Tetris-complete. With only 128 bytes of RAM and only one-half scanline's worth of video RAM, I wondered how a Tetris clone on the VCS would store the playfield. Turns out Ed Federmeyer and Colin Hughes independently discovered that each row of the playfield could be squeezed into two bytes (N.B.: This works only for Tetris). To grab the ROMs, search Google for tetris 2600 or edtris 2600.
Machines that are
not Tetris-complete include:
- SPIM, a MIPS CPU simulator (its console does not support upward cursor movement ergo no repainting)
- Nintendo Game Boy Tetris-complete in theory but not in practice. It plays a reduced version of Tetris that uses a 10x18 board (no big loss to the player) because its display is 20x18 character cells, each 8x8 pixels. (Game Boy Advance's is 30x20 and can display Tetris correctly.) Of course, you could make tiles 4x4 by stuffing four grid spaces into one tile, but you'd have to squint to see anything. (RST notes that Tetris DX apparently keeps track of two lines above the displayed playfield.)
asterphage pointed out that the Atari 2600 console cannot handle Tetris 2 or Tetris Attack without the additional RAM of a Supercharger. Note that just as no machine can be strictly Turing-complete because a Turing machine has an unbounded amount of storage, some machines can be effectively tris-complete with respect to one game but not so with respect to another. For example, Tetris Attack seems to require at least 16 bits per element on its 6x12 board, which would overflow the 2600's 128 bytes of RAM.
RST pointed out that some Tetris clones have differently sized playfields. For example, gnometris's playfield is 9 blocks wide, Tetripz's is 11, and Tetrinet's is 12. I don't count those as conforming Tetris clones because they don't follow the official Tetris standard (which used to be at http://www.tetris.com/under.html until Tetris.com died) and because their changes to the deep geometry of the game require heavy modifications to some basic tactics of advanced players.