Re: Disproof of the Halting Problem's Conclusion

From: Peter Olcott (olcott_at_worldnet.att.net)
Date: 07/22/04 

Date: Thu, 22 Jul 2004 00:13:02 GMT

"Marc Goodman" <marc.goodman@comcast.net> wrote in message news:XuvLc.133840$a24.78695@attbi_s03...
> 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.
>

Turing Thesis:
Any computation that can be carried out by mechanical means
can be performed by some Turing Machine.

Hard to see how more powerful than this can exist.

Relevant Pages