What an algorithm is
An algorithm is a finite, well-defined sequence of steps for solving a problem or carrying out a task. Long division is an algorithm, and so is a recipe that is precise enough to follow without judgment. A computer program expresses algorithms in a form a machine can execute, but the idea predates machines by thousands of years. Understanding that history helps separate two things that are often confused: the method, which is an idea, and the program, which is one way of writing it down.
Ancient procedures
Some of the oldest surviving mathematical texts consist largely of procedures. Clay tablets from ancient Mesopotamia include worked examples that describe how to solve certain types of problems, usually by stepping through a calculation with particular numbers. Egyptian papyri and Chinese mathematical texts contain similar step-by-step methods.
One of the most famous early examples is described in Euclid’s Elements, written around 300 BCE: a method for finding the greatest common divisor of two numbers by repeatedly replacing the larger number with the remainder after division. The method is still taught and is still used in computing, which makes it a frequently cited example of an algorithm that is more than two thousand years old. Another classic is the sieve attributed to Eratosthenes for finding prime numbers by crossing out multiples, though the details of its early history are less certain.
The name comes from a person
The word “algorithm” is generally traced to Muhammad ibn Musa al-Khwarizmi, a scholar working in Baghdad in the ninth century. His book on calculation with Hindu-Arabic numerals was translated into Latin in medieval Europe, and the Latinized form of his name came to be associated with the decimal calculating methods it described. His other major work gave us the word “algebra.” For centuries “algorism” meant arithmetic with these numerals, and the modern spelling and meaning, covering any systematic procedure, settled later.
Machines and mechanical procedure
As calculation became mechanized, algorithms became something that could be built into hardware. Mechanical calculators of the 1600s and later could perform addition and, in some cases, multiplication by following fixed internal mechanisms. Charles Babbage’s Difference Engine embodied one particular method, the method of finite differences, in gears. His proposed Analytical Engine went further, since its punched cards would have allowed the sequence of operations to be changed without rebuilding the machine.
Ada Lovelace’s notes of 1843 on that engine include a table of operations for computing a series of Bernoulli numbers, which many historians regard as an early published example of an algorithm written for a machine. How much of it was her own work and how much came from discussion with Babbage is debated, so it is safest to describe it as a collaborative result.
Making “algorithm” precise
For most of history, “an effective procedure” was an intuitive notion. In the early 1930s, mathematicians who were investigating the foundations of logic wanted a precise definition, which would let them ask whether certain problems could be solved by any procedure at all. In 1936, Alan Turing described an abstract machine, now called a Turing machine, that reads and writes symbols on a tape according to a table of rules. Around the same time, Alonzo Church proposed a different formal system, and the two were shown to be equivalent in power. Together they supported the widely held thesis that these formal models capture what we mean by a computable procedure.
A notable consequence was the discovery that some well-defined questions cannot be answered by any algorithm. That result showed that there are limits on what computation can do, not just limits imposed by speed or memory.
Algorithms meet electronic computers
In the 1940s, practical electronic machines created demand for programs. Early machines such as the ENIAC were set up for particular calculations, at first by rewiring and setting switches, and the people doing that work were often women mathematicians who worked out how to turn a calculation into a sequence of machine operations. Planning a problem for such a machine required breaking it down into elementary steps, which is what algorithm design is about.
The arrival of the stored-program concept, in which instructions are held in the same memory as data, made programs far easier to change. Within a few years, small experimental machines in Britain were running short programs held in memory. Among the earliest was a program on the Manchester machine in 1948 that searched for a factor of a number, and soon after that, machines such as EDSAC in Cambridge were used for tables and scientific calculations. John von Neumann is also known to have written a sorting program in the mid-1940s that used a merge approach still taught today.
Studying algorithms as a field
As programs spread, people began studying algorithms in their own right. Early software was written in machine code, and improved languages and tools, including compilers and interpreters, made it practical to express algorithms at a higher level. Questions that had barely been asked before began to matter: how many steps does a method need as the input grows, and is a faster method possible? Sorting and searching methods became classic topics. In the 1960s, Donald Knuth began publishing a multi-volume work on the subject that helped establish analysis of algorithms as a part of computer science.
Why the history matters
Today the word algorithm is used loosely in news stories, often as a stand-in for any automated decision system. The history is a reminder of the original meaning: a precise recipe for getting from input to output. Some modern systems follow fixed procedures that a person can read and check. Others, particularly those that learn from data, are harder to describe step by step. In both cases, the underlying idea is the same one that Euclid, al-Khwarizmi and the early machine programmers worked with, namely that careful, explicit steps can be followed by someone, or something, that does not need to understand the problem.