Home

turing

A visualization of a 3-symbol, 3-state Turing machine.

seed

α0

315f5b

β0

db76d0

γ0

78c43b

α1

8ac006

β1

4e4a01

γ1

64612b

α2

1fce77

β2

c86934

γ2

5bfc94

input

c75894edd3

source

Description

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)

🔗 Details

The input turing complete hashes to the following:

66a77509eaf0d8589812c53dacb80ebb5f98f16dc06b6ae65f3bd67a5a00937e

We divvy this hash up into several parameters:

α0      66a775
β0      09eaf0
γ0      d85898
α1      12c53d
β1      acb80e
γ1      bb5f98
α2      f16dc0
β2      6b6ae6
γ2      5f3bd6
input   7a5a00937e

Our machine has a head which can read and write values 0, 1, and 2 from an infinite tape (represented by a white square, a gray square, and a black square respectively). The head itself can be in one of three states α, β, and γ. It starts at state α.

The field α0 means “for state α and a value 0 on the tape.” The segment of the hash for field α0 (66a775) is then split into 3 bytes (66, a7, and 75) to generate a triple with the following:

Write (which state should we write to the tape? 0, 1, or 2)
Move (should we move the head left or right?)
State (which state should we set the head to? α, β, or γ)

Repeat this for each of the fields to finish building the transition table.

To keep things interesting, we seed the tape with some initial squares based on input. (We convert input to base 3 and read off the digits to set the tape).

Then we start writing

. After each step, we draw the tape and the position of the cursor with a little ▼.

The results are not super interesting - 3 states and 3 symbols just isn’t that much to work with - but each piece looks pretty unique and that’s plenty interesting to me.