Algorithmic entropy of sets

DOI10.1016/0898-1221(76)90016-XzbMath0367.68036MaRDI QIDQ1242451

Gregory J. Chaitin

Publication date: 1976

Published in: Computers \& Mathematics with Applications (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Information theory (general) (94A15) General topics in the theory of software (68N01) Recursively (computably) enumerable sets and degrees (03D25)

Related Items

Recursion and topology on \(2^{\leq\omega}\) for possibly infinite computations ⋮ Algorithmic complexity as a criterion of unsolvability ⋮ Algorithmic thermodynamics ⋮ Differences of halting probabilities ⋮ Random reals and possibly infinite computations Part I: Randomness in ∅′ ⋮ Information-theoretic incompleteness ⋮ Random numbers as probabilities of machine behavior ⋮ A Chaitin \(\Omega\) number based on compressible strings ⋮ Program size complexity for possibly infinite computations ⋮ Kolmogorov complexity for possibly infinite computations ⋮ Noncomputability arising in dynamical triangulation model of four- dimensional quantum gravity

Cites Work

• Information-theoretic characterizations of recursive infinite strings
• Program size, oracles, and the jump operation
• A Theory of Program Size Formally Identical to Information Theory
• Unnamed Item
• Unnamed Item