Information-Theoretic Limitations of Formal Systems

DOI10.1145/321832.321839MaRDI QIDQ4775470zbMATH OpenOpenAlexFDO

Authors Gregory J. Chaitin

Publication date 1974

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/321832.321839

Mathematics Subject Classification ID

Computability and recursion theory (03D99) Analysis of algorithms and problem complexity (68Q25) Information theory (general) (94A15)

Cited in

(31)

• On the distribution function of the complexity of finite sequences
• The simulation of random processes on digital computers: Unavoidable order
• Information-theoretic incompleteness
• LISP program-size complexity. II
• Shadowing and iterative interpolation for Čebyšev mixing transformations
• Automaton introspection
• On interpreting Chaitin's incompleteness theorem
• Measuring prime program complexity
• Gödel's theorem and information
• Sets with small generalized Kolmogorov complexity
• Revisiting Chaitin's incompleteness theorem
• What one has to know when attacking \(\mathsf{P}\) vs.\(\mathsf{NP}\)
• Finite degree clones are undecidable
• Is complexity a source of incompleteness?
• On explicating the concept `the power of an arithmetical theory'
• Kolmogorov complexity and characteristic constants of formal theories of arithmetic
• Liar-type paradoxes and the incompleteness phenomena
• Differential equations as deterministic models in science and technology Part I: Modelling
• PROBLEMS WITH COMPLEXITY IN GOLD'S PARADIGM OF INDUCTION Part II: Static Complexity
• On Characteristic Constants of Theories Defined by Kolmogorov Complexity
• Propagation of partial randomness
• scientific article; zbMATH DE number 3761442 (Why is no real title available?)
• Rosser-type undecidable sentences based on Yablo's paradox
• Current research on Gödel's incompleteness theorems
• INFORMATION IN PROPOSITIONAL PROOFS AND ALGORITHMIC PROOF SEARCH
• Randomness and intractability in Kolmogorov complexity
• Kolmogorov complexity in perspective. I: Information theory and randomness
• WORD COMPLEXITY AND REPETITIONS IN WORDS
• Predictability: a way to characterize complexity
• Application of Chaitin's incompleteness theorem to quantum gravity
• Thoughts on the Riemann hypothesis

This page was built for publication: Information-Theoretic Limitations of Formal Systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4775470)