The theory of recursive functions, approaching its centennial
Stephen C. Kleene · Bulletin of the American Mathematical Society · 1981
An algorithm is a procedure, given by a finite set of instructions, to serve as follows in relation to a given infinite class of questions, (a) If we select any question from the class, the instructions will tell us how to perform a step, (b) After any step, if we do not receive the answer then, the instructions together with the existing situation will tell us what step to take next, (c) The instructions will enable us to recognize when a situation is reached in which the answer is before us, and to read it off then; and this will eventually happen if the question has an answer.In "steps" and "situations'*, what are we handling?Since there must be no ambiguity, surely some kind of regular complexes of occurrences of symbols from a given finite list.Such complexes can be coded by positive integers.Consider specifically an algorithm for computing a functional for which we already know how to get the values, such that, in the situation represented by (0; ft, b), x(6; ft, £) *• 0 if the answer is not before us, and otherwise x(0; % b) - 0, we have a definition of 52, p. 348]; and «0; 3Q « <J<0; % 0).Thence it is argued that the first recursion theorem, in a proper setting, enables all functionals