Optimal enumerations and optimal gödel numberings

DOI10.1007/BF01762189zbMath0316.02044MaRDI QIDQ4075448

Claus Peter Schnorr

Publication date: 1975

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Mathematics Subject Classification ID

03D20: Recursive functions and relations, subrecursive hierarchies

03D25: Recursively (computably) enumerable sets and degrees

03D99: Computability and recursion theory

Related Items

Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega, Toward an abstract theory of data compression, Some remarks on witness functions for nonpolynomial and noncomplete sets in NP, The independence of control structures in abstract programming systems, A note on natural complete sets and Goedel numberings, The extent and density of sequences within the minimal-program complexity hierarchies, Approximations to the halting problem, On the information carried by programs about the objects they compute, Short lists with short programs from programs of functions and strings, Short lists with short programs in short time, Zipf's law and L. Levin probability distributions, Process complexity and effective random tests, Enumerations including laconic enumerators, What can be efficiently reduced to the Kolmogorov-random strings?, Renormalisation and computation II: time cut-off and the Halting Problem, What Percentage of Programs Halt?, Computational complexity of formal translations

Cites Work

• Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication
• Gödel numberings of partial recursive functions
• Program size in restricted programming languages
• On the size of machines
• A formal theory of inductive inference. Part I
• Unnamed Item