In a book review of Torkel Franzén's "Gödel’s Theorem: An Incomplete Guide to Its Use and Abuse" in the Notices the reviewer (Raatikainen) writes:

Franzén also devotes a brief chapter to the variants of incompleteness results arising from the so-called Algorithmic Information Theory, or the theory of Kolmogorov complexity, and especially the various philosophical interpretations of these results by Gregory Chaitin (one of the founders of this theory). For example, Chaitin claims that his results not only explain Gödel’s incompleteness theorem but also are the ultimate, or the strongest possible, incompleteness results. Franzén first explains these results and then shows that such claims are in noway justified by mathematical facts.

  1. What "philosophical interpretations" are being referred to?

  2. In what sense could Chatin's theorem be the "ultimate, or the strongest possible, incompleteness result"?

[I know I can read the particular section in Franzén's book, and so I have, but a question here is still relevant and useful to others, and explanations by different people yield often additional insight (so also for me).]

  • 3
    $\begingroup$ Chaitin makes (arguably) extravagant and polemical claims about his achievements; Franzen aims to deflate these. $\endgroup$ – Angina Seng Aug 28 '20 at 11:14
  • $\begingroup$ @Angina But there is absolutely nothing to those claims? Have others defended (some of) those viewpoints of Chaitin? Maybe you can write an answer :) $\endgroup$ – Jori Aug 28 '20 at 12:29
  • $\begingroup$ The bits of a chaitin number form in some sense the best compression of a huge amount of informations. The first $n$ digits of a chaitin number can be used to solve the halting problem upto $n$ bits for a corresponding computer. The catch is that the decompression has an enormous complexity. The effort necessary to decode a Chaitin number grows faster with $n$ than any computable function ! $\endgroup$ – Peter Sep 8 '20 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.