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:05:33 GMT

"Mitch Harris" <harrisq@tcs.inf.tu-dresden.de> wrote in message news:2m77adFjrmccU1@uni-berlin.de...
> 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.

Turing Thesis (my text gives no credit to Church):
Any computation that can be carried out by mechanical
means can be performed by some Turing Machine.

This seems to agree much more with what I said, than wht you said.

> this may seem like begging the question to you, since you
> have not accepted the proof that every one else accepts, but

It is not merely that I have not accepted a proof that everyone
else accepts. It is that my disprove of this proof has not yet
been found in error. If you think that any of the refutations of
my refutation were valid, then state which one(s). I have
found serious flaws in everyone of them.

> by your previous statement (that adding a "screen" and
> "protected memory" adds no power, to which I agree) this is

Not necessarily. The Halting Problem might not be solved
without them.

> 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)

Protected memory might be construed as beyond the capabilites
of a TM.

> 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.

It is not meant to be convincing. Its meant to be a simple statement of
fact. If you change the form of the WillHalt() function such that its caller
has no possible access to its result, then the original Halting Problem
can not possibly be constructed. It really just as simple as that.

> --
> Mitch Harris
> (remove q to reply)
>

Relevant Pages

  • 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: Can you find anything wrong with this solution to the Halting Problem?
    ... You DON'T KONW SHIT about the original problem! ... this was only framed within the context of a Turing Machine because ... Turing published his result about the Halting problem in 1936. ... formalisms does NOT excuse YOUR introduction of formalisms ...
    (sci.logic)
  • 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. ...
    (sci.logic)
  • 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
    ... > Peter Olcott wrote: ... >> and protected memory to a computer does not make it more ... except that this might solve the Halting Problem. ... Your program can model any Turing Machine, ...
    (comp.theory)