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

From: Mark Nudelman (markn_at_greenwoodsoftware.com)
Date: 07/14/04 

Date: Wed, 14 Jul 2004 17:14:01 GMT

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

Ok, let me summarize your argument. You claim
1. Turing's proof relies on using the output of WillHalt in another program,
LoopIfHalts.
2. You can construct a version of WillHalt that sends its output somewhere
to which other programs have no access (the "screen").
3. Therefore Turing's proof is invalid.

Now suppose you created such a WillHalt program, call it P1. Suppose I then
take a copy of P1, and make a small change to it so that its output _is_
accessible to other programs -- I return the output rather than writing it
to the screen. Call this new program P2. Obviously P2 is susceptible to
Turing's proof, so P2 cannot exist. But your claim is that P1 can exist, so
it must be the case that it's impossible to modify P1 as I've described.
But how could this be the case? To change P1 to P2, all I need to do is
replace a few statements that write a value to the screen with a few
statements that return that value instead. What could possibly prevent me
from doing this?

Note that your attempts to make P1 "protected" while it is executing are
quite beside the point. I'm not claiming that I need to write a program to
modify P1, or write to P1's memory, or anything like that. I just need to
you provide me with a copy of P1's source, and I'll change a couple of lines
in it to produce P2.

--Mark

Relevant Pages