Meta Maths: The Quest For Omega by Gregory Chaitin

Meta Maths: The Quest For Omega explains some of the relationships between the halting problem, Godel’s incompleteness theorem and the measurement of complexity where this is defined as the size of the smallest program that encodes the information.
The book covers how Chaitin became interested in this area (as a means for understanding Godel’s incompleteness theorem) and covers some of the history of such ideas, relating them to philosophy and logic.
This book is intended as a general overview and missed out some of the more technical details which I think I would have found interesting, but was a good read.
Chaitin’s website contains some of the related material, such as Lisp programs for calculating some of the digits of omega (the halting probability).
 
Advertisements
This entry was posted in Books. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s