Computer science

A machine that reads and writes symbols on a tape, following a finite table of rules, can compute anything any computer can. A universal machine U, given the description of any machine M and its input x, does exactly what M would do. And no machine can decide, for every program, whether it will ever stop.

Use: Why one general-purpose computer replaces every special calculating machine, given enough memory and time; and why no test can prove in general that a program will never hang, so programs are kept simple and checked by parts.

First: Alan Turing, On Computable Numbers, 1936 (Proceedings of the London Mathematical Society; MacTutor).

Adding two binary digits A and B with a carry in gives a sum bit S and a carry out, each a short combination of AND, OR and exclusive-OR (⊕). Any switch that is on or off, a relay, a valve or a transistor, can build these.

Use: Thirty-two adders in a row add two 32-bit numbers; from addition come subtraction, multiplication and every calculation a computer makes (computing).

First: Claude Shannon showed relay circuits obey Boolean algebra, 1938 (Transactions of the AIEE; MacTutor).

An algorithm's cost is counted by how its steps grow with the size n of the job. Halving a sorted list at each look finds any entry in log₂ n looks; good sorting methods take about n log n steps; comparing every item with every other takes n².

Use: A sorted register of a million names is searched in 20 looks, an unsorted one in up to a million: keep ledgers and indexes in order. A method that grows as n² and takes 1 second for 1,000 items takes about 12 days for a million (accountability).

First: Big-O notation, Bachmann, 1894, and Landau, 1909 (MacTutor); von Neumann's merge sort, 1945 (MacTutor).

The number of transistors that can be made on one chip doubled about every two years for half a century: from 2,300 on the first microprocessor in 1971 to more than 100 billion on the largest chips of the 2020s. The doubling has slowed as transistors approach the size of a few dozen atoms.

Use: Why computing power that filled a room became a phone in a generation, and why it rests on the most demanding manufacturing chain there is (semiconductors).

First: Gordon Moore, 1965, revised to two years in 1975 (reprinted in Proceedings of the IEEE).

A signal containing no frequency above fₘₐₓ is captured exactly by samples taken more than twice that often. Sample too slowly and high frequencies masquerade as false low ones (aliasing), so they are filtered out first.

Use: Telephones sample speech up to 3.4 kHz at 8,000 times a second; music CDs sample at 44,100 a second to cover hearing to 20 kHz. The same rule sets how often to read any instrument.

First: Whittaker, 1915; Nyquist, 1928; Kotelnikov, 1933; Shannon's proof, 1949 (Proceedings of the IRE).

No channel of bandwidth B hertz, with signal power S against noise N, can carry more than C bits a second without error; and with good enough coding it can come as close to C as wanted.

Use: A 3 kHz telephone line with a signal 1,000 times the noise (30 dB) carries at most about 30,000 bits a second, which is where dial-up modems stopped. More bandwidth raises capacity far faster than more power (radio).

First: Claude Shannon, A Mathematical Theory of Communication, 1948 (Bell System Technical Journal).

If every two valid code words differ in at least d places, any d − 1 errors are noticed and up to half that many can be put right by choosing the nearest valid word. Hamming's (7,4) code adds 3 check bits to 4 data bits and corrects any single error.

Use: Memory, discs and deep-space links correct errors this way; a QR code still reads with about 30 % of it damaged at its highest correction level. A check digit on an account or book number catches most single typing errors (networks).

First: Richard Hamming, 1950 (Bell System Technical Journal); Reed and Solomon, 1960 (Journal of SIAM).

Combine each bit of the message m with a bit of a key k (exclusive-OR, or adding letters modulo 26). If the key is truly random, as long as the message and never used twice, the ciphertext c reveals nothing at all about the message: it is unbreakable, not just hard.

Use: Still used where the key can be carried by hand in advance. Reusing a pad breaks it completely, which is how wartime Soviet messages were read.

First: Vernam's teleprinter cipher, 1917; Shannon proved its perfect secrecy, 1949 (Bell System Technical Journal).

Each side picks a secret number (a and b) and publishes g raised to it, modulo a large prime p. Each can then compute the same key gᵃᵇ from the other's public number and its own secret; an eavesdropper who sees only gᵃ and gᵇ cannot, because undoing the power modulo p is too hard.

Use: Every secure web connection begins with a key agreed this way, so a password typed into a site is not read on the line.

First: Whitfield Diffie and Martin Hellman, 1976 (IEEE Transactions on Information Theory).

Anyone can encrypt with the public pair (n, e); only the holder of d, which can be found only by knowing the two large primes p and q whose product is n, can decrypt. Run the other way, d signs a message and anyone can check the signature with e.

Use: Digital signatures and the certificates that prove a website is who it says. A large quantum computer running Shor's algorithm (1994) would break RSA and Diffie–Hellman, so in 2024 the US standards body published replacements (NIST FIPS 203).

First: Rivest, Shamir and Adleman, 1978 (Communications of the ACM).

In any steady system, the average number of things inside L equals the rate they arrive λ times the average time each spends inside W. It holds whatever the order of service or the pattern of arrivals.

Use: A clinic seeing 6 patients an hour, each in the building for 1½ hours, has 9 people inside on average: to shorten the queue, raise the rate of service or cut the time each spends. The same sum sizes granaries, warehouses, waiting rooms and computer servers.

First: John Little's proof, 1961 (Operations Research).

A model with adjustable numbers w is fitted to data by repeatedly nudging each number a small step η downhill on the error L. Backpropagation computes those slopes for every number in a many-layered neural network in one backward pass.

Use: Fits everything from a straight line (least squares) to the networks that recognise speech, read X-rays and translate. It needs a great deal of data and computing, and learns whatever biases the data hold.

First: Rumelhart, Hinton and Williams, 1986 (Nature); Nobel Prize in Physics 2024 to Hopfield and Hinton (Royal Swedish Academy).

Each word or piece of input asks a query Q of every other piece's key K; the softmax turns the matches into weights that sum to one, and the output is the weighted mix of their values V. Stacked many times, it lets every part of a text look at every other part at once.

Use: The core of the large language models since 2018, of modern machine translation and speech recognition, and of protein-structure prediction (biology as engineering).

First: Vaswani and colleagues, Attention Is All You Need, 2017 (arXiv).