The Universal Constructor

A heatmap of emergent computational complexity.

The Engine of Creation

The Universal Construction Operator `U` drives everything. At each step `n`, it takes the current universe and produces the next, more complex one.

The core of this process is a pairing function. A pairing function is a method that maps two natural numbers (i, j) to a single unique natural number n. Its inverse decodes n back to (i, j). This guarantees every possible pair is eventually chosen. The example below uses the Cantor "zig-zag" pairing inverse. Other methods like the Szudzik spiral exist. 


function getCantorPair(n) {
  const w = Math.floor((Math.sqrt(8 * n + 1) - 1) / 2);
  const t = (w * w + w) / 2;
  const j = n - t;
  const i = w - j;
  return { i, j };
}
This function takes the current step number `n` and decodes it into a unique pair of indices, `i` and `j`, which are then used to build new objects. 


// The core operation of U at step n
function U(universeState) {
    // 1. Get step number and indices
    const n = universeState.R.length;
    const { i, j } = getCantorPair(n);

    // 2. Construct new objects
    const S_new =  (Sᵢ NOR Sⱼ) 
    const R_new = Sᵢ := Sⱼ 
    const M_new =  Mᵢ rules + Mⱼ rules + R_new 
    
    // 3. Return the new universe
    return { 
        S: [...universeState.S, S_new], 
        R: [...universeState.R, R_new], 
        M: [...universeState.M, M_new]
    };
}

Interpreting the Machine

While all machines are constructed by concatenating their parents' rule lists, they can be executed in two distinct ways. This choice dramatically affects their behavior and the complexity that emerges. You can switch between these modes below.

Parallel (Set-based): In this mode, only the unique rules of a machine are considered. They are all evaluated simultaneously based on the state at the start of a step, much like a hardware logic circuit. This often leads to more complex, oscillating patterns.

Sequential (List-based): Here, every rule in the machine's list is executed in order, one by one. The state is updated immediately after each rule, which can influence the next rule in the sequence. This behaves more like a traditional computer script and tends to settle into simpler patterns more quickly.

The Complexity Heatmap (First 60 Machines)

This is a detailed, interactive view of the first few machines generated by `U`. The lines trace the construction path, while the points are colored by the machine's cycle length. Hover over a point to see its details.

Large-Scale Heatmap (First 5,000 Machines)

This is a non-interactive, high-density view of the first 5,000 machines. Each pixel represents a machine, colored by its cycle length. This provides a broader perspective on the patterns of complexity that emerge as `U` explores the space of all possible programs.

The Challenge

The search for complexity is non-trivial. The most interesting machines are rare. We challenge you to find them. Download the `U.js` library and write your own program to search the computational universe for the machine with the highest cycle length.

Download U.js

Cycle Hunt Log