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

Recursive functions and relations, subrecursive hierarchies (03D20) Recursively (computably) enumerable sets and degrees (03D25) Computability and recursion theory (03D99)

Related Items (17)

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

Cites Work

• Unnamed Item
• 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

This page was built for publication: Optimal enumerations and optimal gödel numberings