Optimal enumerations and optimal gödel numberings
From MaRDI portal
Publication:4075448
DOI10.1007/BF01762189zbMATH Open0316.02044MaRDI QIDQ4075448FDOQ4075448
Authors: Claus Peter Schnorr 
Publication date: 1975
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Recursively (computably) enumerable sets and degrees (03D25) Recursive functions and relations, subrecursive hierarchies (03D20) Computability and recursion theory (03D99)
Cites Work
- A formal theory of inductive inference. Part I
- Title not available (Why is that?)
- Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication
- Program size in restricted programming languages
- Gödel numberings of partial recursive functions
- On the size of machines
Cited In (17)
- Renormalisation and computation. II: Time cut-off and the halting problem
- What can be efficiently reduced to the Kolmogorov-random strings?
- The independence of control structures in abstract programming systems
- The extent and density of sequences within the minimal-program complexity hierarchies
- Zipf's law and L. Levin probability distributions
- Computational complexity of formal translations
- Process complexity and effective random tests
- Short lists with short programs in short time
- Approximations to the halting problem
- What Percentage of Programs Halt?
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
- Enumerations including laconic enumerators
- Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega
- On the information carried by programs about the objects they compute
- Short lists with short programs from programs of functions and strings
- Toward an abstract theory of data compression
- A note on natural complete sets and Goedel numberings
This page was built for publication: Optimal enumerations and optimal gödel numberings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4075448)
