PART II. INFINITE AUTOMATA. COMPUTABILITY — Ch. 6. Recursive Functions
We shall present below another formulation of effective computability in the form of the notion of a recursive function. It will be shown that this theory defines the same class of procedures as Turing machines.
The notions to be presented appeared independently of the work of Turing and Church. Later, however, it was found that these notions lead to the same class of effective procedures, which constitutes an additional argument for demonstrating the validity of Turing’s thesis.
The study of recursive functions, by means of which we shall give a new formulation of computability, will also lead to several observations of interest for programs intended for computers.
