Optimal enumerations and optimal gödel numberings
From MaRDI portal
Publication:4075448
Cites work
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- A formal theory of inductive inference. Part I
- Gödel numberings of partial recursive functions
- On the size of machines
- Program size in restricted programming languages
- Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication
Cited in
(17)- What can be efficiently reduced to the Kolmogorov-random strings?
- 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 extent and density of sequences within the minimal-program complexity hierarchies
- The independence of control structures in abstract programming systems
- What percentage of programs halt?
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
- Computational complexity of formal translations
- Approximations to the halting problem
- Zipf's law and L. Levin probability distributions
- Process complexity and effective random tests
- A note on natural complete sets and Goedel numberings
- Toward an abstract theory of data compression
- Short lists with short programs in short time
- Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega
- Renormalisation and computation. II: Time cut-off and the halting problem
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)
