Probabilistic Logics and the Synthesis of Reliable Organisms From Unreliable Components

TL;DR — In 1956 von Neumann asked how to compute reliably when every gate lies to you with probability \varepsilon, and answered with the first threshold theorem: below a critical noise level, redundancy and "restoring organs" can drive the output error as low as you like, at logarithmic cost. Transistors got so good so fast that the theory sat unused for decades — but near-threshold CMOS, analog in-memory accelerators, and quantum error correction have all dragged component error rates back into exactly the regime his math was built for, making statistical correctness a live design axis again.

The idea as von Neumann had it

The paper — Caltech lectures from 1952, published in the Shannon–McCarthy Automata Studies volume in 1956 — starts from a premise that sounded like engineering realism at the time and reads like heresy now: error is not an accident to be eliminated, but an essential part of the process, to be treated by thermodynamical methods, the way Shannon had just treated noise in communication.

The setup: you have gates (he uses 3-input majority elements and Sheffer strokes, i.e. NANDs) that each fire wrongly with probability \varepsilon, independently, on every use. Naive composition is hopeless — errors accumulate and a deep circuit's output converges to a coin flip. The question is whether any amount of cleverness can keep the final answer's error probability below some target \delta, and at what cost.

His answer has two parts, and both were genuinely new:

1. A possibility result. For \varepsilon below a threshold, a redundant construction computes any Boolean function with output error \le \delta, with multiplicative overhead that grows only like \log(1/\delta) (he computes the constants; they are ugly but finite).
2. An impossibility flavor. Above a critical noise level, no construction works — reliable computation is not achievable at any cost. He works out that a noisy 3-input majority gate is useless once \varepsilon \ge 1/6.

That pairing — a threshold separating "correctable at logarithmic cost" from "fundamentally impossible" — is the intellectual template for every fault-tolerance theorem since, including the quantum threshold theorem.

Multiplexing: a bit becomes a statistic

The construction is the part worth internalizing. Von Neumann replaces every logical wire with a bundle of N wires, and redefines what a bit is: the bundle carries a 1 if more than a fraction 1-\Delta of its lines are stimulated, a 0 if fewer than \Delta are. In between is a malfunction. The bit is now the statistic of an ensemble, not the state of a device.

Computation on bundles has two alternating stages:

• The executive organ: N copies of the noisy gate, each operating on one line drawn from each input bundle. This computes the function but degrades the statistics — if a fraction \xi of input lines are wrong, the output bundle is worse.
• The restoring organ: the error-correcting step. Take the bundle, randomly permute it, split into triples, and feed each triple to a majority gate (he builds majority from NANDs when needed). If a fraction \xi of lines are stimulated, each output line is stimulated with probability roughly

plus the gate's own error \varepsilon. This cubic is the whole story. It has stable fixed points near 0 and 1 and an unstable fixed point at 1/2: bundles that are mostly right get pushed toward entirely right, every stage. Noise perturbs \xi away from the fixed points; restoration pulls it back. Reliable computation is a dynamical system with attractors, and the threshold \varepsilon^* is where gate noise flattens the sigmoid enough that the attractors merge and vanish.

The random permutation is essential and easy to miss: it decorrelates errors between stages, so the i.i.d. analysis keeps holding. It is the same move as random interleaving in coding theory and, arguably, an ancestor of the randomness in dropout.

Von Neumann's own numbers were pessimistic — his Sheffer-stroke multiplexing needs roughly \varepsilon < 0.0073, and he needed bundle sizes in the thousands for the reliability he wanted (he explicitly notes the scheme is only sensible when the error requirements are severe). Later work sharpened the picture considerably: Hajek and Weller proved 1/6 is exactly tight for 3-input gates, Evans and Pippenger pinned the 2-input NAND threshold at (3-\sqrt{7})/4 \approx 0.0886, and Dobrushin–Ortyukov and Pippenger established that O(\log(1/\delta)) redundancy is both sufficient and, for most functions, necessary.

Why it was shelved

The paper was written against vacuum-tube reality: machines with ~18,000 tubes where a tube failure every day or two was normal, and where von Neumann (thinking also of neurons, which he estimated as slow, noisy, and numbered ~10^{10}) reasonably assumed unreliable components were a permanent condition.

Then the transistor made the premise false. By the mid-1960s, silicon logic gates had per-operation error rates so low they were unmeasurable — modern nominal-voltage CMOS is somewhere below 10^{-15} per gate-op, arguably far below (soft-error rates are dominated by cosmic rays hitting SRAM, not logic misfiring). Compare that to von Neumann's threshold of ~10^{-2}: the theory addressed a problem twelve-plus orders of magnitude away from where engineering lived. Deterministic correctness was free, so nobody paid for statistical correctness. ECC memory and TMR in avionics survived as niche descendants, but the core vision — logic itself run in a noisy regime by design — had no customer. The bundle overhead (thousands of lines per bit, in his constants) made it strictly worse than just building better components, which is exactly what happened.

What changed

Three separate roads lead back to \varepsilon \sim 10^{-2}:

• Energy scaling. CMOS dynamic energy goes as CV^2; pushing supply voltage toward the transistor threshold cuts energy per op several-fold, but timing-error probability rises steeply (roughly exponentially in the shrinking voltage margin) as you approach and cross the threshold. The cheapest joules are the noisy ones. Krishna Palem's "probabilistic CMOS" line of work made this explicit in the mid-2000s: treat \varepsilon as a knob you trade against energy.
• Analog and in-memory compute. Crossbar matrix-vector multiplies in ReRAM/PCM/flash suffer device variability, drift, and read noise; effective error rates per analog MAC are in the 10^{-3}–10^{-2} range depending on precision, not 10^{-15}. Current practice hides this behind conservative quantization and calibration — i.e., by not running in the efficient regime.
• Quantum computing. Physical two-qubit gates sit at 10^{-3}–10^{-2} error; the surface-code threshold is around 10^{-2}. The quantum threshold theorem (Aharonov–Ben-Or, Kitaev, Knill–Laflamme–Zurek, late 1990s) is a direct descendant of this paper, and Google's 2024 below-threshold surface-code result is von Neumann's fixed-point picture running on hardware: error per logical operation suppressed exponentially as code distance grows, exactly because the physical error is below \varepsilon^*.

What a 2026 revival looks like

The serious version is an ultra-low-voltage or analog accelerator co-designed with statistical restoration, optimized end-to-end. The objective is explicit: total energy per reliable operation is

where E_{\text{op}} falls steeply as you let \varepsilon rise (voltage scaling, fewer analog calibration cycles) and the redundancy factor R \sim \log(1/\delta) divided by a term that blows up as \varepsilon \to \varepsilon^*. This product has an interior minimum at nonzero \varepsilon — the von Neumann design point, which no shipping digital accelerator targets today.

What to reuse from the paper: the bundle abstraction (a value is an ensemble statistic), the alternating compute/restore structure, and above all the fixed-point analysis for setting \varepsilon safely below threshold. What to replace: majority-of-3 restoration is the 1952 answer; modern sparse-graph codes and lightweight checksum schemes (ABFT for matrix multiplies) achieve the same restoration with overheads of tens of percent, not the 1000× his constants imply. And the workload should be neural-network inference, which is already half-tolerant: a MAC error is a bounded numerical perturbation, not a catastrophic bit flip, so the "restoring organ" can be as cheap as an occasional redundant checksum row in a crossbar, or even the network's own trained robustness (noise-injection training as learned error correction). The concrete experiment: a near-threshold or analog tile where you sweep supply voltage / analog precision from the reliable regime into the noisy one, with restoration overhead adapting online, and measure whether the energy-per-inference minimum sits inside the noisy regime. My expectation — and the honest gap — is that for DNNs the win is real but the full multiplexing machinery is overkill; the interesting open question is where general-purpose (control-flow, exact) computation lands, since there a single flipped branch is fatal and you need the real theory.

Already tried, descendants, and what's open

Vindicated, partially and in translation. Quantum error correction is the theory's unambiguous triumph — same theorem structure, now experimentally demonstrated below threshold. Classical descendants are scattered: Pippenger, Feder, Spielman and others built the rigorous theory of noisy circuits and fault-tolerant computation with polylog overhead; stochastic computing (Gaines, 1960s) literally computes on bit-stream statistics, i.e. bundles serialized in time, and resurfaces every decade for low-power ML; approximate computing and Palem-style PCMOS explored the energy-error trade empirically; razor-style timing-error detection in commercial low-voltage designs is restoration-by-replay rather than by redundancy. There's also a credible reading of the paper as proto-neuroscience: population coding — a quantity represented by the firing fraction of a neural ensemble, restored by nonlinear recurrent dynamics — is the multiplexing scheme, and von Neumann says outright that he had neurons in mind.

Still open: a classical hardware platform that actually lives at the interior optimum rather than retreating to reliability; tight energy-reliability lower bounds connecting the \log(1/\delta) overhead to thermodynamic cost per corrected error; and whether learned representations can subsume explicit restoration — that is, whether training is a compiler targeting von Neumann's noisy machine.

Where to read it

The paper is in Automata Studies (Shannon & McCarthy, eds., Princeton, 1956), doi:10.1515/9781400882618-003; bibliographic details verified. It's long and the notation is dated, but §§8–11 (the multiplexing construction and the fixed-point analysis) are the payload. Read alongside: Evans & Pippenger, "On the maximum tolerable noise for reliable computation by formulas" (1998) for the sharp classical thresholds; Aharonov & Ben-Or's fault-tolerance paper to see the same theorem reborn for qubits; Palem's probabilistic CMOS papers for the energy framing; and Winograd & Cowan's 1963 monograph Reliable Computation in the Presence of Noise, the first book-length attempt to marry this paper to Shannon's coding theory — itself a "before its time" document worth revisiting.