A Note on the Complexity of Goedel Numberings and Isomorphisms

Some problems involved in looking at recursive function theory and thinking about the complexity of computations are discussed. Complexity classes of Goedel numberings are studied where a Goedel numbering is in a given complexity class if every other Goedel numbering can be translated into it by functions ina given complexity class. In particular, we look at the class of numberings that can be trnslated into by polynomial time mappings (GNP) and the class that can be translated into by linear bounded automation mappings (GNLBA). It is shown that polynomial time isomorphisms and LBA computable isomorphisms between two Goedel numberings relate the complexity of the syntax of the numberings. Since the classes GNP and GNLBA contain Goedel numberings with arbitrarily hard syntax, not all members of these classes are isomorphic by polynomial time or LBA mappings. LBA computable isomorphisms can be found between members of GNLBA whose syntax is LBA recognizable. A similar result holds for polynomial time isomorphisms and GNP if P=NP