- New
-
Topics
- All Categories
- Metaphysics and Epistemology
- Value Theory
- Science, Logic, and Mathematics
- Science, Logic, and Mathematics
- Logic and Philosophy of Logic
- Philosophy of Biology
- Philosophy of Cognitive Science
- Philosophy of Computing and Information
- Philosophy of Mathematics
- Philosophy of Physical Science
- Philosophy of Social Science
- Philosophy of Probability
- General Philosophy of Science
- Philosophy of Science, Misc
- History of Western Philosophy
- Philosophical Traditions
- Philosophy, Misc
- Other Academic Areas
- Journals
- Submit material
- More
Algorithmic information theory and undecidability
Synthese 123 (2):217-225 (2000)
Abstract
Chaitin’s incompleteness result related to random reals and the halting probability has been advertised as the ultimate and the strongest possible version of the incompleteness and undecidability theorems. It is argued that such claims are exaggerations.Author's Profile
My notes
Similar books and articles
Computational complexity and Godel's incompleteness theorem.Gregory J. Chaitin - 1970 - [Rio de Janeiro,: Centro Técnico Científico, Pontifícia Universidade Católica do Rio de Janeiro. Edited by Gregory J. Chaitin.
A note on Monte Carlo primality tests and algorithmic information theory.Jacob T. Schwartz - unknown
Kolmogorov complexity and information theory. With an interpretation in terms of questions and answers.Peter D. Grünwald & Paul M. B. Vitányi - 2003 - Journal of Logic, Language and Information 12 (4):497-529.
On interpreting Chaitin's incompleteness theorem.Panu Raatikainen - 1998 - Journal of Philosophical Logic 27 (6):569-586.
Algorithmic randomness in empirical data.James W. McAllister - 2003 - Studies in History and Philosophy of Science Part A 34 (3):633-646.
Effective complexity as a measure of information content.James W. McAllister - 2003 - Philosophy of Science 70 (2):302-307.
Intrinsic information.John D. Collier - 1990 - In Philip P. Hanson (ed.), Information, Language and Cognition. University of British Columbia Press. pp. 1--390.
Analytics
Added to PP
2009-01-28
Downloads
947 (#14,081)
6 months
99 (#39,841)
2009-01-28
Downloads
947 (#14,081)
6 months
99 (#39,841)
Historical graph of downloads
Author's Profile
Citations of this work
Hypercomputation and the Physical Church‐Turing Thesis.Paolo Cotogno - 2003 - British Journal for the Philosophy of Science 54 (2):181-223.
On the philosophical relevance of Gödel's incompleteness theorems.Panu Raatikainen - 2005 - Revue Internationale de Philosophie 59 (4):513-534.
On analogues of the church–turing thesis in algorithmic randomness.Christopher P. Porter - 2016 - Review of Symbolic Logic 9 (3):456-479.
On explicating the concept the power of an arithmetical theory.Jörgen Sjögren - 2008 - Journal of Philosophical Logic 37 (2):183 - 202.
The Equivalence of Definitions of Algorithmic Randomness.Christopher Porter - 2021 - Philosophia Mathematica 29 (2):153–194.
References found in this work
Theory of recursive functions and effective computability.Hartley Rogers - 1987 - Cambridge, Mass.: MIT Press.
The concept of truth in formalized languages.Alfred Tarski - 1956 - In Logic, semantics, metamathematics. Oxford,: Clarendon Press. pp. 152--278.
Classical recursion theory: the theory of functions and sets of natural numbers.Piergiorgio Odifreddi - 1989 - New York, N.Y., USA: Sole distributors for the USA and Canada, Elsevier Science Pub. Co..
Trial and error predicates and the solution to a problem of Mostowski.Hilary Putnam - 1965 - Journal of Symbolic Logic 30 (1):49-57.
Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.
PhilPapers logo by Andrea Andrews and Meghan Driscoll.
This site uses cookies and Google Analytics (see our terms & conditions for details regarding the privacy implications). Use of this site is subject to terms & conditions.
All rights reserved by The PhilPapers Foundation
Server: philpapers-web-7c76586df8-5tf24 uwo