Re: Disproof of the Halting Problem's Conclusion

From: Marc Goodman (marc.goodman_at_comcast.net)
Date: 07/21/04 

Date: Wed, 21 Jul 2004 14:56:56 GMT

Peter Olcott wrote:
> "Marc Goodman" <marc.goodman@comcast.net> wrote in message news:x0lLc.131965$%_6.1311@attbi_s01...
>
>>Peter Olcott wrote:
>>
>>>So you are saying that a machine that can not be transformed into a
>>>Turing Machine, yet can correctly determine whether or not any other
>>>software system (including Turing Machines) halts, would not solve
>>>the Halting Problem because it is not implemented as a Turing Machine?
>>
>>Exactly so. If it requires a model of computation more powerful
>>than a regular Turing Machine, it says nothing at all about the
>
>
> But the Church-Turing thesis says that there can't be a machine
> more powerful than a Turing Machine. Also adding a screen
> and protected memory to a computer does not make it more
> powerful, except that this might solve the Halting Problem.

Here's a trivial proof: Your program can model any Turing Machine,
so your program is at least as powerful as a Turing Machine. But no
Turing Machine can model your program (otherwise it could simulate
your program and return a result, but then it couldn't exist
because of the Halting Problem). So your program must be more
powerful than a Turing Machine. QED.

Relevant Pages