Emergent Computing

Direction · hypotheses

Local rules on parallel hardware

A local rule needs only a cell and its neighbours, so it maps onto parallel hardware with no instruction stream. Three directions: faster search on GPUs, cellular hardware for arithmetic, and analog media. None is tested yet.

· Emergent Computing

Search on GPUs

Population-based search evaluates many candidate programs on the same inputs: a batch of independent simulations, which is the workload GPUs are built for. LUTM-1 and LUTM-6 already run candidates in parallel on CUDA. Bit-packed cellular automata, two bits per EM43 cell, would put 32 cells in a 64-bit word and update them with a few logical operations. Faster evaluation does not fix a rugged landscape, but it changes which search methods are affordable.

Cellular hardware for arithmetic

The direction: hardware in which an operation such as multiplication is carried out by a grid of identical cells, each applying one local rule, with constant work per cell per step. Locality sets a limit on latency. A cell's state after t steps depends only on inputs within distance r·t, where r is the rule radius. Bit n − 1 of an n-bit product a·b, and every bit above it, depends on every bit of both inputs, so it cannot be correct until its backward light cone covers all of them:

Locality bound. Two 12-bit inputs on a one-dimensional array of radius-1 cells. Bit 11 of the product, read at the last cell of a, depends on all 24 input cells; its backward light cone (shaded) covers them only from step 12 on. No local rule can produce it earlier.
  • One dimension: linear time, and it is achievable. Atrubin's real-time multiplier (1965) is a one-dimensional array of identical finite-state cells that outputs one product bit per step as the operands stream in. The Neural GPU learned binary multiplication with a local convolutional update applied for a number of steps equal to the input length, so in linear time with local operations, and generalised from 20-bit training numbers to much longer ones (Kaiser and Sutskever, 2016).
  • k dimensions: latency at least of order n1/k, because n input bits occupy a region of diameter about n1/k. For chip layouts, Brent and Kung proved that the area A and time T of any n-bit multiplier satisfy AT² = Ω(n²) (1981).
  • Constant latency needs non-local summation. Multiplication is in TC⁰: constant-depth circuits of threshold gates with unbounded fan-in compute it. Physically, that means summing many signals at once, as currents or light, which trades time for precision and fan-in.

So the realistic target is not O(1) latency but constant work per cell, high throughput and latency close to the light-cone bound. The open question for us is whether search can find such rules, rather than designing them, and whether the rules found are robust.

Analog media

CEM1D and CEM2D are continuous substrates. With real-valued cells, the same framework describes analog computation, but the paper gives no guarantee there: latent universality is proved for discrete models. The deciding property for a physical implementation is tolerance to noise and to unsynchronised updates. Training neural cellular automata with random asynchronous updates, as in NCPU-EM, is a first way to measure it.

References

  1. S. J. Atrubin. A one-dimensional real-time iterative multiplier. IEEE Transactions on Electronic Computers EC-14(3):394–399, 1965.
  2. Ł. Kaiser, I. Sutskever. Neural GPUs Learn Algorithms. ICLR 2016. arxiv.org/abs/1511.08228
  3. R. P. Brent, H. T. Kung. The area-time complexity of binary multiplication. Journal of the ACM 28(3):521–534, 1981.
  4. G. Bocchese et al. Emergent Models: Intelligence from Tiny Substrates. 2026. arxiv.org/abs/2608.14019