Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2025-01-03T17:27:58.153Z Has data issue: false hasContentIssue false
  • English
  • Français

On primitive recursive permutations and their inverses1

Published online by Cambridge University Press:  12 March 2014

Frank B. Cannonito  and
Mark Finkelstein
Frank B. Cannonito
Affiliation:
University of California, Irvine
Mark Finkelstein
Affiliation:
University of California, Irvine
Get access Rights & Permissions [Opens in a new window]

Extract

It has been known for some time that there is a primitive recursive permutation of the nonnegative integers whose inverse is recursive but not primitive recursive. For example one has this result apparently for the first time in Kuznecov [1] and implicitly in Kent [2] or J. Robinson [3], who shows that every singularly recursive function ƒ is representable as

where A, B, C are primitive recursive and B is a permutation.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 34 , Issue 4 , February 1970 , pp. 634 - 638
Copyright
Copyright © Association for Symbolic Logic 1970

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

1

The first author was supported by Grant No. AF-AFOSR 1321-67 and the second by NSF GP-7500.

References

[1] Kuznecov, A. V., On primitive recursive functions of large oscillation, Doklady Akademii Nauk SSSR 71 (1950), pp. 233–236 (Russian).Google Scholar
[2] Kent, C. F., Algebraic structure of some groups of recursive permutations, Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, Mass., 1960.Google Scholar
[3] Robinson, J., General recursive functions, Proceedings of the American Mathematical Society, vol. 1 (1950), pp. 703–718.CrossRefGoogle Scholar
[4] Cannonito, F. B., Hierarchies of computable groups and the word problem, this Journal , vol. 31 (1966), pp. 376–392.Google Scholar
[5] Rogers, Hartley Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[6] Uspenskií, V. A., Lectures on computable functions, Fizmatgiz, Moscow, 1960; French transl., Actualités Scientifiques et Industrielles, no. 1317, Hermann, Paris, 1966; English transl., Hindustan, Delhi (to appear).Google Scholar
[7] Kleene, S. C., Introduction to metamathematics, Van Nostrand, Princeton, N.J., 1952.Google Scholar
[8] Kleene, S. C., Mathematical logic, Wiley, New York, 1967.Google Scholar
[9] Davis, M., Computability and unsolvability, McGraw-Hill, New York, 1957.Google Scholar
[10] Hermes, H., Aufzählbarkeit, Entscheidbarkeit, Berechenbarkeit, Springer-Verlag, Berlin, 1961.CrossRefGoogle Scholar
[11] Ritchie, R. W., Classes of predictably computable functions, Transactions of the American Mathematical Society, vol. 106 (1963), pp. 139–173.CrossRefGoogle Scholar