LU-A
A small language on one data tape, in the style of Brainfuck: ten operations, the input written on the tape as it is, and the output read where the data head stops.
Description
An LU-A program is a string over ten operations. It runs on a data tape whose cells hold
B (blank), 0 or 1; the tape is unbounded in both directions.
The input bits are written on cells 0, 1, 2, …, and both the instruction pointer and the data head
start at 0.
Each step executes the operation under the instruction pointer. The machine halts when the pointer moves past the last operation. Every string over the ten operations is a program, the empty one included (it returns its input). Nothing is checked or rejected.
LU-A is a language rather than a Turing machine: the program is a sequence of operations run by an instruction pointer, not a transition table. In the project it was developed as LUTM-A.
Usage
- Choose a program and type an input made of
0and1. - Step runs one operation, 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 program has not halted.
- The program text can be edited; the run restarts from step 0. Other characters are ignored.
- 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
Operations
| op | effect |
|---|---|
> < | move the data head right / left |
0 1 x | write 0 / 1 / blank |
~ | toggle 0 and 1; a blank stays blank |
[ ] | brackets that test "the cell holds a bit" |
( ) | brackets that test "the cell holds 1" |
After any operation the pointer moves to the next one, except for these jumps:
- An opener
[or(whose test fails jumps to just after its partner. - A closer
]or)whose test holds jumps to just after its partner.
Partners are found before the run by ordinary nesting, with all four brackets counted alike, so
mixed pairs such as ( … ] are allowed: enter if the cell holds 1, repeat while it holds a
bit. [ … ] is a loop over bit cells, ( … ) a loop over cells holding 1.
The simulator outlines the partner of the bracket under the pointer.
Brackets without a partner also have a meaning. An unmatched opener whose test fails jumps to the end, which halts. An unmatched closer whose test holds jumps to the start of the program.
Output
After halting, the output is the run of bits containing the data head. If the head is on a blank, it is the run that ends just left of it, and it is empty if that cell is blank too. The output cells are shaded on the data tape.
Two short examples
[~>] is NOT: while the cell holds a bit, toggle it and step right. The head stops
on the blank after the input, and the output is the run to its left.
~>] also computes NOT, with an unmatched closer: toggle, step right, and start
again while the head is on a bit. On the blank after the input the closer's test fails and the
pointer runs off the end.
Universality
The project includes a compiler from any Turing machine on literal input to an LU-A program
(the compiled increment listed here is one) and argues on that basis that every computable function
on bit strings has one LU-A program that works for all input lengths. The argument is in the
project's THEORY.md; it is not machine-checked.
The programs listed
- hand-written: written directly in the ten operations.
- compiled: a Turing machine passed through the project's compiler.
- evolved: found by the project's genetic search, then shortened by deleting operations while staying correct.
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.