Re: Turing vs. Godel (Newbie Question) (A simple example)

Tom wrote:
Does anyone have a simple example of a turing machine (or computer
program) which (we assume) doesn't halt, but is unprovable.

I think your request may be based on a misunderstanding of Turing's proof. Turing shows that for any Turing machine M, M does not solve every instance of the halting problem. He does this by constructing a counterexample, but the counterexample depends on M. There is no universal counterexample that works against any proposed algorithm. (Proof: suppose U is the universal counterexample. Either M = "say 'yes'" or M = "say 'no'" will correctly determine whether U halts. Contradiction.)

What Turing proves is the lack of any algorithmic pattern in the sequence of halting answers, not the impossibility of finding some particular term in the sequence.

-- Ben
.

Relevant Pages

  • Re: Church-Turing compared to Zuse-Fredkin thesis (two new papers)
    ... I enjoyed thinking more about the consequences of Turing, ... A sequence is said to be computable if it can be computed by a circle-free ... circular if it performs an infinite computation outputting only finitely ... because it can be generated by a shorter algorithm. ...
    (comp.theory)
  • Re: proof of undecidability of halting problem
    ... however, the contradiction is introduced by using a second function, ... a function like halt can't? ... Turing proved it could be done. ... How can a high level language prove theorems ...
    (sci.logic)
  • Re: Turing vs. Godel (Newbie Question) (A simple example)
    ... Turing shows that for any Turing machine M, ... the counterexample depends on M. ... Goldbach's conjecture. ... It halts if and only if the ...
    (sci.math)
  • Re: [PO] halting problem reading comprehension
    ... "Peter Olcott" wrote in message ... You have been, for some time, been asserting that _finite_ Turing ... machines can solve the Halting Problem. ... is a very simple 'c' program which will halt when it has found ...
    (comp.theory)
  • Re: [PO] halting problem reading comprehension
    ... "Peter Olcott" wrote in message ... You have been, for some time, been asserting that _finite_ Turing ... machines can solve the Halting Problem. ... is a very simple 'c' program which will halt when it has found ...
    (sci.logic)