Accession Number:

AD0684607

Title:

ON PRIMITIVE RECURSIVE PERMUTATIONS AND THEIR INVERSES,

Descriptive Note:

Corporate Author:

CALIFORNIA UNIV IRVINE DEPT OF MATHEMATICS

Personal Author(s):

Report Date:

1969-01-01

Pagination or Media Count:

12.0

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 AB superscript -1C, where A, B, C are primitive recursive and B is a permutation. This report presents a sharper version of Robinsons result, that is, every singulary recursive f is of the form f AB superscript -1C for fixed A,C where A,B,C are elementary functions and B is a permutation. The proof employs meta-mathematical methods. Author

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE