LUTM-6 and LU-A

LUTM-6 and LU-A

Two machines that run programs on bit strings, built for searching programs from examples. Each machine writes the input and reads the output in one fixed way, the same for every program. Open either one to run, step through and edit its programs.

LUTM-6

A two-tape Turing machine

Program
a string over B 0 1 # on a read-only tape
Control
9 states and a halt state, 144 transitions
Input 01
1B11B1
pairs: 0 → 1B, 1 → 11, end → B1
Halts
when the control enters H
A program is
a binary Turing machine written out as records
Open LUTM-6

LU-A

A language with ten operations

Program
a string over > < 0 1 x ~ [ ] ( )
Control
an instruction pointer; brackets paired by nesting
Input 01
01
written as it is
Halts
when the pointer passes the last operation
A program is
written directly in the operations
Open LU-A

The same tasks on both machines

Program length, and the number of steps on input 0110 (counted here, in your browser). Each entry opens in the simulator.

Every program listed was checked on the reference implementations: 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 left out.