On Simple Goedel Numberings and Translations

DOI10.1137/0204001zbMath0272.68046OpenAlexW2068364425MaRDI QIDQ5180402

Theodore P. Baker, Juris Hartmanis

Publication date: 1975

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0204001

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Recursive functions and relations, subrecursive hierarchies (03D20)

Related Items (6)

Reductions among polynomial isomorphism types ⋮ Collapsing degrees ⋮ The independence of control structures in abstract programming systems ⋮ A note on natural complete sets and Goedel numberings ⋮ Toward an abstract theory of data compression ⋮ Composition is almost (but not quite) as good as \(s-1-1\)

This page was built for publication: On Simple Goedel Numberings and Translations