ICCS07/96

From NECSIWiki

[edit] Uncomputable Numbers: Turing's 1936 Paper Revisited

Gregory Chaitin, IBM Research

Abstract

It is usually forgotten that the key point of Turing's famous 1936 paper "On computable numbers with an application to the Entscheidungsproblem" was to exhibit an uncomputable real number. In fact, Borel in 1927 had already done this. I'll discuss the relationship between the ideas of Turing and those of Borel and also my own uncomputable real number, the halting probability Omega.

Reference: Chaitin, Thinking about Godel & Turing, World Scientific, 2007.

[edit] Additional content about this research can be added below

(To edit the abstract and author information above, please go to the abstract submission system so that the information in the on-line proceedings will be up-to-date. The wiki pages wil be updated regularly to include changes made through the submission system.)