Re: Turing vs. Godel (Newbie Question) (A simple example)
- From: israel@xxxxxxxxxxx (Robert Israel)
- Date: 14 Jul 2006 21:14:12 GMT
In article <29961248.1152899513254.JavaMail.jakarta@xxxxxxxxxxxxxxxxxxxxxx>,
Tom <t_d_lowe@xxxxxxxxxxx> wrote:
Tom wrote:
Does anyone have a simple example of a turingmachine (or computer
program) which (we assume) doesn't halt, but isunprovable.
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
Mmmm... so even though he's given this counter-example (that depends on
M), the counter-example is not constructible in practice and in fact,
its kind of this non-constructibility of the counter example which is
why its improvable. I think I get it.
So there's no constructible program like:
x = 0
do
x(n+1) = (x(n)*7 + 13) mod (n + 123)
stop if x = 0
which is unprovably unhalting.. ie x never returns to 0, but its unprovable?
No, there are such programs. You can't just say "unprovable" without
specifying the system, because you could always add the statement
you want to prove as a new axiom, and have a new system where that
statement is provable.
There is a particular polynomial p(a,r,s,t,u,v,w,x,y,z),
constructed by Matiyasevich, with the following property.
Consider the following program.
Input the natural number a.
Search through all 9-tuples of natural numbers (r,s,t,u,v,w,x,y,z)
and halt if p(a,r,s,t,u,v,w,x,y,z) = 0.
For any consistent formal system S of arithmetic with a finite set
of axioms, there is some natural number a such that
p(a,r,s,t,u,v,w,x,y,z) = 0 has no solutions in natural numbers
(so the program will not halt with this input), but that fact
cannot be proven in the system S.
I think this explains why the examples given so far are pretty
complicated to get my head around.
For a simple example, consider the following program
for n from 4 by 2 do
ok := true
for k from 2 to n/2 do
if (k is prime) and (n-k is prime) then ok:= false
end do
if ok then halt
end do
In other words, this searches for a counterexample to
Goldbach's conjecture. It halts if and only if the
conjecture is false. If you could prove it never halts,
you'd have a proof of Goldbach's conjecture. We don't happen
to know whether this conjecture is true (that's why it's
still called a conjecture); it's quite possible that it's
true but there is no proof of that in (choose your
favourite formal system).
Robert Israel israel@xxxxxxxxxxx
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
.
- References:
- Re: Turing vs. Godel (Newbie Question) (A simple example)
- From: Ben Rudiak-Gould
- Re: Turing vs. Godel (Newbie Question) (A simple example)
- From: Tom
- Re: Turing vs. Godel (Newbie Question) (A simple example)
- Prev by Date: Re: JSH: Factoring and residues
- Next by Date: Re: Set Theory: Should you believe?
- Previous by thread: Re: Turing vs. Godel (Newbie Question) (A simple example)
- Next by thread: Re: Turing vs. Godel (Newbie Question) (A simple example)
- Index(es):
Relevant Pages
|
