Re: Yet another Attempt at Disproving the Halting Problem

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

Date: Fri, 30 Jul 2004 05:30:31 GMT

This is most likely the post that is causing Peter's
reading comprehension a challenge. Allow me to clarify:

Marc Goodman wrote:
> Peter Olcott wrote:
>
>> First of all this is flatly incorrect. The Halting Problem does not
>> say that a Halt Analyzer can not ever exist.
>
>
> Yes it does. It most definitely does say that a Turing Machine
> that correctly decides whether any other Turing Machine and
> input string correctly halts cannot exist. Learn the proof.

By "any other" I mean "all," not "some."
Compare and contrast these two sentences:

"Any even integer is divisible by 2." - "Any" is used in the sense of
"For all X, if X is an even integer, then X is divisible by
2"

VS.

"Are there any schools that teach computer theory?" - "Any" is used
in the sense of "does X exist such that X is a school and
X teaches computer theory."

The meaning of the above sentence was:

"The proof of the halting problem most definitely does say that
a Turing Machine cannot exist that correctly decides whether
X halts, for all X, where X is a Turing Machine and input string."

I can't help but feel that if you understood the proof we were
talking about, this fairly simple point would not have caused
you such a difficulty. Or, are you _deliberately_ looking for
things to misunderstand in order to keep this discussion going?

>
> All that it says is that
>
>> under certain weird circumstances it would not produce the correct
>> results.
>
>
> No it doesn't. Read. Learn. Understand. Evolve.
>
> I will wait and see if you can get past that before I proceed.
>

Relevant Pages

  • Re: Peter Olcotts Source of Confusion
    ... >> see if a Turing machine M halts on input x. ... >would solve the Halting Problem sure seems like pure malarkey. ... Processing speed is irrelevant as long as there is some lower bound ...
    (sci.logic)
  • Re: Partial recursive functions and minimization
    ... Suppose that T is a Turing Machine. ... Then G is partial recursive if and only if the halting problem for T ... whether or not T halts on x. Stated this way, ... since it contradicts the undecidability of the Halting Problem. ...
    (sci.math)
  • Re: Gödel, Turing, and Cantor
    ... >1) Gödel's incompleteness theorem ... >machine for which the halting problem is undecidable. ... Turing machine #n [in an appropriate ... finitely many steps that the Turing machine performs until it halts]. ...
    (sci.math)
  • Re: Yet another Attempt at Disproving the Halting Problem
    ... The Halting Problem does not ... It most definitely does say that a Turing Machine ... X halts, for all X, where X is a Turing Machine and input string." ...
    (sci.logic)
  • Re: Yet another Attempt at Disproving the Halting Problem
    ... The Halting Problem does not ... It most definitely does say that a Turing Machine ... X halts, for all X, where X is a Turing Machine and input string." ...
    (comp.theory)