Re: Attempt to Refute the Halting Problem's Refutation

From: Daryl McCullough (daryl_at_atc-nycorp.com)
Date: 08/14/04 

Date: 14 Aug 2004 11:07:19 -0700

Peter Olcott says...

>"Daryl McCullough" <daryl@atc-nycorp.com> wrote

>> The fact above is what Turing proved. If you are talking about
>> anything other than that, you are not talking about Turing's
>> proof.
>
>He did prove the above, yet incorrectly concluded the below from
>the above.

There was nothing incorrect about what Turing concluded. The
informal *conclusions* from Turing's proof are in effect
exrcises left to the reader. They aren't part of the proof.
The fact that you are unable to do that exercise has nothing
to do with the correctness of Turing's proof, which was that
there is no program H(x,y) that returns 1 if and only if x
is a code for a program that halts on input y.

If you agree that Turing proved that, then you have no
disagreement with Turing. Possibly, you want to propose
your own notion of "solving the halting problem" which
is different from Turing's notion. In which case, it
will be up to you, not Turing, to prove that it is or
is not impossible.

It's not Turing's obligation to prove something about Peter
Olcott's notion of solving the halting problem.

I gave an argument that depends on Church's thesis, but
shows that for *any* notion of "solving the halting problem
by a computer program", it's impossible. 

--
Daryl McCullough
Ithaca, NY

Relevant Pages