Peter Olcott's Source of Confusion

From: Daryl McCullough (daryl_at_atc-nycorp.com)
Date: 06/27/04 

Date: 27 Jun 2004 09:54:22 -0700

Peter Olcott is so thoroughly confused by the proof of the
unsolvability of the Halting Problem, and it's very difficult
to track down exactly what the source of his confusion is.
The proof is completely trivial, and it's hard to see how
anyone could possibly be confused by it. But Peter manages
to be confused, no matter how many times it is explained to
him.

Here's my latest hypothesis: He doesn't understand, in the
informal descriptions of the proof, that the counterexample
program is a program *template*. It's not a complete program.
It's a fragment of a program such that, if you plug in the
code for an alleged program H that solves the halting problem,
the result is a program for which H gives the wrong answer.
The counterexample is *not* a universal counterexample---each
attempt at writing a Halt program gives rise to its own
counterexample.

It's like the proof that there is no largest number. You assume
that N is the largest number, and then you construct the number
N+1, which is larger than N. N+1 is *not* a number, it is a template
for a number: you tell me what N is, and I'll give a number, that
is larger than N.

The counterexample to the halting problem works the same way.
You tell me the code for a program H, and I tell you a question
about halting that H fails to give the correct answer to.

I think this is where Peter is confused. People write the
counterexample program like this:

    Q(x) : If Halts(x,x) then loop forever, otherwise halt

Peter thinks that that means "If program x halts when given
input x, then loop forever, otherwise halt". It doesn't mean
that. A computer program cannot branch based on the truth
of an arbitrary statement, it can only branch based on the
value of a *computable* expression. So Q above is not a
single program, it is a program *template*: You give me
the code for a program Halts, and I will use that code
to create a corresponding program Q.

Maybe it would be clearer to Peter if we made it explicit
that there is a *different* program Q for each purported
program Halts:

    Q_H(x) : If H(x,x) then loop forever, otherwise halt

I think it is clear that for any total program H that takes
two strings and returns a boolean, there is a corresponding
program Q_H and a corresponding string q_h (the code
for Q_H) such that

     Q_H(q_h) halts if and only if H(q_h,q_h) = false

So for every program H, there is a corresponding question:
"Does Q_H halt when given its own code as input?" for which H
gives the wrong answer.

That doesn't mean that the question *has* no correct answer.
It's just that *H* doesn't give the correct answer.

I can easily write a new program, H2, that gives the correct
answer to the question correspongin to program H. So H's question
isn't *universally* unsolvable, it is only unsolvable by *H*.
H2 has its own counterexample, Q_H2, and its own corresponding
question that it can't answer:

  "Does Q_H2 halt when given its own code as input?" 

--
Daryl McCullough
Ithaca, NY

Relevant Pages

  • Re: Alan Turings Halting Problem is incorrectly formed
    ... Peter is mixing up several things. ... Now the question (Halting problem) actually is not "Does TM M halt on ...
    (sci.logic)
  • Re: Can you find anything wrong with this solution to the Halting Problem?
    ... Peter> LoopIfHaltswill halt. ... Peter> LoopIfHalts() does not halt, this only leaves UNKNOWN, ... have any such program that can return UNKNOWN for any valid input ... the simplest solution to the halting problem "int WillHalt(string Src, ...
    (comp.theory)
  • Halting Problem: Give up
    ... The following is one of latest messages of Peter in comp.lang.c++ ... Halting Problem is and what the Proof is and how they are connected. ... >> and in a deterministic way determine if all algorithms ever come to an halt. ... >> cannot be correctly analyzed by this assumed algorithm. ...
    (comp.theory)
  • Re: Can you find anything wrong with this solution to the Halting Problem?
    ... Peter> way to construct a solution to the Halting Problem that can ... Peter> not possibly succeed. ... it cannot be a correct solution to the halting problem, ... machine you gave to neither halt sometime nor never halt. ...
    (comp.theory)
  • Re: Disproof of the Halting Problems Conclusion
    ... Peter> the computer making the program not run correctly. ... But as long as you modify your program correctly, ... Halting problem: once you know that the halting problem of Turing ... Turing machine) cannot be solved using anything with no stronger power ...
    (comp.theory)