turing

home . github

seed

α0

315f5b

β0

db76d0

γ0

78c43b

α1

8ac006

β1

4e4a01

γ1

64612b

α2

1fce77

β2

c86934

γ2

5bfc94

input

c75894edd3

28 May 2021

From the hash we construct a 3-symbol, 3-state Turing machine with the following transition table:

Symbol	State α			State β			State γ
Symbol	Write	Move	State	Write	Move	State	Write	Move	State
0	0	L	α	2	L	γ	1	R	β
1	1	R	β	0	L	α	1	L	β
2	0	R	α	2	L	γ	1	R	β

We begin at state α on a tape seeded with input, and use the lookup table to determine which symbol to write (a white square, gray square, or black square), which direction to move the cursor (left or right), and which state to become. (For artistic purposes, the "halt" state H never appears).

With each transition, we draw the one-dimensional tape on the canvas, and move down a line. The result is a two-dimensional drawing that grows off the sides of the screen, empties out completely, or draws something interesting.

Turing machines are named after Alan Turing, who developed them while researching the Entscheidungsproblem. These machines form the basis of "computation" - following a series of steps on some input to produce some output. In order to construct a universal Turing Machine (one which can compute anything), we need more states and symbols*.

[*] Universal machines with the following amounts of (state, symbol) have been found - (15, 2), (9, 3), (6, 4), (5, 5), (4, 6), (3, 9), and (2, 18)