## ::Algorithm

### ::concepts

First::title    Turing::number    Machine::problem    Which::computer    Journal::kleene    Davis::example

{{#invoke:Hatnote|hatnote}} {{ safesubst:#invoke:Unsubst||\$N=Use mdy dates |date=__DATE__ |\$B= }} Flow chart of an algorithm (Euclid's algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≥ A yields "yes" (or true) (more accurately the number b in location B is greater than or equal to the number a in location A) THEN, the algorithm specifies B ← B − A (meaning the number ba replaces the old b). Similarly, IF A > B, THEN A ← A − B. The process terminates when (the contents of) B is 0, yielding the g.c.d. in A. (Algorithm derived from Scott 2009:13; symbols and drawing style from Tausworthe 1977).

In mathematics and computer science, an algorithm ({{#invoke:IPAc-en|main}} AL-gə-ri-dhəm) is a self-contained step-by-step set of operations to be performed. Algorithms exist that perform calculation, data processing, and automated reasoning.

An algorithm is an effective method that can be expressed within a finite amount of space and time<ref>"Any classical mathematical algorithm, for example, can be described in a finite number of English words" (Rogers 1987:2).</ref> and in a well-defined formal language<ref>Well defined with respect to the agent that executes the algorithm: "There is a computing agent, usually human, which can react to the instructions and carry out the computations" (Rogers 1987:2).</ref> for calculating a function.<ref>"an algorithm is a procedure for computing a function (with respect to some chosen notation for integers) ... this limitation (to numerical functions) results in no loss of generality", (Rogers 1987:1).</ref> Starting from an initial state and initial input (perhaps empty),<ref>"An algorithm has zero or more inputs, i.e., quantities which are given to it initially before the algorithm begins" (Knuth 1973:5).</ref> the instructions describe a computation that, when executed, proceeds through a finite<ref>"A procedure which has all the characteristics of an algorithm except that it possibly lacks finiteness may be called a 'computational method'" (Knuth 1973:5).</ref> number of well-defined successive states, eventually producing "output"<ref>"An algorithm has one or more outputs, i.e. quantities which have a specified relation to the inputs" (Knuth 1973:5).</ref> and terminating at a final ending state. The transition from one state to the next is not necessarily deterministic; some algorithms, known as randomized algorithms, incorporate random input.<ref>Whether or not a process with random interior processes (not including the input) is an algorithm is debatable. Rogers opines that: "a computation is carried out in a discrete stepwise fashion, without use of continuous methods or analogue devices . . . carried forward deterministically, without resort to random methods or devices, e.g., dice" Rogers 1987:2.</ref>

The concept of algorithm has existed for centuries, however a partial formalization of what would become the modern algorithm began with attempts to solve the Entscheidungsproblem (the "decision problem") posed by David Hilbert in 1928. Subsequent formalizations were framed as attempts to define "effective calculability"<ref>Kleene 1943 in Davis 1965:274</ref> or "effective method";<ref>Rosser 1939 in Davis 1965:225</ref> those formalizations included the GödelHerbrandKleene recursive functions of 1930, 1934 and 1935, Alonzo Church's lambda calculus of 1936, Emil Post's "Formulation 1" of 1936, and Alan Turing's Turing machines of 1936–7 and 1939. Giving a formal definition of algorithms, corresponding to the intuitive notion, remains a challenging problem.<ref>{{#invoke:citation/CS1|citation |CitationClass=book }}</ref>

Algorithm sections
Intro   Word origin    Informal definition    Formalization    Implementation    Computer algorithms    Examples    Algorithmic analysis    Classification    Continuous algorithms    Legal issues    Etymology    History: Development of the notion of \"algorithm\"    See also    Notes    References    Further reading    External links

 PREVIOUS: Intro NEXT: Word origin << >>