Information-Theoretic Limitations of Formal Systems
From MaRDI portal
Publication:4775470
DOI10.1145/321832.321839zbMath0287.68027OpenAlexW2086390954MaRDI QIDQ4775470
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
Analysis of algorithms and problem complexity (68Q25) Information theory (general) (94A15) Computability and recursion theory (03D99)
Related Items
Measuring prime program complexity, Liar-type paradoxes and the incompleteness phenomena, Is complexity a source of incompleteness?, INFORMATION IN PROPOSITIONAL PROOFS AND ALGORITHMIC PROOF SEARCH, Propagation of partial randomness, 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, WORD COMPLEXITY AND REPETITIONS IN WORDS, Rosser-type undecidable sentences based on Yablo's paradox, Revisiting Chaitin's incompleteness theorem, Unnamed Item, Information-theoretic incompleteness, LISP program-size complexity. II, Shadowing and iterative interpolation for Čebyšev mixing transformations, On explicating the concept `the power of an arithmetical theory', What one has to know when attacking \(\mathsf{P}\) vs.\(\mathsf{NP}\), Thoughts on the Riemann hypothesis, Automaton introspection, Predictability: a way to characterize complexity, CURRENT RESEARCH ON GÖDEL’S INCOMPLETENESS THEOREMS, On the distribution function of the complexity of finite sequences, Gödel's theorem and information, Randomness and Intractability in Kolmogorov Complexity, Kolmogorov complexity and characteristic constants of formal theories of arithmetic, Sets with small generalized Kolmogorov complexity, On interpreting Chaitin's incompleteness theorem, The simulation of random processes on digital computers: Unavoidable order, Finite degree clones are undecidable, Kolmogorov Complexity in Perspective Part I: Information Theory and Randomness
