Uncomputable Numbers: Turing's 1936 Paper Revisited
Gregory Chaitin
IBM Research
Full text:
Not available
Last modified: September 10, 2007
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.
