Primes, sieved by 23,844 parameters

Cell n of the tape holds 1 while n may be prime and 0 once it is crossed out (cells 0 and 1 start at 0). For k = 2, 3, 4, …: if cell k is still 1, k is prime; the machine marks it, walks right to the end of the tape crossing out every k-th cell, walks back to the mark, restores it, and moves on to k + 1.

The countdown to the next multiple is held in the machine's states, one chain of k states for each prime stride k. That is what makes the program big: sieving up to N takes the strides of the primes up to √N, and for 1,680 that is 2 to 37, 250 states and 680 rules. Each spiral here is s × s, showing 1 to s² − 1 (s² itself is not prime, but crossing it out would take a stride for s). Only primes get a stride: when k is composite its cell is already 0, and the machine moves on.

While the machine sweeps prime k, every number below k² that is still lit is proven prime, since a composite number below k² has a prime factor below k. On the Ulam spiral the numbers below k² are the central k × k square, so the proven region grows outward from the middle.

The universal machine version 2 finds a state by its binary address, which is what makes a program of hundreds of states affordable at all (on version 1, each step of this program would cost thousands of times more). Even so, the full lagging-window decoder would make trillions of forward passes, days of computing in a browser. This page computes the same transcript without making every pass: from one ring of the transcript to the next only the cells near the universal machine's head change, and a pass whose window is the same three tokens at the same place as one ring earlier gives the same output (the network is deterministic). So the network reads only the windows that changed, and the rest are copied. The forward passes counted are the full decoder's; web/tests/delta-check.js checks, ring for ring, that the transcript is the same. The program is also run directly, but only to check the network's steps, never to draw them.