
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 metamathematical methods. (Author)
Descriptors : (*MATHEMATICAL LOGIC, RECURSIVE FUNCTIONS), (*RECURSIVE FUNCTIONS, PERMUTATIONS), GROUPS(MATHEMATICS), THEOREMS
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE