Saturday, November 20, 2004


Prof. Gregory Chaitin's latest book is currently online. The title derives from his halting probability Omega. The book is about randomness, information theory, and philosophy. Chaitin tries to make his book accessible to non-mathematicians. I'm obviously not the best judge of how well he did this, but I think a layman can certainly enjoy the book if they skip the technical parts as Chaitin suggests.

Getting a bit technical myself, I like Chaitin's way of proving Godel's incompleteness theorem, but I don't quite understand his aversion to Godel's and Turing's approaches. All three approaches use the same essential trick: assume completeness, then use self-reference to derive a contradiction via a diagonal argument. Godel used a formal sentence about arithmetic that refers to itself (indirectly through a numerical encoding). Turing used a program that refers to its own source code. Chaitin uses a program that refers to the length of its source code. There are certainly ways in which Chaitin's method is more powerful and arguably more beautiful (I really like it), but it still relies on the self-reference trick. If one is comfortable with self-reference, then what's not to like about Godel's or Turing's proof?


Post a Comment

Links to this post:

Create a Link

<< Home