The Old Babylonian period (c. 1900–1600 BCE) produced the earliest known explicit algorithms, preserved on clay tablets that encode step‑by‑step procedures for arithmetic and geometry. These texts, studied by historians such as Otto Neugebauer and Jens Høyrup, used a sexagesimal (base‑60) place‑value notation and a conventionalized instructional language to solve problems involving multiplication, division, square roots, quadratic equations, areas, volumes, and Pythagorean triples. Procedure texts like YBC 4663 and BM 85194 describe how to solve word problems through ordered sequences of operations, while table‑texts such as AO 6456 list precomputed values like reciprocals and squares. The tablet YBC 7289 gives a sexagesimal approximation of √2, and Plimpton 322 lists Pythagorean triples. These tablets show that Babylonian scribes did not merely perform ad hoc calculations but encoded general methods for entire classes of problems, focusing on numerical answers rather than proofs. The corpus includes hundreds of mathematical tablets from sites like Sippar and Larsa, now held in collections such as the Yale Babylonian Collection and the British Museum. This tradition represents an early yet sophisticated form of algorithmic reasoning, where procedures are embedded in worked examples that implicitly define general methods.
The Euclidean algorithm, formalized in Euclid's *Elements*, stands as the first documented procedure for solving a mathematical problem through a finite, repeatable sequence of steps. It computes the greatest common divisor of two integers by exploiting the invariant that the gcd remains unchanged when the larger number is replaced by the remainder of their division. This step-by-step process—repeatedly applying the operation of taking remainders until zero is reached—turns a numerical task into a rule-governed procedure with a clear starting state, a termination condition, and a guaranteed output. The algorithm is rooted in the observation that for any integers a and b with a > b, the pair (a, b) can be reduced to (b, a mod b) without altering the sought-after gcd; each step shrinks the numbers, ensuring progress toward the trivial case of a zero remainder. This method embodies the core modern notion of an algorithm as a precisely defined, deterministic, and terminating process. While absent of the modern word “algorithm,” Euclid’s contribution established a foundational template for algorithmic thinking: that a general problem can be solved by a finite, repeatable procedure that preserves an invariant while reducing complexity. The Euclidean algorithm’s longevity across millennia underscores its role as an early model of algorithmic reasoning, from ancient number theory to contemporary computer science.
Al-Khwarizmi’s 9th-century book *al-Kitāb al-mukhtaṣar fī ḥisāb al-jabr waʾl-muqābala* is the direct origin of the modern word *algebra*, as its Latin translations carried the title element *al-jabr* into European mathematical vocabulary. More than a naming coincidence, the work established systematic problem-solving in algebra by presenting repeatable rules and demonstrations for solving linear and quadratic equations, rather than isolated tricks for individual cases. His method was systematic in two specific ways: he organized equations into standard types—giving procedures for six equation forms—and emphasized *restoration* (*al-jabr*) and *balancing* (*al-muqābala*), meaning the transposition and cancellation of terms to simplify equations into solvable forms. The connection to the term *algorithm* is indirect but important. Al-Khwarizmi’s Latinized name, *Algoritmi*, became the medieval source of the word *algorithm*, which originally referred to arithmetic methods associated with Hindu-Arabic numerals rather than to algebra itself. In historical usage, that term came to mean a step-by-step rule-based procedure, and Al-Khwarizmi’s algebraic treatise exemplified exactly that kind of ordered procedure: a fixed sequence of operations for solving classes of problems. So, in short, *Al-Jabr* did not literally coin the word “algorithm,” but it helped establish the broader mathematical culture of formal, repeatable, rule-governed methods that the term later came to represent.
Medieval European calculation evolved through two intertwined traditions: the board-abacus used by clerics and scholars, and the algorism-abbaco tradition that taught written calculation with Hindu-Arabic numerals for commercial arithmetic. In the late 10th and 11th centuries, scholars like Gerbert of Aurillac revived the abacus in Latin Europe, using counters on a marked board with connections to Hindu-Arabic numeral forms rather than older Roman reckoning. By the 12th and 13th centuries, textbook authors shifted from teaching only the abacus to teaching algorism, the new method of calculation using Hindu-Arabic numerals and written procedures. A Cambridge study of medieval arithmetic notes that manuals at the start of this period taught the abacus, while by the end they described algorism; by the 14th century, students were often taught both theory and practice in arithmetic collections. Fibonacci’s Liber Abaci (1202) was a major turning point because it systematized Hindu-Arabic numerals and practical arithmetic for real-world problems, becoming foundational for the Italian abbaco-school tradition where private teachers trained merchants and artisans in commercial calculation. The abbaco tradition was not purely academic but a practical pedagogy for mercantile life, embedded in a broader culture shared with scholastic knowledge. Medieval calculation methods thus developed along three lines: scholarly abacus use with counters on a ruled board, algorism using written procedures with Hindu-Arabic numerals, and abbaco schools offering merchant-oriented instruction in numeration, multiplication, division, and the rule of three.
Leibniz’s universal characteristic was a planned formal symbol system meant to represent concepts with “real characters” and to make reasoning itself proceed by a calculus analogous to arithmetic and algebra. His mechanical calculator—the stepped-drum machine he developed in the 1670s—was designed to automate arithmetic operations, especially multiplication and division, embodying his conviction that calculation could be mechanized. Leibniz’s broader vision joined these two projects: a symbolic language for thought and a machine for computation. In the universal characteristic, complex ideas would be built from primitive concepts by combining symbols according to strict rules, so that disputes could be settled by computation rather than by extended argument. This is why Leibniz is often described as aiming to turn reasoning into something like formal calculation. That vision prefigured modern algorithmic logic in several ways. First, it treated reasoning as rule-governed symbol manipulation, which anticipates formal logic and computation. Second, it separated the form of inference from the content of the concepts, an idea central to later symbolic logic and computer science. Third, Leibniz explicitly imagined that errors in reasoning would become visible as errors in symbol combination, much like mistakes in arithmetic—a direct anticipation of algorithmic verification and automated proof checking. A careful caveat: Leibniz did not complete a full universal language or a modern logic system, and his mechanical calculator was limited compared with later computers. But his core insight—that valid reasoning could be represented, manipulated, and checked by formal symbols and procedures—was a major precursor to modern formal logic and algorithmic computation.
Ada Lovelace’s 1843 translation of Luigi Menabrea’s account of Charles Babbage’s Analytical Engine, supplemented by her own Notes, produced the first published algorithm intended for execution by a machine. In Note G, she laid out step-by-step instructions for calculating the Bernoulli numbers, an elemental sequence of operations that constitutes an algorithm. Thomas Misa, in a 2023 arXiv paper, affirms that Lovelace created this sequence and that ample evidence from her correspondence with Babbage and mathematician Augustus De Morgan establishes her mathematical sophistication and her collaborative role in the 1843 Sketch. Misa also clarifies that credit between Lovelace and Babbage is not a zero-sum game; both made important contributions. While some sources note that Babbage had earlier, unpublished programs, Lovelace’s work is widely regarded as the first published algorithm for a computing machine, demonstrating that a machine could follow a symbolic procedure beyond fixed arithmetic. This helped establish the concept of programmable computation. The historical nuance is that Lovelace’s algorithm is the first published, not necessarily the first ever written. Misa’s analysis corrects an unduly negative scholarly view of Lovelace and underscores that her algorithm for the Bernoulli numbers remains a foundational artifact in computing history.
Hilbert and Ackermann’s 1928 Entscheidungsproblem sought a finite, effective procedure to decide the universal validity of any logical formula, but at the time no precise definition of “algorithm” existed. Gödel’s 1931 incompleteness theorems then demonstrated that any sufficiently expressive, consistent formal system cannot prove every truth expressible in it, and that undecidable statements necessarily exist, sharply limiting the possibility of a complete algorithmic proof procedure for mathematics. Church, in the 1930s, developed the lambda calculus as a formal system for defining and computing functions, showing that the effectively calculable functions captured by his system aligned with recursive definability, providing one of the first rigorous formalizations of computation. The later identification of equivalence among lambda-definability, recursive functions, and Turing-machine computability gave a precise mathematical notion of algorithm: a function is computable exactly when it can be carried out by one of these equivalent formal models. Thus Hilbert posed the question, Gödel exposed inherent limits of formal axiomatization, and Church’s lambda calculus helped supply the formal notion of effective procedure that became a central basis for the modern definition of an algorithm.
Alan Turing’s 1936 paper defined computability by modeling an algorithm as a finite mechanical procedure carried out by an abstract machine that reads and writes symbols on an unbounded tape according to a fixed rule table, thereby characterizing exactly which real numbers can be produced by finite means. The core idea was that a Turing machine has a finite set of states, an unbounded tape divided into cells, a read/write head scanning one cell at a time, and a finite table of instructions determining every step of its behavior. This made the model universal in the sense that any effectively calculable procedure could be represented by such a machine, so long as it could be reduced to discrete symbol manipulations. Turing’s paper used this model to define computable numbers as numbers whose infinite decimal expansions can be printed out by such a machine, linking the formal machine model to the broader notion of an algorithm. P. M. B. Vitanyi describes the Turing Machine, listing its many influences on the theory of computation and complexity. Joel David Hamkins extends ordinary Turing machines into transfinite ordinal time, providing a natural model of infinitary computability and supertask algorithms. Bruce Edmonds and Carlos Gershenson argue that learning or adaptation is fundamentally different from computation, though it involves processes that can be seen as computations, using the bounded halting problem to illustrate problems that are not effectively designable but are learnable. T. Yokoyama constructs universal reversible Turing machines with fewer states or symbols than previous examples, showing that no RTM with at most two states is universal.
The von Neumann architecture made algorithm execution practical by storing both instructions and data in the same main memory, allowing a CPU to load a program and run it without rewiring hardware for each task. This stored-program concept turned computers into general-purpose machines: the processor repeatedly fetches, decodes, and executes instructions from memory in sequence, enabling the same hardware to run many different algorithms simply by changing the stored program. Programs became data-like objects in memory, so a computer could load, save, replace, and reuse programs electronically rather than being manually reconfigured. Execution became systematic and automatic through the fetch-decode-execute cycle, which implements step-by-step algorithm execution. However, this paradigm created what John Backus called the "von Neumann vicious circle": because programming languages are high-level abstract copies of von Neumann architectures, non-von Neumann computer architectures cannot develop due to the lack of effective non-von Neumann languages, and new languages cannot be created without conceptual foundations for such architectures. This constitutes the current paradigm in computer science, where computations on higher order objects are done only symbolically through term rewriting. Research suggests that higher order computations in the human brain, based on functional reconfigurations of neural circuits, may point toward a non-von Neumann computer architecture that breaks this paradigm.
Computational complexity theory fundamentally reframed the study of algorithms by shifting focus from mere computability to the resources required, especially time and space, making intractability a rigorous discipline. In the early 1960s, Hartmanis and Stearns formalized definitions of time and space complexity for Turing machines, establishing a system to compare algorithms by resource usage rather than just correctness. Stanford’s overview confirms that complexity theory centers on decision problems and classifies computational difficulty with mathematical precision. This changed algorithms in three major ways: from evaluating only correctness to also assessing feasibility, from isolated problems to broad resource-bounded classes enabling comparisons across problem families, and from a collection of practical tricks to a structural theory that can prove intrinsic hardness for certain problems. The later development of P vs. NP sharpened this by asking whether problems with efficiently verifiable solutions also have efficient solutions, turning algorithm design into a study of fundamental limits. The emergence of NP-completeness, which Cook formalized and Karp demonstrated applied to classic problems like traveling salesperson, showed that diverse problems share the same kind of hardness. A survey calls NP-completeness the most significant development in computational complexity. This reoriented research toward finding efficient algorithms, proving hardness, and developing approximation methods where exact solutions are unlikely.
Install this pack and your MIND begins smart — then every answer is grounded in your own knowledge graph.
Try MIND free →