The Complete Guide to Algorithms & the Birth of Computing

1. The Oldest Idea in Computing

Algorithms are four thousand years older than computers.

Somebody once had to work out how to explain, to a person who could not see what you were doing, exactly how to make a cup of tea — every step, in order, with nothing assumed. That is the entire foundation of computing, and it turns out to be far harder than it sounds. 'Add milk' assumes you know when. 'Boil the kettle' assumes you know it needs water in it first.

Algorithm: A finite sequence of unambiguous steps that takes an input and produces an output. Three conditions do all the work: finite (it must stop), unambiguous (no step requires judgement), and general (it works for every valid input, not just one). Long division is an algorithm. 'Season to taste' is not.

The word comes from al-Khwarizmi, a scholar working in Baghdad around 820 CE, whose book on solving equations was so influential that a Latinised version of his name became the term for a step-by-step procedure. Another of his books gave us 'algebra'. The methods themselves are older still: Babylonian clay tablets carry step-by-step procedures for solving problems, and Euclid's method for finding the greatest common divisor of two numbers, written around 300 BC, is still taught and still used.

Euclid's algorithm has been in continuous use for over 2,300 years. It runs, essentially unchanged, inside the encryption protecting the connection your browser is using right now.

For most of history an algorithm was something a person carried out. The word computer was a job title: someone, very often a woman, who did calculations by hand. Observatories, insurance companies and artillery offices employed rooms of them, working in shifts on tables of numbers.

That is where the story starts, because human computers make mistakes. Navigation tables, used by ships to fix their position, were riddled with errors, and an error in a navigation table could put a ship on a reef. Getting the mistakes out was not an academic problem. It killed people.

What just happened

• Algorithms are ancient — Babylonian tablets, Euclid, al-Khwarizmi
• 'Computer' originally meant a person doing calculations by hand
• Human error in printed mathematical tables had lethal consequences at sea

Computing did not begin with electronics. It began with the problem of doing a reliable procedure reliably, and the realisation that humans are the unreliable part.

In the 1820s a furious Englishman looked at a table of errors and said out loud that he wished the calculations had been done by steam.

2. The Engine That Was Never Built

Babbage designs a computer out of brass, and cannot finish it.

Charles Babbage was a mathematician of formidable ability and impossible temperament. Confronted with the error-riddled tables of his day, he designed the Difference Engine: a machine of gears and columns that would calculate polynomial values by repeated addition and — crucially — print the results directly, removing the typesetter as another source of mistakes.

The government funded it. It was never completed. Babbage fell out with his engineer, redesigned constantly, and then had a better idea and lost interest — which, from the government's point of view, was the last straw.

The better idea was the Analytical Engine, and it is the genuine leap. The Difference Engine could do one kind of calculation. The Analytical Engine was designed to do any calculation you could specify: it had a 'mill' that did the arithmetic, a 'store' that held numbers, instructions fed in on punched cards borrowed from the Jacquard weaving loom, and — the decisive feature — the ability to branch, choosing a different next step depending on a result. That is a computer. Babbage designed it in the 1830s.

Conditional branching: The ability to do one thing if a condition holds and something else if it does not — what a programmer writes as 'if'. Without it a machine can only follow a fixed sequence. With it, the machine's behaviour can depend on its own results, which is where all the power comes from.

Ada Lovelace (1815–1852)

Translated a paper about the Analytical Engine and tripled it with her own notes.

Daughter of the poet Byron, taught mathematics from childhood partly to keep her from inheriting her father's temperament, Lovelace translated an Italian account of Babbage's machine and appended notes of her own, labelled A to G. Note G contains a step-by-step method for the machine to compute a sequence called the Bernoulli numbers — including a loop — which is why she is widely described as the first person to publish a program for a general-purpose machine.

“The Analytical Engine might act upon other things besides number … supposing, for instance, that the fundamental relations of pitched sounds … were susceptible of such expression and adaptations, the engine might compose elaborate and scientific pieces of music of any degree of complexity or extent.”

This is the leap nobody else made for a century: that the machine's real subject is not arithmetic but symbols. Everything digital — audio, images, text, video — is that idea.

Commonly believed: Ada Lovelace invented programming single-handed / Ada Lovelace did nothing but transcribe Babbage's work.

Actually: Both extremes are wrong and both are still argued about. Babbage had written trial sequences of operations before her notes; her Note G is more developed and was published under her initials, and her insight about symbols beyond number is unmistakably hers and appears nowhere in Babbage. Historians argue about attribution because the surviving correspondence is genuinely ambiguous — which is itself worth knowing about how history gets made.

What just happened

• Babbage designed the Difference Engine to remove human error from mathematical tables
• The Analytical Engine added memory, punched-card instructions and conditional branching
• Lovelace published a method for computing Bernoulli numbers and saw the machine could manipulate any symbols

The architecture of a computer existed a century before the technology to build one. What was missing was not the idea but the electronics.

The next step came from an unlikely direction — a crisis in pure mathematics about whether every true statement can be proved.

3. The Machine That Could Be Any Machine

Turing answers a question about logic and invents computer science by accident.

In 1928 the mathematician David Hilbert posed the Entscheidungsproblem — the decision problem. Is there a definite procedure that could take any mathematical statement and determine, mechanically, whether it is provable? Most mathematicians expected the answer to be yes. It would have made mathematics, in principle, a machine you could turn.

To answer it, a 24-year-old Cambridge graduate had to make 'definite procedure' precise. So Alan Turing imagined the simplest possible machine that could carry out any procedure at all: an infinite paper tape divided into squares, a head that can read and write one symbol at a time, and a small table of rules saying what to do given the current symbol and the machine's current state. Move left, move right, write, change state, halt.

That absurdly primitive device can compute anything any computer you have ever used can compute. Your phone is faster and vastly more convenient, but there is no calculation it can perform that a Turing machine could not, given enough tape and enough time. This claim has a name — the Church–Turing thesis — and after ninety years nobody has found a counterexample.

Then Turing took the step that matters most. Since the rule table is itself just a pattern of symbols, you can write it onto the tape and build one machine that reads another machine's description and behaves like it. That is the universal machine: hardware that becomes whatever software you feed it. Before this, machines did one job. After it, a machine is a general-purpose thing that runs programs.

And the answer to Hilbert's question was no. Turing showed that no procedure can decide, for every program and input, whether the program will eventually stop — the halting problem. If such a procedure existed, you could use it to build a program that halts if and only if it does not halt, which is a contradiction. Mathematics contains questions no mechanical method can settle.

Alan Turing (1912–1954)

Defined computation, then spent the war breaking the code that used it against him.

Turing published the universal machine paper in 1936, at twenty-four, essentially as a side effect of answering a logic question. He was a serious long-distance runner, an awkward and direct man, and the person British intelligence turned to when they needed the Enigma cipher broken.

What just happened

• Hilbert asked whether a mechanical procedure could decide all mathematical truths
• Turing defined computation using an imaginary tape-and-rules machine
• He proved the halting problem undecidable — and invented the universal machine on the way

The universal machine is the reason one device can be a phone, a camera, a games console and a word processor. Everything else is engineering.

Four years later, that theory met a war, a wooden hut in Buckinghamshire, and a cipher that changed every midnight.

4. The War Machines

Bletchley Park, and the first computers in the world.

1940 — Hut 8, Bletchley Park

German naval Enigma has around 150 million million million possible settings, and they change at midnight. Every message intercepted must be broken within the day, or the U-boats find the convoys first. Rooms of people are working through possibilities by hand and losing the race every night.

Turing's answer, developed with Gordon Welchman and building on earlier Polish work, was the Bombe: an electromechanical machine that did not search for the answer but eliminated impossible settings at speed. The clever part was logical, not mechanical. If you can guess a crib — a phrase likely to appear, such as a weather report or 'nothing to report' — you can chain the guess through the machine's wiring, and any setting producing a contradiction is ruled out wholesale.

For a different German cipher, the Lorenz machine used for high-command traffic, the engineer Tommy Flowers built Colossus in 1943–44: 1,500 valves, programmable by switches and plugs, reading paper tape at 5,000 characters a second. It was the first large-scale electronic digital computer to actually work. The Post Office told Flowers it would be unreliable; he built it anyway, partly with his own money.

Colossus was so secret that most of the machines were destroyed after the war and the people who built and operated them — including thousands of women in the Wrens who ran them — were forbidden to say so for decades. The history of computing was written without them, which is why 'the first computer' is usually credited elsewhere.

After the war Turing worked on designs for stored-program computers and on the beginnings of what would be called artificial intelligence. In 1952 he was prosecuted for homosexuality, then a criminal offence in Britain, and accepted hormone treatment as an alternative to prison. He died in 1954 from cyanide poisoning, ruled a suicide. He was thirty-nine. An official apology came in 2009 and a royal pardon in 2013.

What just happened

• The Bombe eliminated impossible Enigma settings using cribs and logical contradiction
• Colossus, built by Tommy Flowers in 1943–44, was the first working electronic digital computer
• The work stayed secret for decades; Turing was prosecuted in 1952 and died in 1954

The war turned computing from a branch of logic into an industry — and the secrecy that surrounded it distorted the history of the field for a generation.

Before he died, Turing asked a question that is now on the front page of every newspaper — and proposed a way of settling it.

5. How the Machine Actually Speaks

Everything, all of it, is numbers.

A computer has no concept of a letter, a colour or a sound. It has switches that are on or off. Everything else is a convention for representing things in those two states — and once you see the convention, the magic disappears in the best possible way.

Binary: Counting with two digits instead of ten. In decimal each column is worth ten times the one to its right; in binary each is worth two times. So 1011 means 8 + 0 + 2 + 1 = 11. One digit is a bit; eight bits make a byte, which can hold 256 different values.

The same trick, applied to everything

• Text — agree that 65 means 'A'. That is all a character encoding is; modern Unicode is the same idea extended to every writing system on Earth
• Images — split the picture into a grid and store three numbers per square for red, green and blue intensity
• Sound — measure the air pressure tens of thousands of times a second and store each measurement as a number
• Instructions — the program itself is numbers too, which is exactly Turing's universal machine in physical form

Underneath, the arithmetic is done with logic gates: tiny circuits computing AND, OR and NOT. Combine a few dozen of them and you can add two numbers. Combine a few billion — which is roughly what is in the processor you are reading this on — and you get everything else. There is no additional secret ingredient at any level.

This is why the same file can be music or nonsense. A sequence of bytes has no inherent meaning; the meaning lives entirely in which program opens it. Open an image as text and you get gibberish, because you have applied the wrong convention to the right numbers.

Programming languages exist because writing directly in numbers is unbearable for humans. A language lets you write something readable, which a compiler or interpreter translates into the machine's actual instructions. Every abstraction in computing is a way of hiding detail so a human mind can hold the problem — and every one of them is, ultimately, still switches.

What just happened

• Computers store everything as binary — on and off
• Text, images and sound are conventions for turning things into numbers
• Logic gates perform arithmetic; programming languages hide the detail from humans

Once you know that data is meaningless without a convention, most of computing stops being mysterious and starts being engineering.

Which brings us to the question Turing asked in 1950, and which is now argued about daily.

6. Can Machines Think?

Turing's test, the objections, and why the question is harder than it looks.

Turing opened his 1950 paper by proposing that the question 'can machines think?' is too vague to answer, and replacing it with a game. A human judge holds text conversations with a human and a machine without knowing which is which. If the judge cannot reliably tell them apart, on what grounds do we deny the machine thought?

The imitation game: Turing's actual name for it; 'the Turing test' came later. Notice what he did: he refused to define thinking and instead defined a test we could actually run. That move — replacing an unanswerable question with an operational one — is a piece of intellectual craft worth stealing.

He then listed the objections against himself, including one he called the argument from Lady Lovelace: she had written that the Analytical Engine can only do what we know how to order it to perform. Turing's reply was that machines constantly surprise their programmers, and that a machine that learns is not obviously limited to what its designer foresaw.

If a machine passes the test, does it understand anything?

• Behaviour is all we ever have: You have no access to anyone else's inner experience either. You grant other people minds because of how they behave. Applying a stricter standard to a machine than to your friends is a prejudice, not an argument — and Turing said exactly that in 1950.
• The Chinese Room says no: John Searle imagined himself in a room following rules for manipulating Chinese symbols he does not understand. To someone outside, the room answers fluently. Inside, there is no comprehension anywhere — only rule-following. Passing the test may show only that we are easy to fool.

This is no longer a thought experiment. Systems now hold conversations that would have astonished Turing, and the interesting result is that the test has aged strangely: fluent language turns out to be easier to produce than anyone expected, which tells us less about machine minds than it does about how much we were assuming language implied. The philosophical question — whether producing the right words is the same as meaning them — is exactly where Turing and Searle left it.

The practical questions have overtaken the philosophical ones. What happens when a system is used to decide who gets a loan, a job interview or bail, and it has learned its patterns from records of past human decisions that were unfair? You do not need to settle whether the machine thinks to see that this matters enormously.

What just happened

• Turing replaced 'can machines think?' with a conversational test in 1950
• He answered the major objections in advance, including Lovelace's
• Searle's Chinese Room argues that behaving intelligently is not understanding

This is the oldest live argument in computing, and everything now being said about artificial intelligence is a variation on it — usually by people who do not know it is seventy-five years old.

Now you know the story

Everything in this story was worked out before anyone had a working computer. The theory came first, from people arguing about mathematics and logic, and the machines caught up decades later. That is unusual in the history of technology — and it is why the ideas are still the ones we use.

• Define an algorithm precisely enough to recognise one anywhere
• Explain why Babbage's engine mattered even though it was never finished
• Describe a Turing machine in plain words, and say what it proved
• Argue both sides of 'can machines think?' using the test Turing actually proposed

Back to Algorithms & the Birth of Computing →

Incandio does not yet support a Computer Science specification. This course is not mapped to any Computer Science course on any board — if you are taking a Computer Science exam, check your specification for what is actually required.