Turing Tiles

Move the slider grippy until it shows the number you would like to try as a starting number. The first row will be filled with this number as binary value.

Solve the puzzel by dragging tiles from the left side panel to the board in the middle, making sure that the colors at the top of the tile on the board, and on the bottom of the new tile match. If you continue until there are only red and blue tiles left, with a black tile at the far right. The value of the tiles should represent:
your number + 1.

The set of tile types used in this example tiling problem have been produced by applying a well known reduction of a single tape Turing Machine computations by tilings. The idea is that the sequence of colors along a horizontal edge in the tiling encode a configuration of the machine during the computation. The colours encode tape symbols except for a set of special colours which encode state-tape symbol pairs. Each row should contain exactly a single special colour for as long as the computation runs.

The tile types enforce that the coloring in the next horizontal row below then must encode a successor configuration. By requiring the top row of the rectangle to be tiled to enoce the initial configuration on some input, the completed tiling will encode the intial segment of the full computation. Height of the rectangle corresponds to time and the width to the space consumed by the machine. Hence the size of the rectangle must be sufficiently large in order that the computation will not exceed the boundary of the rectangle.

The set of allowed tile types consists of three families: symbol passing tiles which aim at preserving the part of the configuration where nothing happens; state accepting tiles encoding the situation that a tape symbol in the next configuration will be scanned by the head after a move, and finally instruction tiles which are in 1-1 correspondence with the rules in the Turing Machine program. In order to prevent pairs of phantom heads to appear out of nothing the program must be structured in such a way that each state has an associated move direction (when gong to that stat the machine only can move in that direction).

The Program used for this example is that of a simple two state machine which operates on binary numbers and increments these numbers by one. Since this machine computes a string function rather than accepting a set of strings we use the convention that the machie halts by having the state vanish from the configuration.