Gödel numberings versus Friedberg numberings
Marian Boykan Pour‐El · Proceedings of the American Mathematical Society · 1964
In [3], Rogers discussed the concept of Gödel numbering.He defined a semi-effective numbering, constructed a semi-lattice of equivalence classes of semi-effective numberings, and showed that all Gödel numberings belong to the unique maximal element of this semi-lattice.In [l], 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 Gödel numbering.2Question.How do Friedberg numberings (Definition 1 below) compare with Gödel numberings?More generally, where do Friedberg numberings fit into Rogers' semi-lattice?Definition 1.A Friedberg numbering t is a semi-effective num-