Algorithmic information theory and undecidability

Synthese 123 (2):217-225 (2000)
  Copy   BIBTEX


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.

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.
On interpreting Chaitin's incompleteness theorem.Panu Raatikainen - 1998 - Journal of Philosophical Logic 27 (6):569-586.
Is Evolution Algorithmic?Marcin Miłkowski - 2009 - Minds and Machines 19 (4):465-475.
Algorithmic randomness in empirical data.James W. McAllister - 2003 - Studies in History and Philosophy of Science Part A 34 (3):633-646.
Intrinsic information.John D. Collier - 1990 - In Philip P. Hanson (ed.), Information, Language and Cognition. University of British Columbia Press. pp. 1--390.


Added to PP

844 (#12,045)

6 months
134 (#9,223)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Panu Raatikainen
Tampere University

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.
Epistemic optimism.Mihai Ganea - 2008 - Philosophia Mathematica 16 (3):333-353.
The Equivalence of Definitions of Algorithmic Randomness.Christopher Porter - 2021 - Philosophia Mathematica 29 (2):153–194.

View all 6 citations / Add more citations

References found in this work

The concept of truth in formalized languages.Alfred Tarski - 1931 - In A. Tarski (ed.), Logic, Semantics, Metamathematics. Oxford University 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..

View all 14 references / Add more references