Experiments 20
Guessing machinesEvery 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…
Every program
Only the ones that fit
Point at a tile to read its program.
never answeredruled out, or longer than 26 bits
- other
Writing down every program up to 26 bits…
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 position | 3 |
| a(n−1), the term before | 3 |
| a(n−2), two terms before | 4 |
| a number k | 3 + its Elias gamma code |
| + and × | 3 |
| − | 4 |
| ÷ and mod | 5 |
| j, the loop’s counter | 3 |
| first j ≥ x with y = 0 | 4 |
| each starting number | 1 + 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
- Ray J. Solomonoff, “A Formal Theory of Inductive Inference,” Information and Control 7 (1964): 1–22 and 224–254.
- Marcus Hutter, Universal Artificial Intelligence (Springer, 2005).
- Shane Legg and Marcus Hutter, “Universal Intelligence: A Definition of Machine Intelligence,” Minds and Machines 17 (2007): 391–444.
- Peter Elias, “Universal Codeword Sets and Representations of the Integers,” IEEE Transactions on Information Theory 21 (1975): 194–203.