ON PRIMITIVE RECURSIVE PERMUTATIONS AND THEIR INVERSES,
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1969
- Accession Number
- AD0684607
Entities
People
- Frank B. Cannonito
- Mark Finkelstein
Organizations
- University of California, Irvine