Re: Can you find anything wrong with this solution to the Halting Problem?

From: Arthur J. O'Dwyer (ajo_at_nospam.andrew.cmu.edu)
Date: 07/14/04 

Date: Wed, 14 Jul 2004 10:00:13 -0400 (EDT)

[Please note Followup-To]

On Tue, 13 Jul 2004, Peter Olcott wrote:
>
> See if you can find any reason why this would not work.
> http://home.att.net/~olcott/halts.html

  Simple. You provide the source code for your function 'WillHalt',
and I will provide you, within twenty-four hours, with the source
code to a program 'M', and an input 'I', to which your own function
will invariably give the *wrong* answer.

  If you refuse to publish your source code (or even a compiled
binary of the program 'WillHalt' will do, since machine code is just
a different kind of source), then that will be taken as an admission
that you never possessed such a program in the first place.

  I can produce 'M' and 'I' for any putative program 'WillHalt' you
can supply. Do you know how I know this? I will tell you. I can
produce these 'M' and 'I' practically mechanically, using a well-
known proof of something which Turing and others called the "halting
problem." I won't go into the details here, since you haven't shown
any signs of interest, but if you will send me a couple of tries at
'WillHalt' (again, in source or binary form --- anything I can run
on any existing or hypothetical computer system) I will post the
corresponding 'M' and 'I' for which they fail.

Eagerly awaiting your response,
-Arthur

Relevant Pages