Show simple item record

dc.contributor.authorKadin, Jimen_US
dc.description.abstractSome 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.en_US
dc.format.extent1118413 bytes
dc.format.extent255864 bytes
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleA Note on the Complexity of Goedel Numberings and Isomorphismsen_US
dc.typetechnical reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record