Re: [PO] Re: Proving a negative is hard

From: Daryl McCullough (daryl_at_atc-nycorp.com)
Date: 08/20/04 

Date: 20 Aug 2004 08:09:22 -0700

Peter Olcott says...

>"Daryl McCullough" <daryl@atc-nycorp.com> wrote

>> 1. Assume there is a program H(x,y) that returns true if
>> x is a code for a program that halts on input y, and returns
>> false otherwise.
>
>I would say that this is a false assumption.

That's correct. It is provably false that there is a program
H(x,y) that returns true if x is a code for a program that halts
on input y, and returns false otherwise. Glad you agree.

>
>> 2. Define Q(x) as follows: if H(x,x) then loop forever, otherwise halt
>>
>> 3. Consider Q(#Q) (where #Q means the code of Q). If it halts,
>> then it must be that H(#Q,#Q) = false, and so H gave the wrong
>> answer. If Q(#Q) doesn't halt, then it must be that H(#Q,#Q) = true,
>> and so again H gave the wrong answer.
>>
>> Peter's "solution" is to assume that H(x,y) behaves differently
>> depending on who is calling it. He's given two ways this could
>> work: (1) H(#Q) returns false when called at the "top level"
>> (that is, if a user is trying to evaluate H(#Q)), but refuses
>> to give any answer whatsoever if it is called from Q. (2) H(#Q)
>> returns true when called at the "top level" but returns some
>> value that is neither true nor false when called by Q.
>>
>> It's been pointed out to Peter that Q doesn't have to "call"
>> H. Instead, Q can simulate H, to figure out what *would* have
>> happened if H were called at the "top level". I can't remember
>> what Peter's answer to this is. Does he claim that it is *impossible*
>> for one program to simulate another program? Does he claim that
>> the *source* code for H can realize that it is being used in a
>> simulation, and return a different answer.
>
>I claim that this does not nearly meet the burden of proof
>requirements for a valid refutation of my method. The burden
>of proof requirement is that of proving a negative.

I'm not trying to refute your method, I'm trying to *understand*
it. *Why* do you believe that your method works?

>> Peter seems not to understand the distinction between
>> a mathematical theorem and the *interpretation* of that
>> theorem. To prove the unsolvability of the halting problem,
>> you have to
>>
>> 1. Pick a model of computation (for example, Turing machines)
>> 2. Pick a convention for inputs and outputs (for example,
>> the inputs could be one or more strings of nonblank symbols
>> on the tape, separated by blanks, and the output could be
>> the string of nonblank symbols after the machine has halted,
>> if it ever does)
>> 3. Pick a coding of machines as inputs.
>> 4. Prove for this computation model, and for these conventions
>> of inputs and outputs, and for this coding, that there is
>> no program H that takes as inputs strings x and y, and that
>> produces as output the string "1" if x halts on y, and "0"
>> otherwise.
>
>Specifying each of these details is not specifically required,

Yes, it is, if you want to analyze the question mathematically.

>I have correctly refuted the one case that defined the
>undecidability of the Halting Problem.

No, you haven't. That one case was about *Turing* machines,
with a very specific convention for inputs and outputs and
for coding programs as inputs. Your examples are all about
a *different* convention, and a *different* model for
computation. The standard proof doesn't apply in your case.
That doesn't mean that you have refuted the proof. If someone
proves something about elephants, it isn't a refutation to
show that the proof doesn't apply to cats.

If you introduce a new model of computation or a new convention
of how inputs and outputs are handled, then a lot of work is
involved to understand its relationship to the old paradigm.
You haven't done any of that work. Only *after* you understand
the relationship is it meaningful to ask whether a theorem about
the old paradigm applies to the new paradigm.

Of course, nobody (or at least nobody who actually has studied
computability theory) thinks that a new paradigm will make any
difference, because Church's Thesis (which hasn't been proved,
but has a lot of empirical evidence in its favor) implies that
the computing paradigm doesn't make any difference. If the halting
problem isn't solvable with Turing machines, with the usual
conventions, then it isn't solvable for any other paradigm.

That isn't a mathematical proof, but instead is a plausibility
argument.

>The reason that this worked was that for 68 years everyone
>assumed that the mathematical conception of this problem did not
>abstract out crucial salient details that would otherwise
>show that the undecidability does not exist.

No, that's completely incorrect. People have investigated
a dozen different models for computation, a dozen different
conventions for inputs and outputs. Some of these are: Register
machines (sort of like modern computers, with registers that
store integers), productions systems (rewrite rules for
expressions), the lambda calculus, Lisp, etc. No matter what model
of computation people have investigated, the same limitations
come up. The unsolvability of the halting problem shows up in
every model of computation in some variant.

You seem to think that you have come up with a new way of
thinking about the Halting problem. No, you haven't.

>George Greene put this very succinctly, (paraphrase)
>a mathematical function can not refuse to return a result.

Yes, of course a computer program can refuse to answer, in
some circumstance. If H(x,y) *ever* gives an answer, then
that answer can be recorded, and that recorded answer can
be used by another program. It isn't necessary for a program
to make a *call* on H in order for it to use the answers
provided by H. 

--
Daryl McCullough
Ithaca, NY

Relevant Pages

  • Re: [PO] Re: Proving a negative is hard
    ... To prove the unsolvability of the halting problem, ... Pick a coding of machines as inputs. ... and for these conventions ... involved to understand its relationship to the old paradigm. ...
    (sci.logic)
  • Re: [PO] Re: Proving a negative is hard
    ... and for these conventions ... > Turing machines with the standard conventions for input/output ... > he agrees that there is no standard Turing Machine program ... > that solves the halting problem, ...
    (comp.theory)
  • Re: [PO] Re: Proving a negative is hard
    ... and for these conventions ... > Turing machines with the standard conventions for input/output ... > he agrees that there is no standard Turing Machine program ... > that solves the halting problem, ...
    (sci.logic)
  • Re: What is the Result from Invoking this Halt Function?
    ... with the conventions that goes along with the proof. ... Peter seems to believe that the unsolvability of the halting problem ... of formalisms for computation (Turing machines, register machines, ...
    (sci.logic)
  • Re: [PO] Re: Proving a negative is hard
    ... Peter Olcott says... ... >> for a computer program to compute something). ... In terms of that paradigm, ... the halting problem is unsolvable. ...
    (comp.theory)