Accession Number : AD0605964

Title :   SET-THEORETIC FORMALIZATIONS OF COMPUTATIONAL ALGORITHMS, COMPUTABLE FUNCTIONS, AND GENERAL-PURPOSE COMPUTERS,

Corporate Author : RAND CORP SANTA MONICA CALIF

Personal Author(s) : Levien,Roger E.

Report Date : APR 1962

Pagination or Media Count : 1

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.

Descriptors :   (*COMPUTERS, OPERATION), FUNCTIONS(MATHEMATICS), SET THEORY, THEOREMS, MATHEMATICAL ANALYSIS

Distribution Statement : APPROVED FOR PUBLIC RELEASE