turing

home . github

seed

α0

d527b1

β0

d8892d

γ0

da1a9f

α1

674f57

β1

27c9ae

γ1

6ecf27

α2

a81b4c

β2

2905fc

γ2

2c2e6b

input

961e3fa0cd

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	2	L	γ	2	R	γ	2	L	γ
1	1	L	β	0	R	α	1	R	β
2	1	L	β	0	L	α	0	L	α

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)