Re: The proof that I was referring to is on the website

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

Date: Mon, 02 Aug 2004 01:35:05 GMT

"Mitch Harris" <harrisq@tcs.inf.tu-dresden.de> wrote in message news:2n4v4nFs755lU1@uni-berlin.de...
> Peter Olcott <olcott@worldnet.att.net> wrote:
> >
> >"Mitch Harris" <harrisq@tcs.inf.tu-dresden.de> wrote in message
> >>
> >> You're really stuck on this "void" thingy. How can returning a result
> >> be an error?
> >
> >When you are returning the result to a function that changes its behavior
> >based on this result, which changes the result, then it is an error
> >to return
> >this result.
>
> Yes, it -would- be an error if -you- or some other reader of the proof
> then took the changed result to -be- the correct result. But that is
> not what is happening in the proof. The output is being used to create
> -another- TM, -not- the halting function, but -another- TM, (this
> other TM happens to have contradictory behavior).

It does not have contradictory behavior. It merely prohibits the
Halt function form returning its result to this TM.

http://www.netaxs.com/people/nerp/automata/halting2.html
Here is the incorrect conclusion that this link provides:

"This machine, when applied to itself, goes into an infinite loop if
and only if it halts when applied to itself. This is impossible."

If this conclusion was actually true, then you would get the case of
an object requiring mutually exclusive properties, thus it couldn't
possibly exist. This conclusion is not true.

It does not go into an infinite loop if and only if it halts.
It goes into an infinite loop if and only if it DETERMINES THAT IT halts.

If we assume a halt analyzer that has the equivalent intelligence of a human,
then IT WOULD NOT DETERMINE THAT IT HALTS. It would not
make this determination, because it could see that this determination would
immediately be contradicted by the program, LoopIfHalts. So it merely
refrains from making this determination.

So what we are left with is a program that halts, yet can not report this
fact to its calling program. Either I am correct in this or you can find
the specific execution trace point where I err.

No one has ever attempted to do this. Every refutation of this point
has always been the form of one empty unsupported assertion or
another. (or several) The reason that these assertions are not more
precisely targeted at my specific error, is simply that I did not err.

> >> >How about this analogy. What is school teachers
> >> >gave all of their students report cards with the grades written
> >in pencil.
> >> >The instructions would be "if you don't like your grade, then erase it
> >> >and put in a grade that you do like." Would this in any possible way
> >> >change the accuracy of the assessment of the student's performance?
> >>
> >> Correct, changing the grade as written on paper doesn't change what
> >> the true assessment is. But that's what makes your analogy
> >
> >What if whatever grade ended up on the report card was considered
> >the final say in this matter? A kid that never does any work, never pays
> >any attention, doesn't even put his name on any test, actually gets straight
> >A's because that is how the system is defined.
>
> Yes. I agree that would be wrong.
>
> >This is how the Halting Problem is defined.
>
> No, it is not. The constructed TM is not intended to be a new halting
> TM (one whose output is supposed to be identical to the output of the
> original hypothesized TM).
>
> >> inappropriate for the diagonalization proof. In Turing's proof, the
> >> construction depends directly on the outputs of the hypothesized halt
> >> machine.
> >
> >Two things might occur here:
> >(1) The diagonalization proof abstracts out key details that allow a correct
> >conclusion to be formed.
>
> abstracts out? as in removes or as in uses?
Rmoves key details.

> >(2) My reasoning can be applied to the diagonalization proof, thus
> >refuting this form as well.
>
> The analogy is ill-formed, so any reasoning implicit in it doesn't
> work.

It is not the analogy that is crucial. The analogy was just to help you see the
problem. The actual problem itself is allowing the program being analyzed
access to the results of the analysis such that it can changes its behavior,
and thus change the analysis.

They have a specific term for this error. It violates one of the principles of the
scientific method. Something like incorrect isolation of the independent variable
from the dependent variable.

> >> >In the same way that creating report cards with grades written in
> >> >pencil is an error, so is returning the result of the halt
> >analysis to the
> >> >program being analyzed, an error.
> >>
> >> That analogy doesn't work (or is not explicit enough). It very much
> >> depends on how the erasing and rewriting are done. In one case, a
> >> rewriter might just rewrite good grades. That means the rewriter is
> >
> >In any case it does screw up the ability of the teacher to provide
> >accurate asseseement of student performance.
>
> Yes.
>
> >We could have a
> >whole new problem (exactly?) analogous to the Halting Problem.
>
> No. The analogy just doesn't work.
>
> >It is impossible for any teacher to provide reasonably accurate
> >assessment of student performance because it would be possible
> >to return report cards with the grades written in pencil, such that
> >the student's could determine their own grades.
>
> Right.
>
> >I am not sure that this analogy is perfect. There might be places where
> >it fails to correspond to the Halting Problem such that the analogy
> >fails to accurately represent one or more key aspects of the Halting
> >Problem.
>
> Well, there are large swaths of the concepts involved in the HP proof
> that are key, but are not touched by your analogy of rewriting.
>
> >At this time, this does seem to essentially represent all of the
> >key aspects of the Halting Problem accurately.
>
> No, it doesn't. The properties of the diagonalized function depend
> directly on the properties of the halting function. In yours the
> final grades are arbitrarily chosen by the student and don't depend on
> whatever the teacher wrote originally.
>
> Mitch
>

Relevant Pages

  • Re: The proof that I was referring to is on the website
    ... The analogy is ill-formed, so any reasoning implicit in it doesn't ... >> rewriter might just rewrite good grades. ... >whole new problem analogous to the Halting Problem. ... but are not touched by your analogy of rewriting. ...
    (comp.theory)
  • Re: The proof that I was referring to is on the website
    ... The analogy is ill-formed, so any reasoning implicit in it doesn't ... >> rewriter might just rewrite good grades. ... >whole new problem analogous to the Halting Problem. ... but are not touched by your analogy of rewriting. ...
    (sci.logic)
  • Re: The proof that I was referring to is on the website
    ... It does not go into an infinite loop if and only if it halts. ... >>This is how the Halting Problem is defined. ... It is not the analogy that is crucial. ... >>the student's could determine their own grades. ...
    (sci.logic)
  • Re: The proof that I was referring to is on the website
    ... >>gave all of their students report cards with the grades written in pencil. ... > That analogy doesn't work. ... > rewriter might just rewrite good grades. ... whole new problem analogous to the Halting Problem. ...
    (sci.logic)
  • Re: The proof that I was referring to is on the website
    ... >>gave all of their students report cards with the grades written in pencil. ... > That analogy doesn't work. ... > rewriter might just rewrite good grades. ... whole new problem analogous to the Halting Problem. ...
    (comp.theory)
Loading