Algorithm

An algorithm is a finite sequence of mathematically rigorous instructions. These instructions are designed to solve a specific class of problems or to perform a computation. To function, an algorithm requires an initial state and initial input. These inputs are the quantities provided to the process before it begins. As the instructions are executed, the algorithm moves through a series of well-defined successive states. Eventually, it produces an output, which is a quantity that has a specified relation to the inputs. A critical requirement is that an algorithm must terminate in a finite number of steps. If a procedure lacks this finiteness, it is instead called a computational method.

Algorithms operate through structured logic and can vary in their complexity. Most algorithms are deterministic, meaning they follow a predictable path. However, some are known as randomized algorithms because they incorporate random input. Advanced algorithms can also use conditionals to divert execution through different routes. This process is known as automated decision-making. Some systems even use automated reasoning to deduce valid inferences. It is important to distinguish algorithms from heuristics. A heuristic is an approach used to solve problems without guaranteeing a correct or optimal result. For example, social media recommender systems often rely on heuristics rather than true algorithms because there is no single correct recommendation.

Humanity has used step-by-step procedures for millennia. The earliest evidence of algorithms is found in ancient Mesopotamian mathematics. A Sumerian clay tablet from Shuruppak describes an early division algorithm. During the Hammurabi dynasty, Babylonian clay tablets used algorithms for computing formulas and for astronomy. These procedures helped track significant astronomical events. Ancient Egyptian mathematics also included algorithms, such as those found in the Rhind Mathematical Papyrus. Other ancient traditions include Greek mathematics, Indian mathematics, and Chinese mathematics. In the 9th century, the Arab mathematician Al-Kindi developed the first cryptographic algorithm. He used frequency analysis to perform cryptanalysis, which is the process of codebreaking.

The word "algorithm" has a deep etymological history. It is derived from the name of the Persian polymath Muḥammad ibn Mūsā al-Khwārizmī. Around 825 AD, he wrote books on Indian computation and arithmetic. In the early 12th century, Latin translations of his work appeared in Europe. These texts included terms like "algorismi," which was a Latinization of his name. In the 15th century, the word was altered to "algorithmus" due to the influence of the Greek word "arithmos," meaning number. By 1596, the English form "algorithm" was used by Thomas Hood. Previously, the English word "algorism" referred specifically to the use of place-value notation in calculations.

Technological progress has transformed how algorithms are executed. The invention of the weight-driven clock in Europe led to mechanical automata. In the mid-19th century, Charles Babbage and Ada Lovelace worked on the difference and analytical engines. Lovelace designed the first algorithm intended for processing on a computer. Because of this, she is often called history's first programmer. Later, the development of electromechanical relays and telephone-switching technologies aided computer growth. In 1937, George Stibitz constructed a binary adding device while working at Bell Laboratories. This was a significant step away from the burdensome use of mechanical gear-based calculators.

In the 20th century, mathematicians began to formalize the concept of the algorithm. In 1928, attempts were made to solve the Entscheidungsproblem, or decision problem, posed by David Hilbert. This led to definitions of "effective calculability" or "effective methods." Significant formalizations included the recursive functions of Gödel, Herbrand, and Kleene. Other vital contributions came from Alonzo Church's lambda calculus and Alan Turing's Turing machines. Turing machines provide a way to represent algorithms through machine tables, flowcharts, or assembly code. These descriptions can be high-level, implementation-based, or highly detailed formal descriptions.

Today, algorithms are essential to modern digital life and scientific advancement. They power social media apps like Instagram and YouTube by analyzing user interaction. In the field of computing, quantum algorithms are used to solve problems with much higher speeds. This is especially relevant to security, as NIST updated post-quantum encryption standards in 2024. These new algorithms are designed to enhance defenses against potential attacks from quantum computing. Algorithms can be expressed in many ways, including natural language, pseudocode, or programming languages. While natural language is often too ambiguous for technical work, programming languages allow computers to execute these complex instructions directly.