Universal Turing machine · Unary add one

Example 04
0 simulated steps

Shaded = program · # = start of data · ① / ◇ = saved simulated head · ▼ = physical head

Instruction Table

StateReadWriteMoveNext state
Tape encoding

The program and data share one tape. Each five-symbol instruction is state, read, write, move, next state, followed by a semicolon. Thus a11Ra means “in a, read 1, write 1, move right, stay in a”; aB1SH means “in a, read blank, write 1, stay, halt.” ^ starts the program; # starts the data; B encodes blank. The shaded cells contain the program.

The triangle is the universal machine’s physical head. The symbols ①, ⓪ and ◇ mark the simulated head on a 1, 0 or blank. This mark stays on the tape while the physical head searches the program. q, r, w and d are finite control values: simulated state, read symbol, write symbol and direction. The table and diagram group control states by their operation; each click is one actual read/write/move transition.

This interpreter uses states a–z plus H, symbols 0, 1 and blank, and moves L, R or S. The simulated tape extends to the right of #; a left move at its boundary stays in its first cell. The universal machine’s own tape extends in both directions. The starting program is unary add 1; zero is an empty input.

State Machine

0 steps
Single-tape interpreter: read the marked data, search the program, fetch an instruction, return and execute it
Grouped finite-control states · one tape cell per step · keep = write the symbol read