Experiments 20

Guessing machinespart 2 of 5

Every Program at Once

Under Solomonoff induction, every program consistent with observed data votes on what comes next, with shorter programs weighted exponentially higher. Enter a sequence and watch ~840,000 programs up to 26 bits vote in WebAssembly.

Rust · WASM · Solomonoff induction · CanvasView source 

Writing down every program up to 26 bits…

Try
YouIt guessed

Every program

Only the ones that fit

Point at a tile to read its program.

never answeredruled out, or longer than 26 bits

  1. other

Writing down every program up to 26 bits…

Notes on how it works

Notes

Solomonoff induction and the unit square

Under Ray Solomonoff’s 1964 model of inductive inference, every program consistent with an observed sequence votes on the next term with weight 2−b, where b is the program’s length in bits. Because the expression grammar is a prefix-free code, each program of b bits occupies an exact share 1/2b of the unit square. Filtering to matching programs renormalizes the surviving tiles over the posterior distribution.

Expression language

A program specifies initial terms followed by a recurrence rule built from prefix-coded primitives:

n, the position3
a(n−1), the term before3
a(n−2), two terms before4
a number k3 + its Elias gamma code
+ and ×3
−4
÷ and mod5
j, the loop’s counter3
first j ≥ x with y = 04
each starting number1 + its gamma code

For example, a(n) = a(n−1) + a(n−2) starting at 1 costs 15 bits (5 for the initial prefix, 10 for the rule). Adding the unbounded search primitive first j ≥ x with y = 0 makes the language Turing-complete, connects it to Marcus Hutter’s AIXI, and introduces non-halting programs (see Educated Guessing Machines for the neural counterpart in this series).

Implementation and bounds

A Rust/WebAssembly module enumerates all ~840,000 recurrence rules up to 26 bits once at startup, sorted by length. Initial terms are not enumerated; their Elias gamma bit cost is read directly from your input, and literal prefix programs are summed analytically. Because of the halting problem, evaluation caps each program at 400 steps and marks non-terminating programs in gray.

Sources

  1. Ray J. Solomonoff, “A Formal Theory of Inductive Inference,” Information and Control 7 (1964): 1–22 and 224–254.
  2. Marcus Hutter, Universal Artificial Intelligence (Springer, 2005).
  3. Shane Legg and Marcus Hutter, “Universal Intelligence: A Definition of Machine Intelligence,” Minds and Machines 17 (2007): 391–444.
  4. Peter Elias, “Universal Codeword Sets and Representations of the Integers,” IEEE Transactions on Information Theory 21 (1975): 194–203.