Bits have no meaning: the stored-program bargain

The byte 01100001 is three things at once. As text, it is the letter a. As a binary number, it is 97. A processor can also fetch it while its instruction decoder is reading a program. Then it is part of an operation. The pattern itself does not say which reading is correct. That is not a quirk of one machine or a gap in its documentation. It is the founding bargain of stored-program computers. Their power, performance limits, security problems, and mathematical boundaries all follow from it.

This article is the first of a pair. It follows the bargain: where the idea that code is data came from, what it makes possible, what it costs, and how eighty years of engineering has tried to control the ambiguity. The companion article, The halting problem: why code can only be run, never read, takes up the consequence this article keeps approaching: no algorithm can read a program and say what it will do. It follows that problem to the end.

The byte that was three things at once

The claim is precise, so let’s state it precisely. In a stored-program machine, instructions live in the same read-write memory as the data they operate on. The same mechanism fetches and executes both. The computer-history literature puts the consequence this way: bit patterns have no inherent type: “A byte - a fixed-width group of bits, the smallest unit most memories address - is neither data nor instruction in itself. Interpretation alone decides: whatever pattern the processor’s fetch logic delivers to the instruction decoder becomes an instruction; everything else is data.”

A compiler gives the clearest daily proof. It reads a text file of source and produces a file of bytes that the operating system will later load and execute. Between those moments, the same bytes are a number to the linker (addresses, sizes), a payload to the file system, and finally a sequence of instructions to the processor. A byte does not need to “know” what it is for any of this to work.

The alternative - which computing could have chosen and partly did - separates the two kinds of memory: instructions in one store, data in another, never the twain meeting. That design exists. It is called the Harvard architecture, after the Harvard Mark I, and it survives in microcontrollers. It has real advantages, including the one this article will return to. The stored-program design gave up that separation in exchange for something more valuable.

Where the bargain was struck: Turing’s universal machine

The stored-program idea first appears in precise form not in a computer laboratory but in a 1936 logic paper: Alan Turing’s “On Computable Numbers, with an Application to the Entscheidungsproblem.” Turing was not building a machine. He was making “mechanical procedure” mathematically exact to answer a question in logic. His machines are abstractions - a tape, a finite set of states, read, write, erase, move - and they run forever, printing the digits of a real number. The key move is this: Turing shows how to encode a machine as an integer.

The encoding is literal. Every machine table is written as quintuples - current state, scanned symbol, symbol to print, direction to move, next state. The quintuples become a string, which is then converted digit by digit into one big number. Turing’s worked example, the machine that prints 010101..., has a standard description beginning DADDCRDAA;DAADDRDAAA;... and one of its description numbers is 31332531173113353111731113322531111731111335317. A program can be an ordinary integer: enumerable, inspectable, and consumable as input by other programs.

That last phrase is the point. Section 6 of the paper asserts, and section 7 demonstrates with a complete machine table, that “it is possible to invent a single machine which can be used to compute any computable sequence”: given a tape bearing the description of any machine M, the universal machine U computes the same sequence as M. The machine’s editor, Robin Gandy, states the consequence flatly: “The universal machine is a stored-program machine; that is, unlike Babbage’s all-purpose machine, the mechanisms used in reading a program are of the same kind as those used in executing it.” One mechanism reads one kind of storage. What it reads is a program or data according to what the mechanism does with it, not according to what it is.

Software as an industry starts with this encoding step. Compilers, loaders, assemblers, interpreters, virtual machines, and just-in-time code generators are all programs that treat programs as data. The universal machine is the stored-program concept in logical form. Its physical form was a decade away.

The bargain becomes hardware: 1945

The electronic stored-program computer is conventionally dated to the “First Draft of a Report on the EDVAC,” written in June 1945 and circulated under John von Neumann’s name alone - to the documented fury of the machine’s actual Moore School co-authors, J. Presper Eckert and John Mauchly. The historiography is a mess (the report’s circulation was later ruled a public disclosure that barred the patent claims), but the design fact it records is unambiguous. Section 14.1 stipulates that “the orders which are received by CC come from M, i.e. from the same place where the numerical material is stored.” Orders and numbers share one memory and one channel. They have no types. The typeless byte, a logical curiosity in 1936, became an architectural fact in 1945. It has stayed one for eighty years.

The architecture’s price was named by John Backus in his 1977 Turing Award lecture, “Can Programming Be Liberated from the von Neumann Style?” The von Neumann bottleneck follows from the one channel: the processor is “a tube that can transmit a single word” between itself and memory, and the whole program - every instruction, every datum - must pass through it, one word at a time. The physical cost is measured in energy. A modern measurement puts a 32-bit integer add at about 0.1 picojoules, and a DRAM read at roughly 640 - six thousand times more, just to move the operand. The processor and memory got fast. The channel between them did not. Cache hierarchies, out-of-order execution, and today’s “memory-bound” AI inference all negotiate with that gap.

That is the first tax. It is a bill in time and energy. Caches can hide it, and co-locating memory with compute can attack it directly. The second tax is harder to remove. It comes from the same fact.

What the bargain makes possible: code that rewrites itself

Because instructions are data in memory, a program can compute a new instruction as if it were a number, store it over an existing instruction, and execute the result. Self-modifying code was a designed capability in the early machines, not an accident or a hack. The 1946 Burks-Goldstine-von Neumann design explicitly required that instructions be “encoded to be modifiable by other instructions,” so that “one program [can] be treated as data by another.” The first generation of machines had no index registers and no addressing modes. Array access meant updating the address field of the accessing instruction. Procedure call meant patching the return address directly into the return jump. That is why early machine code could not be recursive. For a few years, modifying code was the only way to write a useful loop.

Engineers then removed the practice on purpose. Manchester invented the index register specifically to process arrays “without the need for self-modifying code” - the B-lines, conceived in 1948, in hardware by 1949. The IBM 704 brought three index registers to mass-produced machines in 1954, the machine on which FORTRAN and LISP were first developed. Routine instruction modification went from “powerful technique” to “extremely hard to debug” in about a decade.

It never died. It became managed. Just-in-time compilers are self-modifying code with a permission slip: V8 runs a four-tier pipeline that emits fresh machine code during execution; QEMU is explicitly “a dynamic translator” that converts guest code to host code on first encounter; the Linux kernel rewrites its own text via ftrace and kprobes and livepatching. Lisp showed how to make code-as-data safe at the language level: programs are S-expressions, and S-expressions are data that programs can construct, transform, and evaluate - homoiconicity, in Alan Kay’s phrase, “the primary representation of programs is a data structure in the language itself.” This site’s own metaprogramming article uses the same idea in Elixir: quote turns any expression into a data structure, unquote splices it back, and macros are ordinary Elixir code that writes Elixir code.

The same capability also created a security problem. The Morris Worm of November 1988 overflowed a 512-byte buffer in fingerd with a crafted 536-byte string carrying shellcode - data executed as instructions - and infected roughly 6,000 hosts, about ten percent of the Internet at the time. Polymorphic viruses went further and rewrote their own bodies to evade pattern detection; the 1260 virus could generate on the order of a billion decryptor variants within 1,260 bytes of code. The defense stack that followed - W^X (“write xor execute,” an OpenBSD default since 2003), the hardware NX bit, control-flow integrity, code signing - is an eighty-year effort to restrict the default the stored-program model set in 1945. Each layer narrowed what the machine would consent to execute. Each prompted a workaround that required the next. Return-oriented programming, the 2007 discovery that arbitrary computation can be composed from existing code “gadgets” with nothing injected at all, made the point bluntly: the boundary between code and data, once dissolved by design, can never be re-established by analysis - only policed at runtime.

What happens when the decoder guesses wrong

If self-modifying code is data deliberately rewritten into instructions, “Halt and Catch Fire” is what happens when data bytes are executed as instructions by accident. It is the same typelessness, but the instruction decoder has no trap.

The name began as a 1960s joke instruction. The canonical story attached a fire to the IBM System/360, but no evidence supports it. The documented reality is a Motorola 6800 decode accident. The 6800 used one-byte opcodes, and only 197 of the 256 possible opcode values were valid - with no trap for the other 59. Feed an invalid byte to the decoder and its undecoded bits “plinko” through the chip’s transistors. In his December 1977 BYTE article, Gerry Wheeler named the hex opcodes 9D and DD the “Halt and Catch Fire” instructions. He described what they actually do: “the address bus turns into a 16 bit counter,” interrupts are ignored, and the only recovery is RESET - with “Well, almost” appended about the fire. Motorola then adopted the accident and kept the behavior deliberately as a RAM-scan self-test. The literature calls it “the first intentional built-in self-test feature on a Motorola microprocessor.” The pattern continued - the 6502’s dozen KIL/JAM opcodes, the Pentium F00F bug of 1997, an unprivileged denial of service triggered by the three-byte sequence F0 0F C7 C8 - until modern chips made the illegal-instruction trap the norm.

This site’s own philosophy gives the software answer to the same problem. Let it crash acknowledges that a process can enter a state you did not design and cannot reason it out of. Do not try to prove it will not happen. Isolate the process and let it die. The BEAM takes the million-process version of that bet: an infinite loop or a wedged decoder takes down one process, not the node, and the supervisor’s job is to restart what crashed. HCF is “let it crash” at the silicon level, minus the isolation. Hardware needed eighty years of design to buy that isolation back.

The two taxes

The stored-program bargain levies two taxes. They are not equal. The bandwidth tax is the price of the single channel between processor and memory: time and energy per bit moved. It is an engineering quantity. Caches can hide it, memory-in-compute designs can relocate it, and a given workload can remove it. The analyzability tax is the price of unification: because code is data, no algorithm can in general read a program and determine what it will do - whether it halts, whether a given byte will ever execute, whether the code modifies itself, whether a binary is malicious. That tax is not an engineering quantity. It is a mathematical boundary. No architecture, no matter how clever, can abolish it. It can only route around it.

Everything in this article’s security history routes around that boundary. W^X, the NX bit, code signing, illegal-instruction traps: none of these mechanisms analyzes anything. Each is policy enforced by hardware. Together they admit that the general question is uncomputable and restrict what the machine will consent to run.

The second tax is the subject of the companion piece, and it deserves the full treatment. The bandwidth tax shaped how fast computers are. The analyzability tax shaped what computers can do at all. It is also why this site grades your code by running it, never by reading it.

Where to go next

• The halting problem: why code can only be run, never read
  • the companion article, on the analyzability tax in full.
• Metaprogramming in Elixir: code that writes code
  • homoiconicity’s safe, governed form: macros, quote, and unquote.
• The role of types in programming
  • what types are for, read against this article: a promise about how the bits will be interpreted, made before the bits are touched.
• Let it crash and What the BEAM actually is - the software answer to states you cannot reason about: isolation and restart.
• Reading Elixir as a JS developer
  • where the loop lives, which is Backus’s question about the von Neumann style wearing everyday clothes.
• Sorting: the wall at n log n - the wall argument as this article’s thesis in action: the order was never in the bytes, so a comparison sort has to earn it, one bit at a time.

The typeless byte is the foundation of everything built since 1945 and the boundary beyond which nothing can be built. It is why your compiler works, why your antivirus cannot promise anything, and why an invalid byte can bring a machine to its knees. No type system, no security stack, and no architecture has abolished the ambiguity. The ambiguity is the stored-program bargain itself. Every mechanism that restores meaning to a byte - a type annotation, a memory-protection bit, a compiler - is a promise layered on top of a machine that, by design, makes no promises at all.