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

From: Owen Jacobson (angstrom_at_lionsanctuary.net)
Date: 08/22/04 

Date: Sun, 22 Aug 2004 07:14:14 GMT

On Sun, 22 Aug 2004 04:01:08 +0000, Peter Olcott wrote:

> "Daryl McCullough" <daryl@atc-nycorp.com> wrote:
>
>> Peter Olcott says...
>>
>> >"Daryl McCullough" <daryl@atc-nycorp.com> wrote
>> >
>> >> 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?
>
> There is only one way to make it undecidable. This is a TM such as
> LoopIfHalts. This TM makes sure that it does whatever the opposite is of
> what Halt determines. If Halt determines that it will halt, then it goes
> into an infinite loop. If Halt determines that it will not halt, then it
> halts. If Halt makes sure that it is never invoked as a part of the
> execution of another TM, then whenever Halt is provided a TM such as
> LoopIfHalts, Halt can conclusively determine that it halts. Undecidability
> has been refuted. There are no more instances that are undecidable.

Are you sure? How are you sure? Nobody has proved that there are no
other cases that are unanalyzable by Halt(M, x) ==> {0, 1}. Finding a
single unanalyzable case was sufficient to demonstrate that no TM could be
Halt(M, x) for all possible values of M and x..

In order to claim that there are no other cases that cannot be analyzed,
you'll have to provide a proof that this is true.

(I strongly suspect that most programs that contains Halt(M, x) (calls it,
or contains it inline; they're the same) are unanalyzable by Halt(M, x).)

>> >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.
>
> The problem is not that the standard proof does not apply in my case.
> The problem is that the standard proof applies to hypothetical
> abstractions of Turing Machines, and not actual working hardware.

A Turing machine is a mathematical concept only. No physical machine can
have a truly infinite amount of storage (tape), yet this is part of the
definition of a Turing machine. The computer on your desk that you're
reading this post on is not a complete Turing machine. It can run only a
subset of all possible programs: the subset that can be fit into it's
memory and disk space. While this is a very large subset, the set of all
possible Turing machines is not finite.

>> 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.
>
> The "usual conventions" part is the error on your part. If we assumed
> that the "usual conventions" part was literally true, then every video
> game completely refutes the Church-Turing thesis. The idea is that the
> "usual conventions" can be stretched to include video output, rather
> than strictly adhered to thus refuting Church-Turing.

All of the computations in every video game ever created can be performed
on Turing machines -- even the computations involved in 3D rendering and
sound generation. That we see pictures instead of streams of tape symbols
is a consequence of an agent external to the Turing machine -- your video
processor and montior -- that can examine the contents of a section of the
machine's storage -- video memory. Similarly for sound.

Furthermore, nobody has ever proven the Church-Turing thesis -- so any
assertions based on it are necessarily conditional on the thesis' validity. 

-- 
Some say the Wired doesn't have political borders like the real world,
but there are far too many nonsense-spouting anarchists or idiots who
think that pranks are a revolution.

Relevant Pages

  • Re: [PO] Re: Proving a negative is hard
    ... If Halt determines that it will halt, ... Undecidability ... > abstractions of Turing Machines, ... >> paradigm applies to the new paradigm. ...
    (comp.theory)
  • Re: Largest provable BB(N)?
    ... If you define BB in terms of number of steps needed to halt, ... |And by "provable" I mean within the scope of known mathematics... ... and nonhalting of exactly the same Turing machines as ZFC can. ... Some of their favorite additional axioms are known as "higher axioms ...
    (sci.math)
  • Re: What is the Result from Invoking this Halt Function?
    ... No, it forms a logical contradiction, thus proving that WillHalt (a ... program that determines whether or not an arbitrary program halts) ... The concept of a halt analyser has to be applied to ... Turing Machines, standard C++ with particular implementation defined ...
    (sci.logic)
  • Re: What is the Result from Invoking this Halt Function?
    ... No, it forms a logical contradiction, thus proving that WillHalt (a ... program that determines whether or not an arbitrary program halts) ... The concept of a halt analyser has to be applied to ... Turing Machines, standard C++ with particular implementation defined ...
    (comp.theory)
  • Re: [PO] Re: Proving a negative is hard
    ... If you make this assumption then eliminating the undecidability ... opposite is of what Halt determines. ... The "usual conventions" part is the error on your part. ... Assuming that the Halt Analyzer has a tape, ...
    (comp.theory)