Set-Theoretic Formalizations of Computational Algorithms, Computable Functions, and General-Purpose Computers

摘要

The paper is concerned with formalization of the notion of computational algorithm, determination of the class of functions computable by such algorithms, and development of a formal definition of 'general-purpose computer'. Functional systems, consisting of a set and a function in that set, were introduced and two definitions according to which they may be considered to compute functions were proposed. It was demonstrated that under the first, and more elementary, definition of the function computed by functional systems, a vanishingly small fraction of all functions, only the class of stable functions, is computable. The existence of single functional systems which can compute every function in a given set was demonstrated.