Simple Gödel numberings, translations, and the p-hierarchy (Preliminary Report)
Michael Machtey, Paul Young · 1976
We study restricted classes of programming systems (Godel numberings), where a programming system is in a given class if every programming system can be translated into it by functions in a given restricted class. For pairs of systems in various “natural” classes we give results on the existence of isomorphisms (one-to-one and onto translations) between them from the appropriate class of functions. Our results with the most computational significance concern polynomial time programming systems. We show that if P=NP then every two polynomial time programming systems are isomorphic via a polynomial time computable function. IfP