Universal Construction and Exact Self-Reproduction in Ternary McCulloch-Pitts Networks

Charles C. Norton

cs.LOOct 8, 2026

Universal Construction and Exact Self-Reproduction in Ternary McCulloch-Pitts Networks

Authors: Charles C. Norton

Abstract

A fixed network of McCulloch-Pitts threshold units with weights in {-1,0,1} can hold other threshold networks in its state and run them: the state is a ring of banks of records, each record a unit of a stored network, and each step evaluates one record. We use such a network to carry out von Neumann's universal construction and self-reproduction exactly. As a cellular automaton keeps its rule, the fixed network keeps its weights, and what reproduces is a stored network. A constructor of 143 records reads the description of a network from its tape, builds that network in the next bank, copies the description onto the next tape and hands control to what it built; started on its own description, it rebuilds itself, weights included, in every generation. The scheme scales to a universal computer. A SUBLEQ computer of 17,598 ternary units, stored as 36,080 records and running a program of 27 instructions, builds any network that fits a bank and reproduces itself in the same way, at every word width from eight bits on; run directly, it emits the serialization of its own weights, memory and tape. Integer pre-activations give every orbit a margin of 1/2, and replicating each unit r times multiplies it by r. That suffices against noise of any size on the pre-activations, but against von Neumann's output flips only below a threshold inversely proportional to the fan-in. These results are proved in Rocq.

Figures & tables

Panel of Figure 1 — Figure 1: The ring machine $\mathcal{M}^{\alpha}_{K,S,L}$ at bank index $\kappa$ . A step evaluates the record under the slot head of the active bank on the cells $a_{0}$ and $a_{1}$ , writes the result into cell $a_{o}$ and moves the slot head to the next slot. Window cells $1$ , $2$ and $3$ are the cells under the read head, the arm and the copy head, shaded; the requests in cells $4$ to $12$ move these heads on or return them to cell $0$ , clear the idle bank and the copy tape, and hand over to bank $\kappa+1$ . The other $K-2$ banks and tapes are left as they are.

Panel of Figure 2 — Figure 2: The decoder of the organism, one step per pass, $z$ counting down the bits of a phase: a codon in codon , the eight bits a gate’s codon determines or an escaped record’s first eight in gate , the address bits in addr . Construct mode writes each record under the arm, and copy mode copies every bit read under the copy head.

Address	Symbol	Role	Effect
0xF9	$c_{\mathrm{wr}}$	write request	value $1$ emits $R_{\mathrm{out}}$ and clears it
0xFA	$c_{\mathrm{eot}}$	end-of-tape status	set by a read at $h=\|\tau\|$ , cleared by a read at $h<\|\tau\|$
0xFB	$c_{\mathrm{rw}}$	rewind request	value $1$ sets $h=0$
0xFC	$c_{\mathrm{rd}}$	read request	value $1$ loads $R_{\mathrm{in}}$ and advances $h$
0xFD	$R_{\mathrm{in}}$	input register	written by the device
0xFE	$R_{\mathrm{out}}$	output register	written by the program, cleared on emit

Table 1: The memory-mapped device cells of the host,

A=8

Block	Units	Layer	Computes
$P_{j}$	$2^{A}$	1	decode lines of $p$
$HP_{i}$	$A$	1	$h\wedge p_{i}$
$FA_{o,t,j}$	$3A2^{A}$	2	$\mu_{j+o,t}\wedge P_{j}$
$Q_{i}$	$A$	2	bit $i$ of $p+3$
$F_{o,t}$	$3A$	3	the operands $a$ , $b$ , $c$
$PA_{j}$ , $PB_{j}$	$2\cdot 2^{A}$	4	decode lines of $a$ and $b$

Table 2: The blocks of

H_{A}

in the order of the netlist. The layer is the depth of the block’s units.

$k$	addr	$a$	$b$	$c$	effect
0	0x00	T2	T2	0x03	$\mathrm{mem}[\texttt{T2}]\leftarrow 0$
1	0x03	T1	T1	0x06	$\mathrm{mem}[\texttt{T1}]\leftarrow 0$
2	0x06	NEG1	$c_{\mathrm{rd}}$	0x09	read request
3	0x09	$R_{\mathrm{in}}$	T1	0x0C	$\mathrm{mem}[\texttt{T1}]\leftarrow\nu(\chi)$
4	0x0C	T1	T2	0x0F	$\mathrm{mem}[\texttt{T2}]\leftarrow\chi$
5	0x0F	Z	T2	0x15	branch if $\chi=0$ or $\chi\geq 128$

Table 3: The constructor

P

of Construction 6.8 , instructions

0

20

at 0x00 – 0x3E , and the self-reproducing program

P^{\ast}

of Construction 6.11 , instructions

0

19

P

followed by

20

26

at 0x3C – 0x50 . An instruction

a\;b\;c

assigns

\mathrm{mem}[b]\leftarrow\mathrm{mem}[b]-\mathrm{mem}[a]

and branches to

c

when the result is at most

0

;

x

is the tape byte just read.

Panel of Figure 3 — Figure 3: A generation of the stored host. Each pass evaluates the records of $\mathcal{S}$ and carries out one step of the host on the window. The first pass clears the next bank and the next tape and returns every head to cell $0$ . $P^{\ast}$ then reads $\tau_{\mathcal{S}}$ twice: in phase (A) it decodes it, and the device writes the decoded bytes, the image of $\mathcal{S}$ , under the arm; in phase (B) it copies $\tau_{\mathcal{S}}$ under the copy head. At the halt the hand-over passes control to the next bank, whose first pass loads $m^{\ast}$ and runs the copy.

Panel of Figure 4 — Figure 4: The per-step probability of leaving the orbit under Gaussian read noise of deviation $s$ , against the bounds of Section 8 ; the lines join the values computed at the deviations of Tables 4 and 5 , and the error bars are exact $95\%$ intervals for a Poisson count. (a) $\Lev(N_{\mathrm{host}})$ : the rate at which noisy copies first leave the exact orbit, the product form $b^{\prime}$ and the sum $b$ of the profile bound of Proposition 8.5 , and the bound $Mp$ of Proposition 8.4 . (b) $N_{3}$ : the rate at which the state read by majority first leaves the orbit, the restoration bound of Proposition 8.14 and the first-order bound of Theorem 8.8 (ii), with the rate at which some copy of some state bit first deviates.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

$s$	Deviated	Exposure	Measured rate, $95\%$ interval	$b^{\prime}$	$b$	$Mp$
$0.06$	0/256	768,000	$0$ , $[0,\,4.80\times 10^{-6}]$	$1.21\times 10^{-12}$	$1.21\times 10^{-12}$	$3.30\times 10^{-12}$
$0.08$	7/256	1,008,916	$6.94\times 10^{-6}$ , $[2.79,\,14.3]\times 10^{-6}$	$6.34\times 10^{-6}$	$6.34\times 10^{-6}$	$1.72\times 10^{-5}$
$0.09$	202/256	496,131	$4.07\times 10^{-4}$ , $[3.53,\,4.67]\times 10^{-4}$	$4.27\times 10^{-4}$	$4.27\times 10^{-4}$	$1.16\times 10^{-3}$
$0.10$	256/256	29,384	$8.71\times 10^{-3}$ , $[7.68,\,9.85]\times 10^{-3}$	$8.81\times 10^{-3}$	$8.85\times 10^{-3}$	$2.41\times 10^{-2}$
$0.11$	256/256	3,325	$7.70\times 10^{-2}$ , $[6.79,\,8.70]\times 10^{-2}$	$8.07\times 10^{-2}$	$8.42\times 10^{-2}$	$2.30\times 10^{-1}$
$0.12$	256/256	714	$3.59\times 10^{-1}$ , $[3.16,\,4.05]\times 10^{-1}$	$3.77\times 10^{-1}$	$4.73\times 10^{-1}$	$1.30$

Appendix

Table 4: The per-step probability that

\Lev(N_{\mathrm{host}})

leaves the exact orbit under read noise of standard deviation

s

. One noise-free copy and

256

noisy copies were stepped together from the initial state of the self-describing instance,

3000

steps for

s\leq 0.06

and

4000

otherwise, the full state compared after every step; the exposure is the number of step–copy pairs before a first deviation, and the interval is the exact

95\%

interval for a Poisson count over it.

b^{\prime}

and

b

are the product form and the sum of Proposition 8.5 averaged over the same exposure; at

s=0.08

and

s=0.09

b^{\prime}

bounds the expected number of deviating copies by

6.4

and

212.0

, against

7

and

202

observed.

$s$	Failed	Exposure	Measured rate, $95\%$ interval	Restoration bound	$rM\erfc(r/2\sqrt{2}s)$
$0.10$	—	—	—	$8.62\times 10^{-59}$	$9.24\times 10^{-46}$
$0.15$	—	—	—	$4.02\times 10^{-25}$	$1.92\times 10^{-18}$
$0.20$	—	—	—	$3.59\times 10^{-13}$	$8.03\times 10^{-9}$
$0.22$	—	—	—	$1.82\times 10^{-10}$	$1.16\times 10^{-6}$
$0.25$	—	—	—	$1.58\times 10^{-7}$	$2.48\times 10^{-4}$
$0.27$	5/64	1,237,505	$4.04\times 10^{-6}$ , $[1.31,\,9.43]\times 10^{-6}$	$4.57\times 10^{-6}$	$3.48\times 10^{-3}$

Appendix

Table 5: The per-step probability that the state of

N_{3}

read by majority leaves the orbit under read noise of standard deviation

s

64

noisy copies stepped beside an exact one from the initial state of the self-describing instance for up to

20{,}000

steps, each stopped at its first wrong majority-read state, with the exact

95\%

interval for a Poisson count over the exposure, against the bound

b(t)

of Proposition 8.14 along the same orbit, weighted by the steps each copy ran where copies ran and averaged over the

20{,}000

steps elsewhere, and the first-order bound of Theorem 8.8 (ii).

Result	Rocq theorems
Lemma 2.5	Lev.lev_ok
Theorem 3.2	PhysSem.netlist_step , PhysFacts.phys_ternary , PhysLev.phys_dmax
Lemmas 3.3 and 3.4	Schedule.netlist_pass , Compile.compile_unit , Compile.compile_records
Lemma 4.2 , Proposition 4.4	Complete.describe_complete , PassLemma.machine_pass
Theorem 4.5	Run.universal_construction , Main.builds_every_image
Theorem 4.6	Main.copies , Main.periodic , NetMain.network_reproduces , NetMain.network_periodic

Appendix

Table 6: The Rocq theorems behind each result.

$\ser(\Omega^{\ast})$	c5950d3fec6bcf70e8111586a030d21b2dfa55bd69a1c7fe5f016cb06e7fb523
organism $\rho$	d4913db0b5ef6d3f122c44974cf9a58015fe7dabacb7176cf377d5cd0743f00b
stored host $\mathcal{S}$	9a7821a540fed2ed58fbb263213f65aead6bbbd8cca6344abcabcc5f4289903c

Appendix

Table 7: The SHA-256 digests of the artifact’s files.

Explore similar work

May 7, 2026cs.AI

Von Neumann Networks

In the mid-twentieth century, mathematician and polymath John von Neumann created a computational system on an array of cells as a simple model of the human brain, where each cell had one of a finite set of roles or states that he predicted would be modelled by a diffusion process. In this work, we show that such a system, when developed in a modern deep learning setting, enables the construction of an artificial neuron having specialized roles that can be learnt. We refer to this neuron as the Von Neumann neuron, and the resulting neural network from such neurons result in a self-engineered design whose architecture is only dependent on the structure and locations of its inputs and outputs on this cellular array. The mathematical framework for these Von Neumann Networks (VNNs) is also constructed and shows that they are based on the extension of neural operators and the learning of Green's functions with convolutions on a cellular topology having a diffusion signature. We also prove that these VNNs are part of a more general computational system called Cellular Machines that are computationally universal. Initial experiments show that VNN based multi-layered perceptrons outperform their equivalent deep learning variant on basic tasks, while being more parameter efficient and are capable of learning new types of tasks. This includes the ability to solve for and construct an extension of the Von Neumann (hardware) architecture common to all modern computers to cells and suggests new opportunities that could be explored.

Shekhar S. Chandra

School of Electrical Engineering and Computer Science, The University of Queensland, Australia.

Neural Cellular Automata Cellular Automata

Ask PDF

May 3, 2026cs.LG

A PyTorch Library of Turing-Complete Neural Networks

We present a PyTorch package that compiles neural networks and their weights from Turing machine descriptions, producing models that exactly simulate the specified machine without any training. Given a transition function and a set of terminal states, the package constructs a model whose forward pass corresponds to one step of the Turing machine. Two architectures are implemented, each realizing a different theoretical result: (1) a transformer with self-attention, cross-attention, and feedforward layers based on Wei, Chen, and Ma (2021), and (2) a recurrent network based on Siegelmann and Sontag (1995) that encodes the stack in a Cantor set. We develop the constructions from first principles, showing how ReLU networks implement Boolean circuits (AND, OR, NOT, XOR gates and their composition into DNF formulas and binary adders) and how hard attention implements positional lookup on the tape. The package serves as a concrete, runnable reference for the symbolic-neural bridge, and as a foundation for future work on the stability of constructed solutions under gradient-based optimization. Code is available at https://github.com/jonrbates/turing.

Jonathan Bates

Neural Network Expressivity

Ask PDF

Sep 17, 2026q-bio.PE

Self-Replicating Neural Cellular Automata: Quantifying Emergent Phenotypic and Genotypic Diversity in an OpenEnded Substrate

We study an in-silico substrate in which every pixel of a two-channel cellular-automata grid carries a tiny neural network (an agent) that senses its Moore neighborhood. A cell persists only by self-replication: a living neighbor is cloned and its weights are mutated by a uniform perturbation, so that phenotype (cell state) is driven entirely by genotype (network weights). From a handful of seeded founders the system grows into a spatially organized ecosystem of coexisting, competing and dominating species. Our main contribution is a battery of coarse-grained diversity metrics that make such growth measurable at two scales: four phenotypic tools based on cellular-type frequency, entropy and cell variance, and two genotypic tools that colour each agent by a hash of its full weight vector versus a sparse random-weight probe. Across a five-fold sweep of 1680 small runs and 24 long (1000-generation, 200 x 200) runs, the substrate is persistent and self-maintaining in 20 of the 24 long configurations and exposes a clear phenotype-genotype diversity trade-off: raising phenotypic diversity collapses genotypic diversity and vice versa. Full-genome hash colouring further reveals lineage structure that a random-weight probe systematically misses. Code, data and animations are released as supplementary material.

Sanyam Jain, Felix Simon Reimers, Stefano Nichele

Department of Computer Science and Communication, Østfold University of Applied Sciences, B R A veien 4, 1757 Halden, Norway · Department of Computer Science, Oslo Metropolitan University, Pilestredet 35, 0166 Oslo, Norway

Neural Cellular Automata Artificial Life Cellular Automata

Ask PDF