SET-THEORETIC FORMALIZATIONS OF COMPUTATIONAL ALGORITHMS, COMPUTABLE FUNCTIONS, AND GENERAL-PURPOSE COMPUTERS,
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1962
- Accession Number
- AD0605964
Entities
People
- Roger E. Levien
Organizations
- RAND Corporation