Accession Number : AD0684607

Title :   ON PRIMITIVE RECURSIVE PERMUTATIONS AND THEIR INVERSES,

Corporate Author : CALIFORNIA UNIV IRVINE DEPT OF MATHEMATICS

Personal Author(s) : Cannonito,Frank B. ; Finkelstein,Mark

Report Date : JAN 1969

Pagination or Media Count : 12

Abstract : It is known that there is a primitive recursive permutation of the nonnegative integers whose inverse is recursive but not primitive recursive. Robinson showed that every singulary recursive function f is representable as f = A(B superscript -1)C, where A, B, C are primitive recursive and B is a permutation. This report presents a sharper version of Robinson's result, that is, every singulary recursive f is of the form f = A(B superscript -1)C for fixed A,C where A,B,C are elementary functions and B is a permutation. The proof employs meta-mathematical methods. (Author)

Descriptors :   (*MATHEMATICAL LOGIC, RECURSIVE FUNCTIONS), (*RECURSIVE FUNCTIONS, PERMUTATIONS), GROUPS(MATHEMATICS), THEOREMS

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE