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

From: Peter Olcott (olcott_at_worldnet.att.net)
Date: 08/20/04 

Date: Fri, 20 Aug 2004 02:30:09 GMT

"Daryl McCullough" <daryl@atc-nycorp.com> wrote in message news:cg2d1v04uj@drn.newsguy.com...
> Mitch Harris says...

> Peter is specifically talking about this method (diagonalization):

I really want to learn this, so don't take my critical comments to heart.

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

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

> 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,
as long as it is agreed that such details could not present
an impossibility problem. A dozen people were all certain
that No TM could possibly ever have access to its invocation
context. these details were salient and provided.

> The problem is that we would like to be able to prove the
> result for *any* sensible model of computation, and for

That is not at all required to prove my case. That it works
in one instance is completely sufficient to prove a positive.

> *any* sensible convention for inputs and outputs, and for
> *any* sensible coding scheme. But we can't, because we
> can't formalize the notion of a model or convention or
> coding scheme being "sensible". At this point, we have
> to rely on something like the Church-Turing thesis, that
> any sensible way of formalizing computation gives the same
> set of computable functions. So if there is no solution for
> Turing machines with the standard conventions for input/output
> and the standard coding scheme, then there is no solution,
> period.
>
> But that is exactly what Peter is disputing. I *think* that
> he agrees that there is no standard Turing Machine program
> that solves the halting problem, with the standard conventions.
> But he thinks that this result is an artifact of those
> conventions. He keeps proposing *different* conventions,
> and keeps pointing out that the standard proof doesn't
> apply to these new conventions. He's right. The proof
> was written for a specific set of conventions, and it
> doesn't apply directly in other cases. That doesn't
> mean that the halting problem is solvable in the new
> paradigm, it just means that there hasn't been a rigorous
> proof one way or the other.

I have correctly refuted the one case that defined the
undecidability of the Halting Problem. 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.

George Greene put this very succinctly, (paraphrase)
a mathematical function can not refuse to return a result.
It was this lack of 1-1 mathematical mapping between
the mathematical abstraction of a Turing Machine, and
the Turing Machine itself, that made the math version
blind to the solution.

> What Peter doesn't seem to realize is that he is *really*
> attacking, not the proof of the unsolvability of the Halting
> Problem, but *Church's* thesis. If some other model of
> computation allows something to be computed that is not
> computable by ordinary Turing machines with the ordinary
> conventions, then that shows that Church's thesis is wrong.
>
> If there weren't already enough Peter Olcott threads, I would
> suggest that he change his subject to "Refuting Church's
> Thesis".
>
> --
> Daryl McCullough
> Ithaca, NY
>

Relevant Pages

  • 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: [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. ...
    (comp.theory)
  • 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: Refutation of the Halting Problems Proof (Clarifications Wanted)
    ... > every existing proof of the Undecidability of the Halting Problem. ... "halt analyzer" is a term you need to define, ... TMs don't return results to other TMs. ... "Since returning the result back to the Turing Machine being analyzed is ...
    (comp.theory)
  • Re: [PO] Re: Refutation of the Halting Problems Proof (Clarifications Wanted)
    ... > every existing proof of the Undecidability of the Halting Problem. ... "halt analyzer" is a term you need to define, ... TMs don't return results to other TMs. ... "Since returning the result back to the Turing Machine being analyzed is ...
    (sci.logic)