LISP program-size complexity. II

DOI10.1016/0096-3003(92)90100-FzbMath0757.68066OpenAlexW4236000257MaRDI QIDQ1200219

Gregory J. Chaitin

Publication date: 17 January 1993

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0096-3003(92)90100-f

zbMATH Keywords

program-size complexityinformation-theoretic incompleteness theoremsLISP halting probability

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items

Is complexity a source of incompleteness?, Natural halting probabilities, partial randomness, and zeta functions, LISP program-size complexity. III, LISP program-size complexity. IV

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• LISP program-size complexity
• Gödel's theorem and information
• Register machine proof of the theorem on exponential diophantine representation of enumerable sets
• Proof of Recursive Unsolvability of Hilbert's Tenth Problem
• RANDOMNESS AND COMPLEXITY IN PURE MATHEMATICS
• Information-Theoretic Limitations of Formal Systems
• Information-Theoretic Incompleteness