Re: Disproof of the Halting Problem's Conclusion

From: Mitch Harris (harrisq_at_tcs.inf.tu-dresden.de)
Date: 07/21/04 

Date: Wed, 21 Jul 2004 14:53:33 +0200

Peter Olcott wrote:
> "Marc Goodman" <marc.goodman@comcast.net> wrote in message news:x0lLc.131965$%_6.1311@attbi_s01...
>>Peter Olcott wrote:
>
> But the Church-Turing thesis says that there can't be a machine
> more powerful than a Turing Machine.

No, it doesn't. It says that the many formalisms that happen
to be just as powerful as a TM are what we should all agree
on as the most appropriate formalism in which to discuss
computation.

> Also adding a screen
> and protected memory to a computer does not make it more
> powerful,

OK. to me that means you can't do anything with these two
additional properties that you can't do without. So any
proof using these two things can be done without (and vice
versa).

> except that this might solve the Halting Problem.

this may seem like begging the question to you, since you
have not accepted the proof that every one else accepts, but
by your previous statement (that adding a "screen" and
"protected memory" adds no power, to which I agree) this is
contradictory. If your proposed machine could solve the
Halting problem, then it would be more powerful than your
everyday TM. If it is as powerful as TMs, then it cannot
solve the Halting problem.

> I doubt that you can find anything anywhere in the academic
> research that says adding a screen to a machine that solves
> the Halting Problem, makes this solution not count.

I was about to say "I agree" (because 1) no one would bother
to take the time to do such a search for a nonentity, and 2)
because I would find it difficult to imagine such additions
being publishable in such language).

But a reasonable interpretation of your additions ("screen"
sounds like write only memory, and protected memory sounds
like... well.. like... memory.) And these restrictions,
shoot lets add in read only memory, that's a little more
useful, these restrictions have been proved to be no
restrictions at all (these kinds of TM modifications are
excellent homework style problems, like multitape, or multi
head)

If you are saying that your new kind of machine, has
particular restrictions, such that there is a procedure
(doesn't have to be the same kind of machine, could be a TM
or a very lucky geiger counter) to determine if any given
machine of your new kind halts or not on given input, well,
that's no surprise. There are all sorts of machines for
which this is known (some of which have already been
mentioned: FSAs, linear bounded automata).

I'm sorry but none of this sounds convincing. Not that it is
not true, just that they are just simple statements, not
even an attempt at convincing. 

-- 
Mitch Harris
(remove q to reply)

Relevant Pages

  • Re: Disproof of the Halting Problems Conclusion
    ... It says that the many formalisms that happen ... "protected memory" adds no power, to which I agree) this is ... Halting problem, then it would be more powerful than your ... I'm sorry but none of this sounds convincing. ...
    (comp.theory)
  • Re: Disproof of the Halting Problems Conclusion
    ... It says that the many formalisms that happen ... means can be performed by some Turing Machine. ... The Halting Problem might not be solved ... Protected memory might be construed as beyond the capabilites ...
    (comp.theory)
  • Re: Disproof of the Halting Problems Conclusion
    ... It says that the many formalisms that happen ... means can be performed by some Turing Machine. ... The Halting Problem might not be solved ... Protected memory might be construed as beyond the capabilites ...
    (sci.logic)