Accession Number : AD0736944

Title :   Augmented Loop Languages and Classes of Computable Functions,

Corporate Author : INDIANA UNIV BLOOMINGTON DEPT OF COMPUTER SCIENCE

Personal Author(s) : Machtey,Michael

Report Date : DEC 1971

Pagination or Media Count : 44

Abstract : A classification of all the computable functions is given in terms of subrecursive programming languages. These classes are those which arise from the relation 'primitive recursive in.' By distinguishing between honest and dishonest classes the classification is related to the computational complexity of the functions classified, and the classification has a wide degree of measure invariance. The structure of the honest and dishonest classes under inclusion is explored. It is shown that any countable partial ordering can be embedded in the dishonest classes, and that the dishonest classes are dense in the honest classes. Every honest class is minimal over some dishonest class, but there are dishonest classes with no honest class minimal over them. (Author)

Descriptors :   (*MATHEMATICAL LOGIC, RECURSIVE FUNCTIONS), COMPUTER PROGRAMMING, THEOREMS

Subject Categories : Theoretical Mathematics
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE