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

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

Date: Sun, 22 Aug 2004 04:01:08 GMT

"Daryl McCullough" <daryl@atc-nycorp.com> wrote in message news:cg54720302i@drn.newsguy.com...
> 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.

If you make this assumption then eliminating the undecidability
of the Halting Problem is not possible. If you do not make this
assumption the deciding whether or not each and every element
of the set of all TM's is not undecidable. Whenever I make any
assumptions, I try very hard not to make any arbitrary assumptions
that block my path to a solution.

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

> >> 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 don't think that it is even required mathematically.
If there exists only a single form of TM that is undecidable, and
a method is provided such that this TM can now always be decided,
all of the other details instantly become moot.

> >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.
It applies to a concept of a Turing Machine, and not the Turing Machine
itself.

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

None of this is required. There is one instance that defines
undecidability. I have refuted this one intance, Done!

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

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

Yet not a one of them ever thought about even the possibility
of selectively refraining from providing a result. That is why
they failed, and I succeeded.

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

That was very good. That was the closest attempt to refuting my
current method. I thought it through off and on all day today. I
concluded that I could categorically eliminate the possibility of
this presenting any problem, yet would be required to add back
in a point that was brought up from one of my earlier methods.

Assuming that the Halt Analyzer has a tape, just like any other
TM. The tape holds three different symbols, ZERO, ONE, and
SPACE. (I like this definition the best). I like it the best because
a number of any length can be easily represented. This allows
the tape locations to be numbered consecutively starting with one.

Here is the specific additional slight augmentation: We reserve the
first location of the Halt Analyzer's tape for the value of TRUE, it
must be either ZERO or ONE. As soon as the Halt Analyzer is
done processing it writes the answer to its halt analysis in its own
tape location TWO, and it writes a space to tape position ONE.
The human user is responsible to provide the initialization value
that is defined to mean TRUE. Because of this TM's such as
LoopIfHalts will have access to the return value of the Halt
Analyzer after it complete processing, yet will not have access
to the meaning of this value.

If we combine this with the augmented UTM method, then there
is no possible way left for LoopIfhalts to define undecidability.

> --
> Daryl McCullough
> Ithaca, NY
>

Relevant Pages

  • 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)
  • Re: Alan Turings Halting Problem is Incorrect (PART-THREE)
    ... >>or not should not accept as input TMs that neither halt nor not halt? ... but you maintain that the concept of undecidability is itself ... halting problem is reducible to it (you can solve the halting problem ... problem (that's my way of formalizing "is this program correct?" ...
    (sci.logic)
  • 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. ...
    (sci.logic)
  • 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: Smaller UTM than Rule110
    ... cater to your obsessions, not mine. ... > specified mark at a specified point on the tape. ... include the enhancement of an oracle that is aware ... What makes you think the tape has _room_ for a halt ...
    (comp.theory)