On Simple Goedel Numberings and Translations
J. Hartmanis, T. P. Baker · SIAM Journal on Computing · 1975
In this paper we consider classes of Goedel numberings, viewed as simple models for programming languages, into which all other Goedel numberings can be translated by computationally simple mappings. Several such classes of Goedel numberings are defined and their properties are investigated. For example, one such class studied is the class of Goedel numberings into which all other Goedel numberings can be translated by finite automata mappings. We also compare these classes of Goedel numberings to the class of optimal Goedel numberings and show that translation into optimal Goedel numberings can be computationally arbitrarily complex, thus indicating that from a computer science point of view, optimal Goedel numberings have undesirable properties.