LUTM-6

A Turing machine with two tapes and a fixed control of nine states. The program is a binary Turing machine written out as records on its own tape; the fixed control reads the records and carries them out on the data tape.

Description

LUTM-6 is one fixed two-tape Turing machine. The program tape P holds the program and is never written. The data tape X holds the input and is the working memory and the output. Both tapes use the symbols B (blank), 0, 1 and #, and both are unbounded in both directions.

Each step looks at the control state and at the two symbols under the heads, then writes a symbol on X, moves each head by at most one cell and sets the next state. Nine states times four times four symbols give the 144 rows of the transition table shown under the simulator. That table is the whole machine: programs differ only in what is written on P.

The machine halts only when the control enters the state H. Every string over B 0 1 # is a program. Nothing is checked or rejected; a string either halts, runs forever, or stops at the step limit you set.

Usage

Choose a program and type an input made of 0 and 1.
Step runs one transition, Run runs at the chosen speed, To halt runs at full speed. Back undoes steps (up to the last 200,000). Reset returns to step 0.
Max steps is where a run stops if the machine has not halted.
The program text can be edited; the run restarts from step 0. Characters other than B 0 1 # are ignored, and b or _ are read as B.
Keys: space run/pause, → step, ← back, R reset, H to halt.
The address bar keeps the program and the input, so a link reopens the same run.

How it works

Input and output

The input is written on X from cell 0, two cells per bit, and ends with a marker pair:

input	on X
bit 0	`1B`
bit 1	`11`
end	`B1`

For example 010 becomes 1B 11 1B B1. Both heads start at cell 0, in state D. After the machine halts, the output is read in pairs starting at the data head: 1B is 0, 11 is 1, and any other pair ends the output. Whatever lies left of the head or after that pair is ignored. The output cells are shaded on the data tape.

Inside a run the data tape holds bits as B (for 0) and 1. The symbols 0 and # on X serve as a single temporary mark, used for jumps.

Programs as records

A program describes a binary Turing machine with states q0, q1, …. Each state has two records: what to do on reading 0, then on reading 1. A record ends with #:

w d 1…1 #    write bit w, move left (d = 0) or right (d = 1),
             then continue with the record numbered by the count of 1s
#            halt

Records are numbered from 0, two per state, so a run of 2t ones continues with state qt. The hand-written NOT program starts with 001111# (q0 reading 0: write 0, move left, four ones: go to q2) and 1111# (q0 reading 1: write 1, move right, go to q1).

The nine states

state	what it does
D	Reads X. On `1` (or the mark `#`) goes to S. Otherwise the record under P applies: writes its bit on X and goes to M; halts if the record is `#`.
S	Moves P past the record for 0, then goes to W.
W	Writes the bit of the record for 1 and goes to M; halts if the record is `#`.
M	Reads the direction bit and moves X one cell left or right.
K	Marks the new X cell without losing its bit: `B` becomes `0`, `1` becomes `#`.
C	Moves both heads right while P reads 1s, so X ends 2t cells right of the mark.
R	Moves P left to the blank before the program, then onto record 0.
J	If X holds the mark, restores it (`0` → `B`, `#` → `1`) and goes to D, with P now at record 2t. Otherwise moves X one cell left and goes to U.
U	Moves P past one record and returns to J.

A jump to state t is therefore done by counting on the data tape: C walks X out by 2t cells, then J and U walk it back one cell per skipped record until X meets the mark. One step of the encoded machine costs a number of transitions proportional to the program length.

The record reading is how the table treats programs written as records, but the table applies to any string: a record without a direction bit halts in M, a B inside the program stops R's rewind at that cell, and S, U, D, W and M halt when P runs off the program.

Universality

Writing out the records of any binary Turing machine gives a LUTM-6 program for it, and a block compiler turns any Turing machine on B 0 1 # into such a binary machine. On this basis the project argues that every computable function on bit strings has one LUTM-6 program that works for all input lengths, with this fixed input and output format. The argument is written out in the project's CONSTRUCTION.md; it is not machine-checked.

The programs listed

hand-written: binary Turing machines written by hand and serialized as records.
compiled: Turing machines on B 0 1 # passed through the block compiler.
evolved: found by the project's genetic search, starting from random strings.

Every listed program was checked on the reference implementation: all inputs up to 8 bits and random inputs of 16, 32 and 64 bits. Programs that are correct only on their training inputs are not listed.