Simple Gödel Numberings, Isomorphisms, and Programming Properties

DOI10.1137/0207003zbMath0412.03020OpenAlexW2002183962MaRDI QIDQ4198487

No author found.

Publication date: 1978

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

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

zbMATH Keywords

Turing machinesprogramming languagefinite-state automatanatural translation-complexity numberingsrecursive fixed-point functiontranslation isomorphismtranslation properties of Gödel numberings

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) Complexity of computation (including implicit computational complexity) (03D15) General topics in the theory of software (68N01) Turing machines and related notions (03D10) Theory of numerations, effectively presented structures (03D45)

Related Items

Some remarks on witness functions for nonpolynomial and noncomplete sets in NP, Generality's price: Inescapable deficiencies in machine-learned programs, The independence of control structures in abstract programming systems, Remarks on recursion versus diagonalization and exponentially difficult problems, A note on natural complete sets and Goedel numberings, Program Self-reference in Constructive Scott Subdomains, Program self-reference in constructive Scott subdomains, Composition is almost (but not quite) as good as \(s-1-1\)