Von Neumann, Automata, and the Problem of Organized Complexity

In September 1948, John von Neumann gave a lecture at the Hixon Symposium in Pasadena called “The General and Logical Theory of Automata.” The text we have is, according to von Neumann himself, only a slightly edited version of that lecture, and he explicitly presents it as an outline rather than a finished theory. That is useful context, because the paper moves across several subjects that later became separate fields: computer architecture, reliability, neural networks, information representation, complexity, universal computation, and self reproduction. What holds them together is not a particular machine. It is a question about organization: what happens when large numbers of relatively simple components are arranged into systems complicated enough to compute, survive errors, recognize patterns, and eventually reproduce their own organization? [1]

This is also why reading the paper as a collection of predictions misses most of what is interesting about it. Von Neumann is not sitting in 1948 making a list of technologies that will exist decades later. He is looking at the first serious electronic computing machines, comparing them with nervous systems and living organisms, and trying to figure out which problems are accidental consequences of the technology of his time and which problems are fundamental to any sufficiently complicated automaton. The result is uneven, sometimes speculative, and in places obviously tied to the biology and hardware knowledge available in 1948. But the structure of the argument has aged much better than many of the details.

Start with the boundary of the problem

Von Neumann begins by splitting the study of a complicated organism into two different problems. The first is to understand the individual elementary components themselves, for example the physical and chemical operation of a neuron. The second is to assume that the behavior of those components is already known well enough and ask how a large collection of them can be organized into a functioning whole. He is interested mainly in the second problem, because it is the one that can be approached through mathematics and logic. [1]

His way of doing this is to treat the elementary component as a black box. Instead of modeling every physical process inside it, we specify the stimuli it can receive and the responses it can produce. Then we study networks of such boxes, their connections, their collective dynamics, and whatever regularities appear when very large structures are assembled from them. Von Neumann is careful about what this abstraction can and cannot tell us. It can tell us what follows from a chosen model of the element, but it cannot prove that the model is biologically correct. That question still belongs to physiology, chemistry, and physics. [1]

This distinction is now so deeply embedded in engineering that it is easy to overlook. We build computers almost entirely by hiding lower levels behind interfaces. A software process does not need to know how a transistor works, and a distributed database does not need to model the switching behavior of every gate inside every processor. Von Neumann is applying the same intellectual move to biological organization. The point is not that substrate is irrelevant, but that there is a separate problem at the level of composition.

That becomes important later in the paper because many of the properties he cares about do not belong to any individual component. Reliability can be a property of a network made from unreliable parts. Complicated logical behavior can be a property of a network made from simple threshold elements. Self reproduction can be a property of a machine that combines a general constructor with a transferable description. Again and again, the interesting thing happens one level above the individual element.

Why computers are unusually sensitive to mistakes

Von Neumann then turns to computing machines and asks what makes them special compared with other artificial automata. His answer is not simply speed. A computer can execute an extremely long chain of operations in which later operations depend on earlier results, and in such a chain a single incorrect step may affect everything that follows. In the numerical examples of the paper, he estimates that a substantial scientific calculation may correspond to around a billion elementary operations, and later considers machines that may need to execute as many as 10¹² operations for a problem. [1]

He contrasts this with systems such as microphones, television, or radar, where enormous numbers of physical events also occur but where an error in one event often contributes only a small amount to the final noise. Computation is different because individual operations can have structural consequences. A wrong intermediate value can become another operation’s input, so the error is not necessarily diluted by everything around it. Von Neumann even remarks that a substantial fraction of the steps in a computation may be capable of invalidating the result completely. [1]

From this he gets to a point that looks obvious now but was not built into classical logic. It is not enough to know whether a procedure terminates after a finite number of steps. For an actual automaton, the number of steps matters. A procedure taking one thousand operations and another taking 10²⁰ operations may both be finite, but only one may be physically useful. More importantly, if every physical operation carries a small nonzero probability of malfunction, longer computations accumulate more opportunities for failure. [1]

Von Neumann therefore argues that a proper logic of automata will have to care about two things that classical formal logic largely ignores: the length of the chain of operations and the probability that individual logical operations fail. This is not yet computational complexity theory in the later formal sense, and it would be misleading to say that he develops such a theory here. What he does identify very clearly is the physical reason why finiteness alone is an inadequate measure of computation.

Analog and digital are not opposites in the naive sense

The paper then spends considerable time on analog and digital computing. In an analog machine, a number is represented directly by some physical quantity such as an electrical current, a voltage, or a mechanical displacement. A physical process is arranged so that transforming those quantities implements addition, multiplication, integration, or another mathematical operation. The unavoidable problem is noise. Since the physical quantity itself carries the value, an uncontrolled physical fluctuation directly becomes an error in the represented number. [1]

Digital machines change the error model. A number is represented as a sequence of discrete digits, and as long as the physical components remain within their permitted tolerances, small changes in the underlying voltage or mechanical state do not change the logical digit. This allows the system to regenerate discrete states rather than carry every small physical deviation forward. Von Neumann nevertheless emphasizes that digital arithmetic is not magically exact. Finite digit width introduces truncation and rounding, so error returns in another form even if each individual digital operation is performed correctly. [1]

I think this is one of the cleaner parts of the paper because it avoids an argument that still appears today. Digital computation is not nonphysical mathematics implemented by perfect little Boolean objects. The hardware underneath it remains physical, continuous, noisy, and limited. Digital behavior is an engineered regime in which a range of physical states is deliberately treated as the same symbolic state. The real advantage is control over error propagation, not the disappearance of physics.

Von Neumann carries the same idea into biology and does not simply claim that the nervous system is a digital computer. He distinguishes parts of an organism that appear effectively digital from processes that are plainly continuous. Neural impulses can have an all or none character at the level being modeled, while chemical concentrations, blood flow, and other physiological variables remain analog. The organism can therefore contain transitions between analog and digital representations rather than fitting cleanly into one category.

The machine and the organism fail differently

This leads into what I think is the strongest part of the paper. Von Neumann compares the way engineers of his time dealt with a malfunctioning computer with the way a living organism appears to deal with local failure. In an artificial machine, the engineering practice was to make an error visible as quickly as possible, isolate the defective component, and repair or replace it. Because diagnosis became much harder once several independent faults were present, there was strong pressure to catch the first fault before another appeared. [1]

A living organism appears to follow almost the opposite strategy. Local components malfunction, but the immediate objective of the whole system is not necessarily to stop and announce the error. The effect of the malfunction is suppressed, compensated for, or routed around so that normal operation can continue. Repair can happen later. Von Neumann describes this contrast very directly: natural organisms tend to make errors inconspicuous and harmless, while the artificial automata of his time were organized so that errors became conspicuous and potentially disastrous. [1]

Some of his biological statements here are obviously broad, and they should not be read as current neuroscience or cell biology. The useful point is architectural. A system can be built around the assumption that its parts are nearly perfect, or it can be built around the assumption that local failures are normal and that the system must remain useful despite them. Modern computing eventually adopted much more of the second philosophy than the machines von Neumann was describing.

A modern storage system expects disks to fail. A distributed service expects processes and machines to disappear. Networks expect lost packets. Large clusters expect hardware faults simply because a sufficiently large collection of machines produces some fault somewhere almost continuously. The architecture is therefore designed to preserve the service even when the identity and health of its physical components change. This is not proof that computers have become biological, but it is a useful example of the same design principle: system reliability does not have to be identical to component reliability.

Reliability can be constructed

The discussion following the lecture contains a particularly clean numerical example. Von Neumann imagines a machine with a probability of 10⁻¹⁰ of malfunctioning on an individual operation and gives it a problem requiring 10¹² operations. On average, such a machine would experience around one hundred errors during the calculation, making it useless if the computation cannot tolerate them. He then considers three such machines performing the same operations and comparing their results after each one. If two agree, their value is accepted. [1]

Under the simplifying assumption that the relevant failures are independent, the probability that two machines fail on the same operation is on the order of 10⁻²⁰. Accounting for the three possible pairs and 10¹² operations gives the estimate von Neumann states in the discussion, roughly 3 × 10⁻⁸ for the whole problem, or about one chance in 33 million. His calculation is an illustrative argument, not a complete fault model. Correlated faults, a failing comparison mechanism, common power failures, shared software errors, and many other real failure modes would complicate the picture substantially. But the conceptual point survives all of that: adding imperfect components can make the system more reliable if they are arranged so that their failures do not coincide in the same way. [1]

This reverses a common intuition about redundancy. If the only thing being optimized is the number of components, three machines doing the work of one look wasteful. If the quantity being optimized is the probability of completing a long computation correctly, the redundant design may be much more efficient. The extra hardware is not accidental overhead. It is what creates the desired system property.

Redundancy also changes how information should be represented

Von Neumann makes a related argument using the nervous system. He considers the problem of transmitting a continuous quantity, such as pressure, through nerve impulses. In the model he discusses, the nerve still produces individual all or none pulses, but information about the continuous stimulus is carried by the pulse frequency. He gives illustrative values of 125 impulses per second under one pressure and 71 per second under a smaller pressure. [1]

He compares this counting method with ordinary positional number representation. To distinguish roughly one million values, a binary representation requires about twenty binary digits, while a literal counting representation could require vastly more events. The binary code is much more economical. But the counting representation has another property: losing one pulse changes a count of one million only slightly, while corrupting a significant digit in a positional representation can change the represented number dramatically. [1]

Von Neumann generalizes this into a trade between efficiency of notation and safety from error. Redundancy costs something, but that cost can buy stability. The specific neurophysiology in this part reflects the state of knowledge in 1948 and should not be turned into a general claim that nervous systems simply encode continuous quantities by rate and nothing else. Modern neuroscience knows many temporal and population coding schemes. But the information theoretic argument he extracts from the example is much broader than the example itself.

We still make that trade everywhere. Error correcting codes add bits that carry no new user payload but make recovery possible. Replication stores information more than once. Checkpoints consume storage so computation can survive interruption. Quorums duplicate work so a service can tolerate missing participants. The most compact representation is not necessarily the best representation when the medium is unreliable.

A logic for real machines has to admit failure

This brings von Neumann to his proposed future theory of automata. Classical logic treats operations such as conjunction and negation as exact. Physical automata cannot. An actual gate, relay, neuron model, or other switching element can malfunction with a low but nonzero probability, so a useful mathematical theory of large automata has to include those exceptions rather than pretending they do not exist. [1]

He expects such a theory to look less purely combinatorial and more analytical than classical formal logic. In particular, he points toward thermodynamics in the statistical tradition of Boltzmann as an example of a theory where enormous numbers of microscopic events can be handled through macroscopic probabilistic quantities. Von Neumann does not develop the mathematical machinery in this lecture, and it would overstate the paper to claim that a complete probabilistic logic appears here. What appears is the requirement for one: logical operations embedded in physical systems need a theory that includes chain length, error probability, and large scale statistical behavior. [1]

That is a subtle change of perspective. Once the logical gate is treated as a physical event with a probability distribution rather than an infallible primitive, reliability itself becomes something that must be synthesized. The question is no longer whether a gate is reliable, but how a hierarchy of mechanisms transforms one error rate into another.

McCulloch and Pitts, and the limits of explicit description

The paper then turns to formal neural networks, specifically the work of Warren McCulloch and Walter Pitts. Von Neumann uses a simplified neuron with excitatory inputs, inhibitory inputs, a threshold, and a fixed delay. In the particular presentation here, he considers threshold values of one and two. If enough excitatory inputs are active and no inhibitory input is active, the formal neuron emits a pulse after the specified delay. He repeatedly notes that this is an axiomatic simplification, not a realistic physiological description of a neuron. [1]

Von Neumann summarizes the important McCulloch and Pitts result in strong terms: any functioning that can be described logically, strictly, unambiguously, and in finitely many words can be realized by a suitable finite formal neural network. It is worth keeping the attribution in that sentence. This is von Neumann’s formulation of what he takes the result to mean in the context of his argument, not a good reason to casually replace the entire McCulloch and Pitts paper with the modern slogan that neural networks can do anything. [1]

More interestingly, von Neumann immediately says that formal realizability does not solve the practical problem. A network may exist but be too large to fit inside the organism or any machine we can build. He then raises a second issue: perhaps some behaviors are difficult to capture in a compact explicit verbal or logical description even though a physical network realizes them perfectly well. [1]

His example is visual analogy. Describing a clean geometric triangle is easy, but real recognition includes curved triangles, incomplete triangles, shapes defined by shading, and an open ended family of objects we still treat as related. A sufficiently exhaustive symbolic catalogue can become enormous, and the general concept of analogy is much broader still. Von Neumann suggests that it may be possible for the connection pattern of the visual brain itself to be the simplest practical expression of the principle we are trying to describe. [1]

This is one of the sections that reads most naturally today, but it is also easy to overinterpret. Von Neumann is not describing gradient descent, learned representations, deep learning, or anything resembling a modern Transformer. The point is more general and, I think, more interesting. A network implementing a complicated function may sometimes be a more economical specification of that function than the explicit formal description we hoped to replace it with.

That problem did not disappear when neural networks became practical. We now routinely train systems whose parameters implement functions for which we do not possess compact symbolic equivalents. We can run the system and experimentally characterize its behavior, but converting the entire function into a short set of explicit human readable rules may be harder than retaining the network itself. Von Neumann’s wording is unusually cautious here, but the representational problem he identifies is real.

Turing gives him the key abstraction

From neural networks, von Neumann moves to Alan Turing’s theory of computing automata. He describes Turing’s machine in terms of a finite set of internal states and an indefinitely extendable tape containing symbols. The important part for his argument is the universal automaton. A general description of a particular automaton can itself be represented as information, and another automaton can interpret that description and imitate the behavior of the described machine. [1]

Universality changes the relationship between mechanism and behavior. You do not need to construct a different physical machine for every computation. A sufficiently general machine can stay fixed while a finite description determines which specific machine it is currently emulating. In modern language this feels completely ordinary because we live inside layers of interpreters, virtual machines, compilers, containers, and emulators. In von Neumann’s argument, however, it becomes the bridge to something more unusual.

Turing’s automata produce symbolic output on a tape. Von Neumann wants to ask about automata that produce other automata. So he broadens the problem: instead of a universal machine that reads a description and simulates the described machine, consider a universal constructor that reads a description and physically constructs the described machine from a reservoir containing suitable elementary components. [1]

This is an abstract construction, and it is important not to confuse it with all of von Neumann’s later work on cellular automata and self reproducing systems. In this lecture he describes the principle at a higher level. He first assumes a finite catalogue of elementary parts, noting that roughly a dozen types can suffice under a reasonable choice of primitives, then asks whether an aggregate of these parts can construct another aggregate exactly like itself when placed in an environment containing plentiful copies of those elementary parts. His answer is yes in principle. [1]

How the self reproducing automaton actually works

The construction is easier to understand if you keep its components separate. Automaton A is a general constructor. Give A an instruction describing some automaton, and A constructs that automaton from the available elementary parts. The instruction itself is represented physically as an aggregate of components with the required notational properties. Von Neumann explicitly notes that a constructor can build something larger than itself because the information specifying the larger object arrives in the instruction, whose own size can grow with the complexity of the object being built. [1]

Automaton B has a different job. It copies an instruction. It is not required to interpret what the instruction describes, in the same way that a machine copying punched tape does not need to understand the program represented by the holes. Von Neumann then introduces a control mechanism C. C first instructs A to construct the automaton described by the input instruction, then instructs B to copy that instruction, inserts the copy into the newly constructed automaton, and finally releases the new construction as an independent entity. [1]

He calls the combined system A + B + C by the name D. Now comes the recursion. Construct an instruction I_D that describes D and place I_D into D. The resulting aggregate, which he calls E, contains both the machinery D and an instruction describing that machinery. When E runs, A constructs another D, B copies I_D, and C places that copy inside the newly built D. What comes out is another E. [1]

The reason this does not create an infinite regress is that the description and the machinery are not produced in the same logical step. D already exists before I_D is attached to it. The instruction describes D, not the entire infinite history of descriptions of descriptions. During reproduction, the machinery is reconstructed from the description while the description itself is copied separately. This distinction between interpreting information and copying information is the central trick.

Where the comparison with genes is valid, and where von Neumann says it is not

Von Neumann himself makes the biological comparison. He says that the instruction roughly performs the function of a gene and that B performs the fundamental reproductive act of duplicating the genetic material. That is his analogy, not a modern interpretation added to the paper later. But in the very next part he warns that the analogy has limits. He specifically says that a natural gene probably does not contain a complete description of the object whose construction it stimulates and may instead contain more general pointers or cues. [1]

That caveat matters. It would be easy to turn his argument into a simplistic statement that DNA is a blueprint and the cell is just a universal constructor reading it. Modern developmental biology makes that picture inadequate, and von Neumann was already suspicious of a literal version of it. His abstract automaton deliberately uses a complete construction description because that makes the logical problem clean. Natural development can distribute information across genetic material, cellular machinery, spatial organization, chemical gradients, previous state, and environment.

The more durable point is not that living organisms implement his automaton exactly. It is that self reproduction becomes logically manageable once the system separates a general constructive mechanism from information that can both influence construction and be transmitted to the next generation. That is the abstract pattern he was after.

Mutation falls out of the same architecture

Once reproduction depends on a copied instruction, von Neumann can modify the instruction and ask what survives. He notes that many changes will be lethal in the simple sense that the resulting system no longer reproduces. Other changes can leave the reproduction machinery intact while altering some property of what the system produces. He explicitly describes this as analogous to a nonlethal mutation. [1]

He then gives a slightly extended construction in which the instruction describes not only D but also another automaton F. The resulting self reproducing system constructs its own successor and also produces F as an additional product. If a change in the relevant part of the instruction replaces F with F′, the system remains self reproductive but now produces F′. This gives him a very simple abstract model in which inherited information can change without destroying the mechanism that transmits it. [1]

It is tempting to jump immediately from here to Darwinian evolution, artificial life, or recursive self improvement. Those are reasonable later connections, but the paper itself stays more limited. Von Neumann is showing that self reproduction and heritable variation are logically compatible with an automaton built from simple parts. He is not presenting a full evolutionary theory, and he is certainly not describing modern autonomous software agents. Keeping that boundary actually makes the result more interesting, because the construction does not need those later concepts in order to work.

There may be a threshold where complexity stops degrading

The self reproduction argument appears inside a broader discussion of what von Neumann calls complication. He starts from an intuitive problem. If automaton A constructs automaton B, it seems that A must somehow contain B’s description plus all the machinery required to interpret that description. This suggests a degenerative process in which an automaton can construct only something less complicated than itself. Nature is an obvious counterexample because organisms produce organisms of comparable complexity. [1]

The universal constructor changes the picture by allowing complexity to be divided between the general construction machinery and the supplied instruction. A fixed constructor can build objects more complicated than itself as long as the instruction supplying the missing structure is correspondingly complicated. The output does not have to be contained inside the constructor in the naive sense. Some of what determines the output enters as information. [1]

Von Neumann ends this part with a more speculative claim. He suggests that below some minimum level of complication, construction may indeed be degenerative, while beyond that level self reproduction and even construction of higher entities become possible. In his words, complication and organization may become self supporting and even increasing beyond some threshold. This is not a theorem about complexity in the modern algorithmic sense, and the paper does not define a general quantitative measure that would let us calculate the threshold. It is a research direction emerging from the self reproduction construction. [1]

I think that distinction is important because this is exactly the kind of sentence people now pull out of old papers and attach to whatever current technology they are excited about. Von Neumann’s point is narrower. Once a system is sufficiently general to interpret descriptions and reproduce the machinery that interprets them, construction no longer has to reduce complexity at every generation. That is already a substantial result without turning it into a prophecy.

What actually holds the paper together

The paper can look like a sequence of separate topics if you read it quickly: analog computers, neurons, reliability, logic, Turing machines, self reproduction. But there is a fairly consistent path through all of them. Von Neumann is trying to understand what changes when a system crosses from a manageable collection of components into a highly complicated organization where errors, representations, and internal descriptions become part of the problem.

The first answer is that the behavior of the whole cannot be identified with the behavior of one component. Physical noise can be suppressed by digital organization. Component failures can be suppressed by redundant organization. Complicated behavior can be represented by the connectivity of a network rather than a short external logical formula. A universal constructor can separate general mechanism from specific description. Self reproduction can then preserve the organization by rebuilding the mechanism while separately copying the description that makes rebuilding possible.

That is why I would not describe “The General and Logical Theory of Automata” primarily as a paper about neural networks, or self reproducing machines, or fault tolerant computers. It touches all of those things, but they are examples of the larger issue. Von Neumann is looking for a theory of highly complicated organized systems, and he thinks neither the formal logic nor the engineering practice of 1948 is adequate for the job.

Reading it now

Some parts of the paper are plainly historical. Its estimates for biological complexity come from the science of the time. Its neuron model is intentionally crude. Its account of neural rate coding is much simpler than what we know today. Its comparison between engineered and biological materials belongs to an era of relays, vacuum tubes, large mechanical structures, and early electronic computers. Even its vocabulary feels unfamiliar in places because von Neumann uses “complication” where we would probably reach for several different modern concepts.

But those limitations are also useful because they expose the argument. He cannot appeal to modern machine learning, modern distributed systems, molecular genetics, error correcting memory, cloud infrastructure, or semiconductor reliability. He has to reason from first principles about what a complicated automaton must somehow accomplish.

The result is a paper in which several concepts that now live in different departments are still visibly connected. Reliability is connected to information representation. Information representation is connected to the physical implementation of logic. Logic is connected to neural networks. Universal computation is connected to machine description. Machine description is connected to construction, construction to self reproduction, and self reproduction to the possibility of preserving complexity.

What I find most useful about the paper is this refusal to place all the intelligence or reliability of a system inside its smallest parts. A part can be unreliable while the system is reliable. A primitive can be simple while the network is complicated. A constructor can be relatively general while the object it constructs is specialized. A description can remain passive data in one operation and become active instructions in another. The interesting properties belong to the organization and to the transformations between levels.

We now build systems large enough that this way of thinking matters again. A large computing service is not one machine. A modern AI system is not just a model file. It can include models, inference runtimes, tools, memory, external data, schedulers, networks, other software, and people. Replacing one component does not necessarily replace the system, and understanding one component does not necessarily explain the behavior of the composition.

That does not mean von Neumann had a theory of modern AI hidden in a 1948 lecture. He did not. What he had was a clear view of a harder problem that remains open: how should we reason about machines once their organization becomes complicated enough that reliability, behavior, description, and reproduction are properties of the whole system rather than obvious properties of its individual parts?

That is a much better reason to keep reading the paper than saying that it predicted the future.

References

1. The General and Logical Theory of Automata, John von Neumann, Hixon Symposium, 1948.