NECSI Resources

 International Conference on Complex Systems (ICCS2007)

Uncomputable Numbers: Turing's 1936 Paper Revisited

Gregory Chaitin
IBM Research

     Full text: Not available
     Last modified: September 10, 2007

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.

Maintained by NECSI Webmaster Copyright © 2000-2007 New England Complex Systems Institute. All rights reserved.