Editing Theoretical computer science (section)

===Algorithms===
{{main|Algorithm}}
An [[algorithm]] is a step-by-step procedure for calculations. Algorithms are used for [[calculation]], [[data processing]], and [[automated reasoning]].

An algorithm is an [[effective method]] expressed as a [[wikt:finite|finite]] list<ref>"Any classical mathematical algorithm, for example, can be described in a finite number of English words". {{cite book|title=Theory of Recursive Functions and Effective Computability|year=1967|publisher=McGraw-Hill|first=Hartley Jr.|last=Rogers|author-link=Hartley Rogers Jr.}} Page 2.</ref> of well-defined instructions<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" {{harv|Rogers|1967|p=2}}.</ref> for calculating a [[Function (mathematics)|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", {{harv|Rogers|1967|p=1}}.</ref>  Starting from an initial state and initial input (perhaps [[null string|empty]]),<ref>"An algorithm has [[zero]] or more inputs, i.e., [[quantity|quantities]] which are given to it initially before the algorithm begins" (Knuth 1973:5).</ref> the instructions describe a [[computation]] that, when [[Execution (computing)|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 the use of continuous methods or analog devices . . . carried forward deterministically, without resort to random methods or devices, e.g., dice" {{harv|Rogers|1967|p=2}}.</ref>