Re: Daryl, Dave, Barb and the Georges' source of Confusion

From: Chris Menzel (cmenzel_at_remove-this.tamu.edu)
Date: 07/06/04 

Date: 6 Jul 2004 16:09:08 GMT

On Tue, 06 Jul 2004 12:10:01 GMT, Peter Olcott <olcott@worldnet.att.net> said:
>
> "Arthur J. O'Dwyer" <ajo@nospam.andrew.cmu.edu> wrote in message
> news:Pine.LNX.4.58-035.0407052017160.25415@unix44.andrew.cmu.edu...
> ...
> Not in this case. In this case the program takes your answer and
> does just the opposite, just like in the original. The only big difference
> between my version and the original is that the set of individual
> humans also consistently fails to pass my Halting Problem test.
> http://home.att.net/~olcott/halts.txt
>
> > So it is not correct to say that no program can produce the
> > right answer to the single question "Does Q halt?" It is,
> > of course, correct to say that no program can produce the
> > right answers to *all* questions "Does P halt?" for *all*
> > programs P.
>
> But that is merely an impossible question,

*Where* is the impossible question? Do you not know that a sentence
containing a question is not necessarily a question? Here is what
Arthur said (slightly revised):

(1) No program can produce the right answers to all questions of
    the form "Does P halt on input I?" for all programs P and
    inputs I.

That is not a question. It is a declarative sentence wholly analogous
to:

(2) No number is greater than all prime numbers.

We know what programs are -- the set of programs (given a well-defined
programming language) is as completely well-defined as the set of
numbers. We know what it is for one program P* to produce a correct
answer to the question "Does P halt" for other programs P, just as we
know what it is for one number to be greater than another -- it is
trivial to construct examples. More generally, there are sets S of
programs {P1, P2, ...} such that there is a program H_S that correctly
answers the question "Does P halt on I?" for any input I for all the
programs P in S. In such a case, the following is entirely meaningful,
just demonstrably false:

(3) No program can produce the right answers to all questions of
    the form "Does P halt on input I?" for all programs P in S
    and inputs I.
 
But if (3) is obviously meaningful for some S, what basis could there
possibly be for denying it is meaningful for any S, in particular, for
the case where S is just the set S* of *all* programs, rather than a
some proper subset of them:

(4) No program can produce the right answers to all questions of
    the form "Does P halt on input I?" for all programs P in S*
    and inputs I.

(Clue: None.) But this is your "impossible question".

Chris Menzel

Relevant Pages

  • Re: Daryl, Dave, Barb and the Georges source of Confusion
    ... > does just the opposite, ... > But that is merely an impossible question, ... Arthur said: ... answers the question "Does P halt on I?" ...
    (comp.theory)
  • Re: Peter Olcotts Source of Confusion
    ... of the empty set. ... In either case HALT() would give the w r o n g answer. ... Merely an impossible question, thus an incorrect question, ... It is like rejected CAD software as ...
    (sci.logic)
  • Re: Peter Olcotts Source of Confusion
    ... "Peter Olcott" wrote in ... >> The question IS whether the program does or doesn't halt ON ... > If you quit trying so hard to refute me, ... But it's not an impossible question, ...
    (sci.logic)
  • Re: Alan Turings Halting Problem is Incorrect (FINAL PART)
    ... > Does program P halt on input q? ... > is not an incorrect question, since there's certainly a correct answer ... Either is halts or is doesn't forms the CECE ... It forms an impossible question, ...
    (sci.logic)
Quantcast