Loading...
Please wait, while we are loading the content...
Similar Documents
Gödel numberings versus Friedberg numberings
| Content Provider | Semantic Scholar |
|---|---|
| Author | Pour-El, Marian Boykan |
| Copyright Year | 1964 |
| Abstract | In [3], Rogers discussed the concept of Godel numbering. He defined a semi-effective numbering, constructed a semi-lattice of equivalence classes of semi-effective numberings, and showed that all Gddel numberings belong to the unique maximal element of this semi-lattice. In [1], Friedberg gave a recursive enumeration without repetition of the set of partial recursive functions of a single variable. Friedberg's numbering is clearly a semi-effective numbering which is not a Godel numbering.2 QUESTION. How do Friedberg numberings (Definition 1 below) compare with Godel numberings? More generally, where do Friedberg numberings fit into Rogers' semi-lattice? DEFINITION 1. A Friedberg numbering r is a semi-effective numbering such that (1) Dr= N, (2) r i j if i -7j. SUMMARY OF RESULTS.3 I. If r is a Friedberg numbering then [T] is a minimal element of Rogers' semi-lattice. (Theorem 1.) II. There exists two Friedberg numberings r1 and r2 such that [r1] and [r2] are incomparable. (Theorem 2.) As a consequence of I and II we see that Rogers' semi-lattice is not a lattice (which answers a question raised in [3]). |
| Starting Page | 252 |
| Ending Page | 256 |
| Page Count | 5 |
| File Format | PDF HTM / HTML |
| DOI | 10.1090/S0002-9939-1964-0174479-5 |
| Volume Number | 15 |
| Alternate Webpage(s) | http://www.ams.org/journals/proc/1964-015-02/S0002-9939-1964-0174479-5/S0002-9939-1964-0174479-5.pdf |
| Alternate Webpage(s) | https://doi.org/10.1090/S0002-9939-1964-0174479-5 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
