Re: Yet another Attempt at Disproving the Halting Problem

[Peter Olcott]

Actually, it would be nice of you to at least try to explain
Linz's proof (or whatever he or you call it). I realise that
would be problematic since that is probably the proof that
you originally disagree with.

I just posted a detailed explanation to in my immediately prior post.
Basically my contention is that the conclusion does not logically
follow from the proof. It looks like every proof only applies the
corrupted version to itself. When the original uncorrupted version
is applied to any other TM (including the corrupted one), the result
is conclusive rather than undecidable. Thus Turing did not prove
that solving the Halting Problem is impossible, only that there is
one way to try to solve it, that does not always work.

 

[Aatu Koskensilta]

It looks like every proof only applies the
corrupted version to itself. When the original uncorrupted version
is applied to any other TM (including the corrupted one), the result
is conclusive rather than undecidable. Thus Turing did not prove
that solving the Halting Problem is impossible, only that there is
one way to try to solve it, that does not always work.

And which way might this be?

 

[Karl Heinz Buchegger]

I just posted a detailed explanation to in my immediately prior post.
Basically my contention is that the conclusion does not logically
follow from the proof. It looks like every proof only applies the
corrupted version to itself. When the original uncorrupted version
is applied to any other TM (including the corrupted one), the result
is conclusive rather than undecidable. Thus Turing did not prove
that solving the Halting Problem is impossible, only that there is
one way to try to solve it, that does not always work.

You did not understand the proofing idea this proof is based on.
In this type of proof you really don't want to solve anything.
You assume that it is already solved (in this case: you assume
that there is a function WillHalt() that works) and use that
assumption to turn it against itself.

infinte amount of Prime numbers

assume there is a border such that no numbers bigger then that
border are prime.

use that border to construct a number which is
a) greater then the border
b) prime

-> conclusion: No such border can exist

Halting problem

assume there is a working function WillHalt()

Using that function WillHalt(), construct a function
which uses the result of WillHalt() in such a way that
inconsistent results are obtained.

-> conclusion: No such function can exist.


Also note: in the case of the Halting problem we are not interested
in a WillHalt function() that works most of the time. In fact such
things can be done, no problem. The Halting problem is about a function
wich works *always*, and it is the nature of for-all theorems that one
single counter example is enough to make them false.

See also:
http://en.wikipedia.org/wiki/Halting_problem
http://en.wikipedia.org/wiki/Reductio_ad_absurdum

 

[Mitch Harris]

Basically my contention is that the conclusion does not logically
follow from the proof. It looks like every proof only applies the
corrupted version to itself. When the original uncorrupted version
is applied to any other TM (including the corrupted one), the result
is conclusive rather than undecidable. Thus Turing did not prove
that solving the Halting Problem is impossible, only that there is
one way to try to solve it, that does not always work.

- what the heck is "the corrupted version"? There's no
corrupted or broken version of anything in the proof.
There's a hypothesis of something that forces a contradiction.

- I can only add slightly to this many visited theme about
the use of proof by contradiction.
- do you accept the proof by contradiction of the
infinitude of primes?
- do you accept the proof by contradiction of the
irrationality of sqrt(2)?
- do you accept the proof by construction of the
uncountability of the reals?
- If so, you can probably parlay that understanding into
a reconciliation of your doubts about Turing's proof.

 

[Chris Menzel]

Basically my contention is that the conclusion does not logically
follow from the proof.

So you're saying the proof is unsound, i.e., that it involves a false
premise or an invalid inference. Please identify a flaw in the proof:
http://tinyurl.com/6ow6c . If you can't (and you can't), then your
claim is OBVIOUSLY false.

Chris Menzel

 

[Kevin Stern]

is conclusive rather than undecidable. Thus Turing did not prove
that solving the Halting Problem is impossible, only that there is
one way to try to solve it, that does not always work.

Perhaps a contemporary dramatic version of the proof of the halting
problem will clear things up for you, Peter:

Alan Turing: Hmm, could there be a TM that recursively decides
whether or not all other TMs halt?

Alonzo Church: Well, Alan, that's a great question ... why don't you
think about it for awhile and let me know what you find out.

Alan Turing: Alonzo ... I think that what I'll do, in order to be
completely general and make no assumptions whatsoever about the
structure, is to assume that such a TM exists and to label it HALT.
You see, Alonzo, this way, I can see if the very existance of such a
program causes a contradiction without having to delve into any gory
details of 'code'.

Alonzo Church: Alan, that's a fine approach - I did something similar
when I showed that there can be no 'truth predicate' for sufficiently
powerful systems of arithmetic. Also, my friend Kurt Gödel took a
similar approach when showing that there can be no 'provability
predicate' within the system of the Principia.

Alan Turing: Thanks for the encouragement, Alonzo - I'm now convinced
that this will be a fun endeavor ... hmm, let's see:

Now, if HALT is recursive then certainly the following program will be
recursive:

D(x) {
IF HALT(x, x) = 'NO' THEN HALT
ELSE LOOP FOREVER
}

Because, as we recursion theorists know (here is where contemporary
comes into play, the label 'recursion theory' didn't come about until
much later), the composition of recursive functions is itself
recursive. So, now, could THIS be a TM?

Oh, oh, hey, Alonzo, I think I've got it ... D cannot be a TM ...

Here's why:

Let's enumerate all TMs into a table:

tm_1 tm_2 tm_3 [...]
tm_1 1 0 1 [...]
tm_2 0 0 1 [...]
tm_3 1 1 0 [...]
[...]

where (tm_x, tm_y) = 1 if tm_x(tm_y) halts and it is 0 if tm_x(tm_y)
does not halt.

Well, we have a list of TMs, let's see if it's in the list:

Is it TM_1? Well, it cannot be, because

D(TM_1) = if Halt(TM_1, TM_1) = 'No' then Halt else Loop Forever

And we can clearly see that TM_1(TM_1) halts (from the graph that I've
constructed), so D(TM_1) does not halt.

Is it TM_n? Well, it cannot be, because

D(TM_n) = if Halt(TM_n, TM_n) = 'No' then Halt else Loop Forever

And we can clearly see that if TM_n(TM_n) halts then D does not halt
and if TM_n(TM_n) does not halt then D halts.

It, therefore, cannot be any Turing Machines in the list of all Turing
Machines. D is not a Turing Machine and, therefore, Halt is not a
Turing Machine.

Woohoo!

Alonzo Church: Hey, Alan, you're no dummy!

Alan Turing: Thanks Alonzo, you're a pretty sharp cookie yourself!

 

[Chris Menzel]

Perhaps a contemporary dramatic version of the proof of the halting
problem will clear things up for you, Peter:

Alan Turing: Hmm, could there be a TM that recursively decides
whether or not all other TMs halt?

Alonzo Church: Well, Alan, that's a great question ... why don't you
think about it for awhile and let me know what you find out.

Alan Turing: Alonzo ... I think that what I'll do, in order to be
completely general and make no assumptions whatsoever about the
structure, is to assume that such a TM exists and to label it HALT.
You see, Alonzo, this way, I can see if the very existance of such a
program causes a contradiction without having to delve into any gory
details of 'code'.

Alonzo Church: Alan, that's a fine approach - I did something similar
when I showed that there can be no 'truth predicate' for sufficiently
powerful systems of arithmetic.

AT: Alonzo, you old coot, that was Tarski! *You* showed that
first-order validity was undecidable!

AC: Whatever.

 

[Peter Olcott]

- what the heck is "the corrupted version"? There's no
corrupted or broken version of anything in the proof.
There's a hypothesis of something that forces a contradiction.

Yes. That is what I am referring to. If this was applied as
input to the set of all possible TM's, and there was found at
least one TM that could properly determine its halting status,
then the contradiction would evaporate. Since it is only tested
against itself, the search for a possible halt analyzer was not
at all categorically exhaustive, thus it can not be concluded
from applying this one TM to itself, that all other TM's would
also have to fail.

Yes each and every one of these TM's can be modified to
have the same result as this TM. What no one (except me)
has yet understood, is that one must find data that all TMs
fail to process correctly to prove the case for the Halting
Problem. To merely show that each of them can be ruined
by changing them does not prove the case for the Halting
Problem.

It would be like saying that no computers are capabale of running
any programs, specifically because each any every one of these
computers can be made to not run correctly numerous ways.

 

[Peter Olcott]

Peter Olcott wrote:

Using that function WillHalt(), construct a function
which uses the result of WillHalt() in such a way that
inconsistent results are obtained.

-> conclusion: No such function can exist.

You find one way to screw up one version of WillHalt() and from that
you conclude that there is no possible way to make WillHalt() work?
For years this has been proposed as if it was one case of input that
no possible TM could possibly correctly process.

If this would have been what it was, then it would have proven the case
for the Halting Problem. Since this is NOT what it is it fails to prove the
case for the Halting Problem. Feel free to provide state transition diagrams
showing that no possible TM can correctly process this counter-example
TM.

 

[Peter Olcott]

And which way might this be?

--
Aatu Koskensilta ([email protected])

"Wovon man nicht sprechen kann, daruber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus

+----------+
| |
| |
input TM will halt V |
q(0)---------------------------->q(y)------>q(a)-------q(b)
|
|
| input TM will NOT halt
+--------------------------->(q(n))

 

[Marc Goodman]

You find one way to screw up one version of WillHalt() and from that
you conclude that there is no possible way to make WillHalt() work?
For years this has been proposed as if it was one case of input that
no possible TM could possibly correctly process.

Q: How many different versions of WillHalt() can there be?
A: Zero. If there were any more than zero, they would all
return the same results on the same input, so proving that any
one of them cannot exist is equivalent to proving that none of
them exist.

 

[Peter Olcott]

Q: How many different versions of WillHalt() can there be?
A: Zero. If there were any more than zero, they would all
return the same results on the same input, so proving that any
one of them cannot exist is equivalent to proving that none of
them exist.

If one program is made to function incorrectly, then can
we conclude that every program always functions incorrectly?

 

[Kenneth Doyle]

If one program is made to function incorrectly, then can
we conclude that every program always functions incorrectly?

The point you continually seem to miss is that the proof says that there is
a case where the halting analyser is incorrect if and only if it is
correct.

 

[Aatu Koskensilta]

+----------+
| |
| |
input TM will halt V |
q(0)---------------------------->q(y)------>q(a)-------q(b)
|
|
| input TM will NOT halt
+--------------------------->(q(n))

But this isn't "one way to try to solve" the Halting Problem. Or if it
is, it's spectacularly stupid one. Specifications for Turing machines
don't contain transitions labeled "input TM will halt" or "input TM will
NOT halt", so the above is not a Turing machine, which makes it rather
trivial that it can't be a way to solve the Halting Problem.

Turing's proof goes like this: the output of every Turing machine
differs from the function

Halt(A,x) = 1 if the machine described by A halts when given x as input
0 otherwise

in at least one argument pair. To demonstrate this, consider any Turing
machine M. As is known, there is a universal Turing machine U, s.t.
U(A,x,y) = A(x,y). From the instructions of U and M a Turing machine E_M
can be constructed as follows. When given input A the machine E_M
executes the instructions of the Universal Turing machine U, giving to
it as arguments M, A and A. Then depending on the output of U on these
arguments, it loops for ever if U(M,A,A) gives 1 as output and halts
otherwise. We see easily that M(E_M,E_M) necessarily differs from
Halt(E_M,E_M), thus showing that M differs from Halt(A,x) at least for
one argument pair, namely (E_M,E_M).

There is no "one way to try to solve the Halting Problem" here. If you
think there is, please indicate where exactly it occurs.

 

[Mitch Harris]

Yes. That is what I am referring to. If this was applied as
input to the set of all possible TM's, and there was found at
least one TM that could properly determine its halting status,
then the contradiction would evaporate. Since it is only tested
against itself, the search for a possible halt analyzer was not
at all categorically exhaustive, thus it can not be concluded
from applying this one TM to itself, that all other TM's would
also have to fail.

Yes each and every one of these TM's can be modified to
have the same result as this TM. What no one (except me)
has yet understood, is that one must find data that all TMs
fail to process correctly to prove the case for the Halting
Problem. To merely show that each of them can be ruined
by changing them does not prove the case for the Halting
Problem.

It would be like saying that no computers are capabale of running
any programs, specifically because each any every one of these
computers can be made to not run correctly numerous ways.

You are -so- close to figuring this out...

1 - The proof, in the proof by contradiction style, assumes
the existence of an arbitrary TM that is supposed to compute
Halt(M, w), and then goes on to show that this assumption
leads to a contradiction.

2 - You seem to think that that's not a problem, the
assumption just chose a particular -bad- version or modified
the assumed TM or something. You seem to think that one
could just choose -another- TM or modify it differently, so
that it doesn't force a contradiction.

3 - But the original proof is not like that. When it assumes
the existence of an arbitrary TM for Halt(M,w), it is
-arbitrary-. It stands for -any- possible TM. No matter what
the specific TM that is chosen, it is a black box, it is not
modified at all. Only the assumption of the property that it
computes Halt(M,w) matters and that property -always- -can-
lead to a contradiction. So no TM can compute Halt(M,w).

 

[Karl Heinz Buchegger]

[snip a marvelous proof using Cantors Diagonal argument]

Kevin, thanks for this wonderful 'proof'-story. I enjoyed reading
it.

 

[Karl Heinz Buchegger]

You find one way to screw up one version of WillHalt() and from that
you conclude that there is no possible way to make WillHalt() work?

Yep. (BTW: Why 'one version of WillHalt()'? No inner details of WillHalt()
were presented, so in the proof WillHalt() stands for: no matter what
WillHalt() looks like, as long as it attempts to do its job)

The claim is: WillHalt() works for *all* inputs. As usual, to disprove
a for-all argumentation it is enough to show one counterexample.
If that can be done, then the original claim is no longer valid: It doesn't
work for any and all.
Wondering: That's quite usual and accepted in proofing theory. If you
try to proof or diprove things you should know this.

 

[Andrew Koenig]

If one program is made to function incorrectly, then can
we conclude that every program always functions incorrectly?

You are asking the wrong question. The right question is this:

If one program is made to function incorrectly, then can we
conclude that every program *that returns the same results as
the incorrect program when given the same inputs* always
functions incorrectly?

The answer to this question is obviously yes: A program that produces
the same results as a broken program is broken.

 

[Marc Goodman]

If one program is made to function incorrectly, then can
we conclude that every program always functions incorrectly?

A program has to exist before it can be made to function incorrectly.
WillHalt cannot exist, your point is moot.

 

[Peter Olcott]

A program has to exist before it can be made to function incorrectly.
WillHalt cannot exist, your point is moot.

First of all this is flatly incorrect. The Halting Problem does not
say that a Halt Analyzer can not ever exist. All that it says is that
under certain weird circumstances it would not produce the correct
results. I will wait and see if you can get past that before I proceed.