Computer

Computer

Computers connected in a network
Defining property	Programmability (general-purpose symbol manipulation)
Theoretical basis	Turing machine (1936)
First stored-program run	Manchester Baby, 21 June 1948
Core components	Processor, memory, storage, input, output

A computer is a machine that carries out sequences of operations automatically, according to instructions it stores and can change. The second half of that sentence carries the weight: a calculator performs arithmetic, but a computer holds a program in the same memory as its data, which is what makes one machine able to do arbitrarily many different things.

Nearly all computers follow the same broad organisation:

• a processor that fetches an instruction, decodes it, executes it, and moves to the next;
• memory holding both instructions and data, addressable by number;
• storage that survives loss of power;
• input and output connecting the machine to the world.

Because instructions live in ordinary memory, a program can generate or modify other programs. Compilers, interpreters, operating systems and virtual machines all rest on this fact. Alan Turing identified it in 1936 in his description of a universal machine, several years before any hardware could exploit it.

Devices for computation are ancient; the abacus is the oldest to survive in use. In the seventeenth century Wilhelm Schickard, Blaise Pascal and Gottfried Leibniz built geared machines that performed arithmetic directly. All were calculators: they did one fixed kind of work.

Charles Babbage designed the Difference Engine in the 1820s to compute mathematical tables, then in the 1830s the Analytical Engine, which would have been programmable by punched card, with a separate arithmetic unit and store, and conditional branching. Neither was completed in his lifetime. Ada Lovelace's 1843 notes on the Analytical Engine describe a method for computing Bernoulli numbers on it and observe that such a machine could manipulate symbols of any kind, not only numbers.

Electronic machines arrived during and just after the Second World War. Colossus, at Bletchley Park in 1943, was programmable by switches and plugs and was used against German teleprinter ciphers. ENIAC, completed in 1945, was programmed by rewiring, which could take days. The decisive step was the stored-program design, in which the program is held in the same read–write memory as the data. The Manchester Baby ran the first stored program on 21 June 1948; EDSAC at Cambridge followed in 1949 as a working service machine.

The transistor (1947) replaced the vacuum tube; the integrated circuit (1958) put many transistors on one piece of silicon; the microprocessor (1971) put an entire processor on a single chip. Component counts on a chip roughly doubled every two years for decades, an observation known as Moore's law, and the cost of a given amount of computing fell by orders of magnitude. Computers moved from air-conditioned rooms to desks, then to pockets, then into objects that are not thought of as computers at all.

By count, embedded computers vastly outnumber every other kind.

Computers are limited in principle as well as in practice. Turing's 1936 proof of the undecidability of the halting problem shows that some questions about programs cannot be answered by any program. Complexity theory adds a second boundary: many problems are decidable but require resources that grow so quickly with input size that solving large instances is not feasible. Both limits are mathematical facts about computation, not shortcomings of current machines.

• Alan Turing
• Internet
• Free software