## ::Algorithm

### ::concepts

{{#invoke:Hatnote|hatnote}}
{{ safesubst:#invoke:Unsubst||$N=Use mdy dates |date=__DATE__ |$B=
}}

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ödel–Herbrand–Kleene 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 |

<< | >> |

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=
}}

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ödel–Herbrand–Kleene 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 |

<< | >> |