Pinned · in progress

Latent-universal machines

The latent-universality theorem says that models with a fixed rule and a fixed interface can compute any computable function by changing only the program. LUTM-1, LUTM-6 and LU-A are small, concrete machines of this kind, built to measure how hard their programs are to find.

The idea

A substrate is latently universal if every computable function already exists somewhere in its space of programs, under one fixed interface. Four properties separate this from ordinary Turing completeness:

The interface is program-blind. Rule, encoder, halting condition and decoder never change. The input is written literally next to the program and the output is read literally; the interface never looks at the program, so it cannot do part of the work.
Every string is a program. Nothing is parsed or rejected. The whole space of strings is valid, and that space is the search space.
Exactness. For each computable function there is a finite program that is correct on all inputs, of every length, and halts exactly where the function is defined.
Existence, not accessibility. The theorem says nothing about the size of the program or how hard it is to find. The capability sits in the rule and stays dormant until a search finds it; hence “latent”.

Ordinary universality says that you can write any program. Latent universality says that the solutions are already in the space, so a blind search over strings is searching a space where they exist. The machines below make this concrete enough to run searches and count costs.

The machines

Machine	Structure	Interface	Notes
LUTM-1	one tape, 150 states, 16 symbols: 2,384 transition rows, the same for every task	tape `p#x`; output: the bits right of `#` at halting	Universal by construction, but slow and rigid: x + 1 needs a 176-bit program, x² 4,605 bits.
LUTM-6	two tapes, 4 symbols, 9 states: 144 rows	read-only program tape of `#`-terminated records; input bits written as pairs, 0 → `1B`, 1 → `11`, end `B1`	Built for search: small table, every program tape is valid.
LU-A	ten operations and an instruction pointer; no transition table	input written as it is; output: the bit run at the head	Direct operations: move, write, erase, flip, and two kinds of loop.

Program lengths

The same tasks on the three machines. Units are the machine's own: bits for LUTM-1, symbols for LUTM-6, operations for LU-A. Programs marked ● were found by evolutionary search.

Task	LUTM-1	LUTM-6	LU-A
NOT	80	82	3
parity	–	32 ●	12 ●
x + 1	176	1,676	13 ●
2x	114	1,310	8 ●
reverse	–	1,216	51
x²	4,605	1,449,178	368,813

Direct operations make programs short, fast and evolvable: on LU-A, search found x + 1, 2x and parity. Squaring shows the other side: when the machine's primitives do not match the task, program length grows by orders of magnitude.

Traces

LU-A, x + 1. The evolved 13-operation program (>]x>]<<(0<)1 on x = 1011. One row per executed operation; dark 1, light 0; red: the data head. Input: x is written directly in binary on the data tape from cell 0, with both heads at 0. Halt: the instruction pointer moves past the last operation. Output: the run of bits under the data head, or ending just left of it if the head is on a blank; here 1100.

LUTM-6, parity. The evolved 32-symbol program 0111011#11011#000#01#0000#1#1100 on input 1101001, over 1,429 transitions. Top: head position on the read-only program tape. Bottom: data tape (rows are cells), data head in red. Input: each bit is written as a pair of cells on the data tape from cell 0, 0 as 1B and 1 as 11, followed by the end marker B1 (B is blank). Output: after the machine halts, pairs are read from the final data-head position with the same code, until the first pair that is neither 11 nor 1B.

What search finds

Working observations from evolutionary runs on these machines; not yet measured systematically.

Programs are found, not written. They are compact and odd, and reuse structure in ways a person would not: unmatched brackets used as restart loops, a blank cell used as a marker, toggles reused as counters, a lookup table encoded in the tail of the program.
Exactness on the training set is not enough. It can come from memorisation or from a length-general algorithm. Only the second counts, so programs are validated on inputs longer than any seen in training.
Solutions come out layered: a length-general part plus a bounded lookup part that saturates at the largest case in the sample. The data decide which part grows.
Search optimises what is measured. It exploits any regularity in the data. The practical response is to shape the pressure rather than the program: a curriculum on input length, stratified sampling, exactness required on all inputs up to a validation length, and an archive of every exact program.

Status and code

For LUTM-1 and LUTM-6, a constructive argument for fixed-interface universality is written out but not formally verified. Tests give finite evidence, not proof. Every program in the LUTM-6 and LU-A simulators is checked exact on all inputs up to 8 bits and on random 16-, 32- and 64-bit inputs. The open question is search: how program length, run time and the shape of the fitness landscape interact.

LUTM-1: simulators in Python, NumPy and CUDA, an island genetic algorithm and a program miner.
LUTM-6: machine, resumable genetic algorithm.
LUTM-6 and LU-A simulators (code): step-through browser simulators with the programs above.

Background: latent universality in the Emergent Models paper.