Re: Gödel, Turing, and Cantor

From: Robert Israel (israel_at_math.ubc.ca)
Date: 09/14/04 

Date: 14 Sep 2004 22:14:02 GMT

In article <4146a8be$0$167$edfadb0f@dread11.news.tele.dk>,
Michael Jřrgensen <ingen@ukendt.dk> wrote:

>I'm wondering whether there is a connection between
>1) Gödel's incompleteness theorem
>2) Turing's Halting Problem
>3) Cantor's Theorem

>The proof of all three statements involve some kind of diagonalization, i.e.
>where there is some function f(x,y) and the proof then procedes by iterating
>over f(x,x).

>At least Gödel's and Turing's statements are very similar: They both talk
>about something that is undecibable/unprovable. Gödel proved constructively
>the existence of an unprovable statement, while Turing constructed a Turing
>machine for which the halting problem is undecidable.

Turing implies Gödel:

Consider the statement H(n): Turing machine #n [in an appropriate
numbering] will halt. Assume this can be formalized appropriately
in a certain formal language L, such that if Turing machine #n halts
then H(n) is provable in L [typically, by going through each of the
finitely many steps that the Turing machine performs until it halts].
Suppose also that language L is consistent.
If "not S(n)" is provable in L then S(n) is not provable in L, so
the Turing machine does not halt. Then it must be that for at least
one n, neither S(n) nor "not S(n)" is provable in L. For otherwise,
there would be an algorithm to tell whether Turing machine #n halts:
  Search sequentially through all finite strings in L until you find
  either a proof of S(n) or a proof of "not S(n)". If you find a
  proof of S(n), conclude that the machine halts, if you find a
  proof of "not S(n)", conclude that it doesn't halt.

I'm not sure if you can go in the opposite direction.

Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2
  

Relevant Pages

  • Re: Godel proved maths inconsistent not incompleteness theorem
    ... formulating Godel's Incompleteness Theorem in "The Emperor's New Mind" ... It is also not reducing anything to the Halting Problem or the Always ... the statement "Turing machine with Godel number x will not halt on ...
    (sci.logic)
  • Re: Peter Olcotts Source of Confusion
    ... >> see if a Turing machine M halts on input x. ... >would solve the Halting Problem sure seems like pure malarkey. ... Processing speed is irrelevant as long as there is some lower bound ...
    (sci.logic)
  • Re: Contradiction or paradox
    ... and ~_is_ a wff by that definition. ... ~LTand then halts. ... The rest of the line is CBL command write with argument ... YES"Turing Machine a halts yes on input b." ...
    (sci.logic)
  • Re: Partial recursive functions and minimization
    ... Suppose that T is a Turing Machine. ... Then G is partial recursive if and only if the halting problem for T ... whether or not T halts on x. Stated this way, ... since it contradicts the undecidability of the Halting Problem. ...
    (sci.math)
  • Re: Rados Sigma and the Halting Problem for Programs
    ... AD> computer language that does not contrive a logic paradox ... Halting Theorem may be proven without recourse to reductio ... computation halts, and is bottom, i.e. _|_ if the computation diverges ... Assume that from a Turing Machine M we can construct a Turing Machine ...
    (comp.theory)
Loading