Optimal enumerations and optimal gödel numberings
From MaRDI portal
Publication:4075448
DOI10.1007/BF01762189zbMath0316.02044MaRDI QIDQ4075448
Publication date: 1975
Published in: Mathematical Systems Theory (Search for Journal in Brave)
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