Algorithmic Information Theory, Free Will, and the Turing Test "All theory is against the freedom of the will; all experience for it."-Samuel Johnson M any profound philosophical problems have their origin in pure mathematics, problems ranging from the nature and properties of infinity to the limitations of mathematical proof and the meaning of truth itself. But few developments in the history of mathematics have deeper and more diverse philosophical ramifications than Go Β¨del's incompleteness theorem.
The discovery of Go Β¨del's theorem in the 1930s shook the mathematical world to its core. Go Β¨del's work put an end to a half century or more of unsuccessful attempts to build a firm theoretical foundation for mathematics. His theorem showed that there are infinitely many statements in mathematics that are true but cannot be proved [1, Chapter 2]. Chaitin [2, p. 61] notes that:
At the time of its discovery, Kurt Go Β¨del's incompleteness theorem was a great shock and caused much uncertainty and depression among mathematicians sensitive to foundational issues, since it seemed to pull the rug out from under mathematical certainty, objectivity, and rigor. Also, its proof was considered to be extremely difficult and recondite. With the passage of time the situation has been reversed. A great many proofs of Go Β¨del's theorem are now known, and the result is now considered easy to prove and almost obvious.
Chaitin goes on to describe his recent innovations that expand on Go Β¨del's work by exploring its multifarious connections with other important areas of mathematics,