The Algorithm as a Concept: From Euclid to Turing

Zusammenfassung

The algorithm — a finite sequence of unambiguous instructions guaranteed to produce a result — is one of humanity’s oldest intellectual tools, yet it took until the twentieth century to receive a precise definition. From Euclid’s procedure for finding greatest common divisors to Alan Turing’s mathematical model of mechanical computation, the history of the algorithm is the history of humanity learning to think rigorously about procedure itself. Today the concept has escaped mathematics entirely, shaping law, politics, and daily life in ways its originators could not have imagined.

Before the Word: Ancient Procedures

Long before the word existed, the thing itself was already ancient. Around 300 BCE, the Greek mathematician Euclid recorded in his Elements a procedure for finding the greatest common divisor of two numbers: divide the larger by the smaller, take the remainder, and repeat until the remainder is zero. The last non-zero remainder is the answer. The procedure is finite — it will always terminate, because each step produces a strictly smaller number. It is definite — at each step, exactly one action is required. And it is effective — it always produces the correct answer.

Euclid’s algorithm, as it is now universally called, is the oldest named algorithm still in routine use. But it was not the oldest procedure. Babylonian clay tablets from roughly 1800 BCE record systematic methods for division, multiplication, and the extraction of square roots. These tablets are not proofs — they are recipes. They instruct the reader, step by step, what to do. Archaeologists have found what appear to be worked examples alongside the procedures, suggesting that scribal students were being trained to follow computational routines mechanically, without necessarily understanding the underlying mathematics.

What these ancient procedures had in common — though no ancient mathematician articulated it — was structure: a finite list of steps, each unambiguous, collectively guaranteed to terminate and to yield a result. The concept existed in practice for two millennia before anyone thought to name or analyze it.

The name came from an unlikely source. In 820 CE, the Persian scholar Muhammad ibn Musa al-Khwarizmi, working at the House of Wisdom in Baghdad, wrote a treatise titled Kitab al-mukhtasar fi hisab al-jabr wal-muqabala — “The Compendious Book on Calculation by Completion and Balancing.” Its subject was the systematic solution of linear and quadratic equations. Medieval European scholars, translating the text into Latin, rendered al-Khwarizmi’s name as Algoritmi. The word drifted through algorismus to the modern English algorithm, meaning a systematic computational procedure. The same treatise, via its title’s keyword al-jabr, also gave us the word algebra. Al-Khwarizmi thus inadvertently named two of the central concepts of mathematics from a single work.

The medieval tradition that descended from al-Khwarizmi was deeply practical. European merchants and scholars learned to compute with Hindu-Arabic numerals through algorithmic recipes: rules for addition, subtraction, long division, and the extraction of roots. These were taught as procedures to memorize and execute, not as mathematical truths to derive. The distinction between knowing how and knowing why was, for centuries, unremarked.

Mechanical Calculation and the Idea of Procedure

The seventeenth century brought a new question: could procedures be mechanized? Gottfried Wilhelm Leibniz, dreaming in 1679 of what he called a calculus ratiocinator, imagined a universal logical machine that could resolve any dispute by computation. Two philosophers quarreling, he wrote, need only sit down, take up their pencils, and say: calculemus — let us calculate. Leibniz built a mechanical calculator, the Stepped Reckoner, to perform arithmetic. But his deeper vision was of a machine that could execute any valid inference, reducing rational disagreement to a mechanical process.

That vision remained fantasy until Charles Babbage, in the 1820s and 1830s, designed the Analytical Engine — a mechanical computer of extraordinary ambition. Unlike his earlier Difference Engine, which could only evaluate polynomials, the Analytical Engine was general-purpose: it had a store (memory), a mill (processor), and could be programmed via punched cards to execute any sequence of operations. It was never built in Babbage’s lifetime, but its design was coherent, and one person understood its implications more clearly than Babbage himself.

Ada Lovelace, translating an Italian description of the Analytical Engine in 1843, added notes longer than the original text. In those notes she described what is now recognized as the first algorithm intended for execution by a machine: a procedure for computing Bernoulli numbers. She understood that the Engine’s power lay not in any particular calculation but in the generality of the concept — the same machine, fed different instructions, could produce any computable result. Cross-referencing Ada Lovelace and the Analytical Engine, her insight was that the algorithm and the machine were separable: the procedure existed as an intellectual object independent of the hardware that would execute it.

The conceptual leap this opened was vertiginous. If a machine can execute any procedure, what are the limits? Are there well-posed questions for which no procedure exists? The question could not be answered — could not even be properly asked — until someone provided a mathematical definition of what a procedure was.

The Formalization Crisis: Hilbert’s Challenge

In 1900, David Hilbert posed twenty-three open problems to the international mathematical community, setting the agenda for the century. Among them was an ambition more fundamental than any particular problem: to place all of mathematics on a rigorous axiomatic foundation, to prove that foundation consistent (free of contradictions) and complete (every true statement provable), and to find a decision procedure — a mechanical method that, given any mathematical statement, would determine in finite time whether it was provable.

This last demand, the Entscheidungsproblem or “decision problem,” was formally stated by Hilbert and Wilhelm Ackermann in 1928. It seemed, on the face of it, like a reasonable goal. Mathematicians had been finding algorithms for specific problems for millennia. Why not a master algorithm for all of mathematics?

The problem exposed a gap at the heart of mathematics: no one had ever defined what a “mechanical procedure” actually was. For practical purposes, the definition seemed obvious — you know one when you see one. But Hilbert’s question required precision. To prove that such a procedure exists, you would need to construct one that fits some definition. To prove it cannot exist, you would need a definition tight enough to reason about all possible procedures and show that none of them worked. Without a formal definition of algorithm, the Entscheidungsproblem could not be answered.

Info

The Entscheidungsproblem was not merely an academic puzzle. If solved positively, it would mean that all of mathematics could in principle be mechanized — every proof reducible to a finite computation. If solved negatively, it would reveal permanent limits to what formal reasoning could achieve. The question touched the foundations of knowledge itself.

The crisis came from an unexpected direction. In 1931, Kurt Gödel proved his incompleteness theorems: any sufficiently powerful formal system contains true statements that cannot be proved within it. Consistency and completeness could not both hold. Hilbert’s program was, in its most ambitious form, impossible. But the Entscheidungsproblem remained open. Answering it required the missing definition. See David Hilbert and the Entscheidungsproblem for a fuller account of this foundational crisis.

Turing and Church: The Definition Arrives

In 1936, two mathematicians independently provided what was missing, from opposite directions.

Alonzo Church, working at Princeton, had developed the lambda calculus — a formal system for expressing computations as mathematical functions and function application. Church proved, using his system, that the Entscheidungsproblem had no solution: no procedure could decide all mathematical questions. His proof was mathematically rigorous but the machinery was abstract, and the definition of “procedure” embedded in lambda calculus was not immediately intuitive. The full account of Church’s contribution is in Alonzo Church and Lambda Calculus.

Alan Turing, working independently at Cambridge and unaware of Church’s paper until his own was nearly complete, took a different approach. Rather than building up from mathematics, Turing began from a careful analysis of what a human computer actually does. A person following a procedure, he observed, can be in one of a finite number of mental states, is looking at one symbol at a time on a piece of paper, and at each step either writes a symbol, moves their attention left or right, or changes state. Turing abstracted this observation into a mathematical model: a hypothetical machine with a finite set of states, an infinite tape of symbols, and a transition function specifying exactly what to do in each state for each symbol read. This was the Turing Machine.

The Turing Machine was not a blueprint for a device anyone would build. It was a definition. Any procedure that could be followed by a human computer following explicit rules could, Turing argued, be simulated by a Turing Machine. The claim was not proved — it was a thesis about the nature of computation, not a theorem — but it was compelling. And armed with this definition, Turing answered Hilbert’s question.

Consider the halting problem: given a description of any algorithm and any input, determine whether that algorithm will eventually terminate or run forever. Turing proved, by a precise diagonal argument, that no Turing Machine can solve the halting problem for all possible inputs. The proof works by assuming such a machine exists, constructing an input that causes it to contradict itself, and deriving a contradiction. The halting problem is undecidable: no algorithm can solve it.

The Entscheidungsproblem fell as a corollary. Hilbert’s dream of a master decision procedure was not merely unrealized — it was impossible in principle. And the impossibility was established by the very act of defining what an algorithm was. The definition and the limitation arrived together.

The Church-Turing Thesis — that Turing Machines and lambda calculus capture exactly the same class of computable functions, and that this class corresponds to everything intuitively computable — remains a thesis rather than a theorem, because “intuitively computable” resists formalization. But in the ninety years since, no one has found a credible counterexample. Every model of computation anyone has proposed turns out to compute exactly what Turing Machines compute. The definition seems to have found its target. For more on Turing’s contributions, see Alan Turing and the Enigma.

The Computer Age: Algorithms as Engineering

The theoretical definition of algorithm arrived just as physical machines capable of executing algorithms were being built. The von Neumann architecture of the late 1940s — a stored-program computer with memory, a processor, and input/output — made the Turing Machine practical in a form that could be manufactured. Suddenly the question was not “what is an algorithm?” but “what are good algorithms?”

Early programmers, working close to the hardware, discovered that the same problem could be solved by procedures of wildly different efficiency. Sorting a list of a thousand items with bubble sort — repeatedly swapping adjacent elements until the list is ordered — required on the order of a million operations. Merge sort, which recursively divides the list and merges sorted halves, required roughly ten thousand. The problem was identical; the algorithms were not.

Expressing and comparing these differences required a vocabulary. Big-O notation, borrowed from number theory, provided it: an algorithm running in O(n²) time scales quadratically with input size, while O(n log n) scales nearly linearly. The notation abstracts away hardware details, allowing algorithms to be compared as mathematical objects independent of the machine that runs them.

Donald Knuth’s monumental The Art of Computer Programming, begun in 1962 and still being completed, was the first systematic treatment of algorithms as objects of study in their own right — to be analyzed for efficiency, proven correct, and aesthetically evaluated. Knuth established that algorithm analysis was a mathematical discipline, not merely an engineering heuristic. His work on sorting and searching, on data structures, on random number generation, established the vocabulary and methods that the entire field still uses. The full scope of Knuth’s influence is traced in Donald Knuth and the Art of Programming.

Correctness and Termination

Knowing that an algorithm runs efficiently is useful only if it runs correctly. The discipline of program verification — proving, with mathematical rigor, that an algorithm does what it claims to do — emerged in the 1960s and 1970s.

Robert Floyd, in 1967, introduced the method of assertional verification: annotate each step of an algorithm with a loop invariant, a logical condition that holds before and after each iteration, and prove that the invariant is maintained. If the invariant at termination implies the desired result, and if the algorithm terminates, then it is correct.

C.A.R. Hoare formalized this approach into what became Hoare logic (1969): a calculus of preconditions and postconditions, in which the statement {P} S {Q} asserts that if condition P holds before executing statement S, then condition Q holds afterward. A complete proof of an algorithm’s correctness consists of a chain of such triples from input to output.

Edsger Dijkstra pushed further, arguing that programming was not engineering but mathematics, and that programmers should construct proofs of correctness alongside — or even before — writing code. His method of weakest preconditions, developed in the 1970s, allowed reasoning backward from desired outputs to required inputs. For Dijkstra, a program without a proof was not a finished product; it was a conjecture.

Info

Formal verification remains the exception rather than the rule in commercial software development. The gap between Dijkstra’s ideal and everyday practice is vast: most production systems contain millions of lines of code that have never been formally verified and never will be. The discipline survives in safety-critical domains — aircraft control systems, medical devices, cryptographic protocols — where the cost of failure exceeds the cost of proof.

The question of termination, Turing had shown, was in general undecidable. For any specific algorithm, however, termination can often be proved by finding a decreasing measure: a quantity that is always positive and strictly decreases with each iteration. Euclid’s algorithm terminates because the remainder strictly decreases at each step. Demonstrating termination for more complex algorithms — especially those involving recursion or concurrent processes — can require significant ingenuity.

The Algorithm as Cultural Object

In the twenty-first century, the algorithm escaped the boundaries of mathematics and engineering and entered general culture. The word, once confined to textbooks, began appearing in newspaper headlines, legal filings, and political speeches.

PageRank, Google’s algorithm for estimating the authority of web pages by counting and weighting links, transformed the economics of information by making some pages systematically visible and others invisible. Facebook’s feed-ranking algorithm, designed to maximize engagement, was implicated in the spread of misinformation and the amplification of political polarization. Credit-scoring algorithms, opaque to those they evaluated, determined who could borrow money, rent apartments, or secure employment. Recidivism-prediction algorithms, used in criminal sentencing, were found to exhibit racial bias — not because their designers intended discrimination, but because the historical data on which they were trained encoded historical inequalities.

The cultural tension this produced was novel and unresolved. Algorithms, in their mathematical sense, are maximally transparent: they are finite, explicit, determinable. Given the code and the inputs, any competent programmer can trace exactly what an algorithm will do. But when algorithms are deployed at scale on human data, trained on human history, and embedded in human institutions, their effects become social, political, and contested in ways that no formal specification can capture.

The European Union’s AI Act, adopted in 2024, represents the first major legal framework that treats algorithms — particularly those used in high-stakes decisions about individuals — as regulated objects subject to transparency requirements, impact assessments, and in some cases outright prohibition. The law grapples, not always successfully, with the gap between the mathematical precision of an algorithm as a defined procedure and the social complexity of its real-world effects.

The vocabulary of algorithm has also infected domains far removed from computation. Biologists speak of the genetic algorithm of evolution. Economists model markets as optimization algorithms. Cognitive scientists describe human decision-making in algorithmic terms. The word has become a general-purpose metaphor for any systematic process producing a result — a usage that would have puzzled Euclid and alarmed Turing.

What Makes a Good Algorithm

Behind the cultural noise, the mathematical question of what constitutes a good algorithm remains active and surprisingly unresolved.

Correctness is necessary: an algorithm that produces wrong answers is not solving the problem, whatever its efficiency. Efficiency matters: an algorithm that is provably correct but requires more steps than atoms in the universe is theoretically satisfying and practically useless. Knuth added a third criterion that is less often discussed: elegance. A beautiful algorithm is short, transparent, and surprising — it reveals structure that brute force obscures. Euclid’s algorithm is beautiful. Bubble sort is not.

The discovery that different algorithms for the same problem can have radically different efficiency has motivated decades of research into lower bounds — proofs that no algorithm, however clever, can solve a given problem faster than some minimum. Proving that sorting n elements requires at least O(n log n) comparisons in the worst case established that merge sort and quicksort are, in a precise sense, optimal for comparison-based sorting. But lower bounds remain hard to prove, and for many fundamental problems — including the P versus NP question, which asks whether problems whose solutions are easily checkable can also be solved efficiently — no proof exists.

The search for better algorithms for basic problems continues. Matrix multiplication, fundamental to machine learning and scientific computing, was long assumed to require O(n³) operations; Volker Strassen’s discovery in 1969 of an O(n^2.81) algorithm was a shock, and researchers have steadily improved the exponent since. Integer multiplication, primality testing, graph search: for each, algorithms discovered decades ago have been improved, and for each, the question of the optimal algorithm remains open.

This is perhaps the most humanly important lesson in the history of the algorithm as a concept: it is not a solved problem. The object was defined with precision in 1936, analyzed with rigor since the 1960s, deployed at planetary scale since the 1990s — and yet the question of how to find, analyze, and evaluate algorithms for fundamental problems remains one of the deepest and most active areas of mathematics and computer science. Euclid’s procedure, recorded on papyrus more than two thousand years ago, is still the best known algorithm for its problem. The history of the concept is, in a sense, still being written.