Algorithmic information theory and undecidability
Synthese 123 (2):217-225 (2000)
| Abstract | Algorithmic information theory, or the theory of Kolmogorov complexity, has become an extraordinarily popular theory, and this is no doubt due, in some part, to the fame of Chaitin’s incompleteness results arising from this field. Actually, there are two rather different results by Chaitin: the earlier one concerns the finite limit of the provability of complexity (see Chaitin, 1974a, 1974b, 1975a); and the later is related to random reals and the halting probability (see Chaitin, 1986, 1987a, 1987b, 1988, 1989. | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,679 |
| External links |
  Try with proxy. |
| Through your library | Configure |
Similar books and articlesGregory J. Chaitin (1970). Computational Complexity and Godel's Incompleteness Theorem. [Rio De Janeiro,Centro Técnico Científico, Pontifícia Universidade Católica Do Rio De Janeiro.
James W. McAllister (2003). Effective Complexity as a Measure of Information Content. Philosophy of Science 70 (2):302-307.
W. J. (2003). Algorithmic Randomness in Empirical Data. Studies in History and Philosophy of Science Part A 34 (3):633-646.
Marcin Miłkowski (2009). Is Evolution Algorithmic? Minds and Machines 19 (4):465-475.
Panu Raatikainen (1998). On Interpreting Chaitin's Incompleteness Theorem. Journal of Philosophical Logic 27 (6):569-586.
Peter D. Grünwald & Paul M. B. Vitányi (2003). Kolmogorov Complexity and Information Theory. With an Interpretation in Terms of Questions and Answers. Journal of Logic, Language and Information 12 (4):497-529.
Michiel Van Lambalgen (1989). Algorithmic Information Theory. Journal of Symbolic Logic 54 (4):1389 - 1400.
Analytics
Monthly downloads |
Added to index2009-01-28Total downloads10 ( #106,301 of 549,087 )Recent downloads (6 months)1 ( #63,317 of 549,087 )How can I increase my downloads? |
My notes
Discussion
