CS Paper Radar

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

Charles C. Norton

cs.LO cs.NE ·submitted 2026-10-08 16:25 UTC · v1
code/data

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.

Comment
42 pages, 4 figures, 7 tables. Rocq proofs, code and run records: https://huggingface.co/phanerozoic/threshold-computers

Closest papers

Nearest neighbours by meaning across the whole index.

Dalek: A Constructive Agent Machine

cs.AI ·2026-09-03 ·Wanpeng Xie
similarity 0.57
Abstract

We present Dalek, a closed machine designed for agents that realizes self-maintenance, self-evolution, self-reproduction, and self-organization on any substrate satisfying a general host contract. The machine is built from three primitives---actors, messages, and channels. Four obligations---a host boundary, a construction language, admissible transitions, and rule heredity---give its boundary, identity, and closure a structural basis. Von Neumann's 1948 self-reproducing automaton supplies a hereditary constructional core: a self-description together with a constructor, a copier, and a controller. Dalek combines this core with the four obligations and rederives its medium for a text-and-message agent substrate, adding explicit structures for boundary, identity, history, and growth. A large language model and a compiler occupy the payload position and form a general capability producer. New capabilities are authored, compiled, installed into the description, and inherited by descendants. The same path produces the machine's own organs and even its runtime, closing heredity and evolution within the machine.

0.17

Many Processors, Still One Computer: The Nested Parallel von Neumann Architecture and Nested BSP

cs.DC cs.AR ·2026-09-15 ·Heng Liao
similarity 0.56
Abstract · 14 pages, 4 figures

The contest in large-scale AI computing is no longer whether one processor can be made stronger, but whether a million of them can still behave as a single computer. This paper argues that two extensions are required. First, classic BSP, nested recursively, becomes a plan that holds at every scale: each superstep consists of parallel work, then exchange and aggregation, then a barrier, and at every layer the participating units are peers. Second, the von Neumann single-machine architecture, extended past its master--slave habit, becomes the Nested Parallel von Neumann Architecture: a nest of peer-equal layers, from chip package to autonomous zone, joined end to end by one memory-semantic interconnect, the Unified Bus. The software nest and the hardware nest correspond layer by layer, and the $τ$ Scaling law folds time at every layer. We examine which workloads the nested structure serves, AI training above all but much of classic HPC as well, and describe the hardware decisions that make the nesting physical. Many processors, still one computer.

0.33

Complexity of liveness in ring Petri nets and of halting in chip-firing on simple digraphs

cs.CC cs.DMcs.FL ·2026-10-16 ·Eike Best, Raymond Devillers, Petr Jančar, Matěj Ošťádal
similarity 0.54
Abstract

A ring Petri net (weighted circuit, cyclic weighted T-system) consists of a single directed circuit with arbitrary positive arc weights. We show that deciding liveness of ring Petri nets is coNP-complete, and that coNP-hardness holds in the strong sense already for token-conserving rings, in which every transition consumes and produces the same number of tokens. The proof is a short reduction from the covering problem for systems of residue classes (the complement of Simultaneous Incongruences). Together with a known reduction to circuits, it follows that liveness of weighted T-systems (weighted marked graphs, synchronous dataflow graphs) is coNP-complete, and coNP-hard in the strong sense. As a further consequence, the halting problem for chip-firing on simple directed graphs is NP-complete, which answers a question of Farrell and Levine. On 7 October 2026, the problem of liveness was posed to the AI model Claude Opus 5.5 (Anthropic), which found the reduction, also suggesting the application to the chip-firing problem, and wrote a first version of this paper; the human authors checked it and, together with the model, revised it iteratively into the present form.

0.24

Composability rather than computation sets the cost of an analog EML hardware fabric

cs.ET cs.AR ·2026-09-15 ·C. Teuscher
unusual similarity 0.51
Abstract

The operator eml(x, y) = exp(x) - ln(y) with the constant 1 generates the elementary functions, a continuous counterpart to NAND. Whether it yields a useful fabric had not been asked of hardware. We ask in network models, circuit simulation and SkyWater 130 nm layout. Four bipolar junctions evaluate the operator for 13 fJ, beating a width-matched digital datapath by 4-134x. The fabric assembled from them is not cheap: it loses to resource-matched baselines, and over the reals its grammar excludes trigonometry. Amplifiers holding those junctions' operating points take 74.5% of a cell's current, so a cell costs 3000 times what they spend. Extracted non-idealities cost 2.6x when a cell must hold a value and nothing when it need only be repeatable. Sharing them across cells recovers two of the three orders. The premise was that a universal primitive licenses a uniform machine. It survives in the primitive and fails in the machine.

0.26

Batched Feedback and the Random-Access Wall in Search-Based Graph Construction

cs.DB ·2026-09-24 ·Édgar Chávez
similarity 0.51
Abstract

Navigable graphs for nearest-neighbor search are built either incrementally, each inserted point searching a graph that mutates as construction proceeds, or in batch over a fixed substrate, which buys determinism and parallelism at a price in build time. We measure that price and find where it comes from. Instrumenting a tuned Vamana and PiPNN and building every system repeatedly in a paired design on one 64-thread machine, we separate build time into work (distance evaluations) and cost per evaluation. Letting the batch builder's substrate mutate in $B$ synchronous blocks recovers the feedback loop of incremental construction while the graph stays a function of (data, seed, parameters, $B$): eight trees with batched feedback match thirty-two frozen trees, and the build does $0.88\times$ Vamana's distance work. Yet it takes $1.55\times$ Vamana's wall-clock, because the mutating substrate costs more per evaluation. Pushing further, we find a wall that no search-based builder crosses. Every one of them, incremental or batched, evaluates distances adaptively, one dependent random access at a time, and runs $20$-$27\times$ below a dense kernel on the same machine at $d \approx 100$, five to six times of it with the data resident in cache. The gap is not a low-dimension artifact: an adaptive evaluation costs $d^{1.04}$ and a blocked one $d^{0.63}$, so the wall grows as $d^{0.4}$ and is twice as high at $d = 960$ as at $d = 128$. PiPNN's order-of-magnitude build advantage is that kernel: it evaluates as many distances per point, but as fixed-in-advance dense blocks. We show the beam cannot be batched after the fact (the useful density of a lockstep block is 2-3%), state the wall as a two-ceiling roofline, and delimit it: it binds whenever the distance is a black box or the evaluation order is data-dependent.

0.47

The Rhythm of the Tiles: Narrow and Low Temperature Computation and Simulation in Synchronous Tile Self-Assembly

cs.CG ·2026-10-12 ·Florent Becker, Phillip Drake, Benjamin Durbin, Nicolas Ollinger, Brent Orlina +1 more
publishedtheoryunusual similarity 0.51
Abstract · 112 pages, 52 figures, Submission to the 2027 ACM-SIAM Symposium on Discrete Algorithms (SODA27)

In this paper, we prove that the synchronicity provided by the syncTAM can be leveraged to perform two additional feats impossible in the asynchronous aTAM. The aTAM has long been known to be equivalent to finite automata in the one-dimensional case. For our first set of results, we prove that this still holds when a finite, fixed amount of space is available in the second dimension. Yet, surprisingly, in the synchronous setting, a small, fixed, width is enough to simulate a Turing Machine. This holds even in the non-cooperative setting. For our second set of main results we prove that there exists a single set of syncTAM tiles that can be used to simulate any syncTAM system simply by using those tiles to create a scaled version of the seed structure of the original system and then letting the tiles from that set self-assemble from the scaled seed structure. While it has been shown (FOCS 2012) that such a tile set also exists in the aTAM for simulating all aTAM systems, that "intrinsically universal" (IU) tile set requires cooperativity (and is impossible without cooperativity as shown in SODA 2014). We prove there exists an IU tile set in the syncTAM that works without cooperativity. Furthermore, there exists a tile set that is IU for the class of directed systems (i.e. systems which each have a single terminal assembly) while remaining directed during simulation. This was shown to be impossible in the aTAM (FOCS 2016).

0.40

Neural Logic, Invariance, and the Retina---McCulloch and Pitts

cs.FL q-bio.NCcond-mat.dis-nncs.NE+1 ·2026-09-02 ·Nima Dehghani
similarity 0.50
Abstract · Book chapter from NeuroAI: Theoretical Foundations of Dynamics, Learning and Computation in Brains, Minds, and Machines. Includes reproducib…

This chapter reconstructs the McCulloch-Pitts program as a physics of neural computation rather than the familiar cartoon of a binary neuron. The 1943 logical calculus is developed in both directions: given a net, characterize the propositions realized by its activity; given an admissible logical expression, construct a net that realizes it. We recover the original distinction between thresholded excitatory summation and absolute inhibitory veto-one the weighted-threshold form cannot preserve for arbitrarily large excitatory inputs-and read unit-time delay as the physical realization of logical depth. Recurrence is treated exactly: an autonomous, deterministic network of finitely many binary units has a finite state space, so every trajectory eventually enters a periodic orbit-a fact about finite-state dynamics, not unbounded Turing computation. A single threshold element realizes only linearly separable Boolean functions, whereas finite feedforward networks of them synthesize any Boolean function on a finite domain. We then follows McCulloch and Pitts beyond threshold logic. The 1945 heterarchy paper turns cyclic preference into an obstruction to representation by a scalar utility. The 1947 work on universals asks how a physical network can identify inputs related by nuisance transformations, developed here via group averaging and feedback canonicalization. The 1959 frog-retina study makes the adequate-stimulus question experimental, revealing parallel invariant operations before the brain proper. Spike-triggered analysis shows how a nonlinearly driven neuron can have a vanishing first-order average while second-order statistics recover its hidden selectivity: methodological failure can masquerade as physiological absence. Modern mathematical tools are used without projecting their notation onto the historical papers, and limitations of the idealization are stated explicitly.

0.25

Cyclotron: A Recurrence Language for Expressing Interprocessor Communication

cs.DC ·2026-10-14 ·Shiv Sundram, Akhilesh Balasingam, Nathan Zhang, Kunle Olukotun, Fredrik Kjolstad
similarity 0.50
Abstract

We present Cyclotron, a compiler that expresses streaming dataflow algorithms using recurrence equations, which are then compiled to distributed topologies of interlinked processors. Our compiler lowers a language of recurrences over logical iteration spaces into per-processor programs of sends, receives, and computations. In these recurrences, data accesses are not limited to external accesses to memory; data can live separately on the iteration space itself, allowing internal points to communicate values directly with other points. Users specify this communication directly in the recurrence language, which allows them to express various communication patterns such as a nearest-neighbor systolic exchange, a one-to-all broadcast, a bidirectional split ring, or an asymmetric and piecewise broadcast pattern, which are often not supported by standard distributed linear algebra libraries. These recurrences describe the algorithm and communication independently of how they map onto the hardware. A programmer then chooses which dimensions execute across processors and which execute over time, without rewriting the entire program. Users only specify data dependencies across the iteration space, and the compiler safely generates a program, per process, with correct placement of both communication and computational operators according to the chosen space--time mapping. We evaluate distributed matrix multiplication, TRSM, Cholesky, and fused Cholesky--TRSM on up to 16 CPU nodes and 16 GPUs, comparing against ScaLAPACK, SLATE, and cuSolverMp. Cyclotron is competitive with and often outperforms these hand-optimized libraries; for Cholesky, the best communication strategy changes with problem size and architecture.

0.25