Universal Turing machine · Unary add one
Example 04Shaded = program · # = start of data · ① / ◇ = saved simulated head · ▼ = physical head
Instruction Table
| State | Read | Write | Move | Next 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.