Hostname: page-component-78c5997874-mlc7c Total loading time: 0 Render date: 2024-11-05T16:32:06.406Z Has data issue: false hasContentIssue false

Gödel numberings of partial recursive functions

Published online by Cambridge University Press:  12 March 2014

Hartley Rogers Jr.*
Affiliation:
Massachusetts Institute of Technology

Extract

In § 1 we present conceptual material concerning the notion of a Gödel numbering of the partial recursive functions. § 2 presents a theorem about these concepts. § 3 gives several applications. The material in § 1 and § 2 grew out of attempts by the author to find routine solutions to some of the problems discussed in § 3. The author wishes to acknowledge his debt in § 2 to the fruitful methods of Myhill in [M] and to thank the referee for an abbreviated and improved version of the proof for Lemma 3 in § 2.

In the literature of mathematical logic, “Gödel numbering” usually means an effective correspondence between integers and the well-formed formulas of some logical calculus. In recursive function theory, certain such associations between the non-negative integers and instructions for computing partial recursive functions have been fundamental. In the present paper we shall be concerned only with numberings of the latter, more special, sort. By numbers and integers we shall mean non-negative integers. Our notation is, in general, that of [K]. If ϕ and ψ are two partial functions, ϕ = ψ shall mean that (∀x)[ϕ(x)≃(ψx)], i.e., that ϕ and ψ are defined for the same arguments and are equal on those arguments. We consider partial recursive functions of one variable; applications of the paper to the case of several variables, or to the case of all partial recursive functions in any number of variables, can be made in the usual way using the coordinate functions (a)i of [K, p. 230]. It will furthermore be observed that we consider only concepts that are invariant with respect to general recursive functions; more limited notions of Gödel numbering, taking into account, say, primitive recursive structure, are beyond the scope of the present paper.

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1958

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.)

References

REFERENCES

[D]Davis, M., Computability and unsolvability, McGraw-Hill (1958), New York.Google Scholar
[K]Kleene, S. C., Introduction to metamathematics, Van Nostrand (1952), New York.Google Scholar
[K&P]Kleene, S. C. and Post, E. L., The upper semi-lattice of degrees of recursive unsolvability, Annals of mathematics, vol. 59 (1954), pp. 379407.CrossRefGoogle Scholar
[M]Myhill, J. R., Creative sets, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 1 (1955), pp. 97108.CrossRefGoogle Scholar
[Me]Médvédév, Ú. T., Degrees of difficulty of mass problems (Russian), Doklady Akadémii Nauk SSSR, vol. 104 (1955), pp. 501504.Google Scholar
[P]Post, E. L., Recursively enumerable sets of positive integers and their decision problems, Bulletin of the American Mathematical Society, vol. 50 (1944), pp. 284316.CrossRefGoogle Scholar