Turing-Machine Variants & the Church–Turing Thesis

the stored-program concept

Early machines were rewired for each new task: to make them do something different, engineers physically replugged cables and flipped switches, a job that could take days. The stored-program concept is the now-obvious-seeming idea that lifted computing out of that dark age: keep the program in the same memory as the data, so that to run a different task you simply load different instructions, no rewiring at all. The program becomes just another kind of data the machine reads.

Concretely, in a stored-program (von Neumann) computer, both the instructions of a program and the data it works on live in one addressable memory. The processor repeats a simple loop: fetch the next instruction from memory, decode what it asks, execute it (which may read or write data, or jump to another instruction), and repeat. Because instructions sit in memory like any other bytes, a program can even read or modify instructions, including its own. Loading a new program is nothing more than writing new bytes into memory.

This is the engineering realization of the universal Turing machine. Turing's universal machine takes the description of any machine M as input data and then behaves like M; a stored-program computer takes a program as input data and then behaves as that program dictates, the same idea, the same self-application of 'a program is just a string', made out of transistors instead of tape. It is why one laptop can be a word processor, a game, and a compiler on the same hardware. The honest caveat is historical and conceptual: the von Neumann design is one influential architecture, not the only possible one (the Harvard architecture keeps program and data in separate memories), and 'stored-program' is about flexibility and universality, not about speed.

When you double-click an app, the operating system copies that program's bytes from disk into memory and then sets the processor to start executing them. Nothing was rewired; the very same CPU that ran your last program now runs this one, exactly as a universal Turing machine switches behavior based on the <M> it is handed.

Program is data: load different bytes, get different behavior, the universal machine made of transistors.

The stored-program idea is the practical descendant of universality, not a separate kind of power. And the von Neumann layout is one architecture among others (e.g. Harvard, with separate program and data memories), chosen for flexibility, not because it is the only option.

Also called
von Neumann architectureprogram as datastored-program computer范紐曼架構馮諾伊曼架構