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

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

Date: Sun, 01 Aug 2004 17:44:07 GMT

"Mitch Harris" <harrisq@tcs.inf.tu-dresden.de> wrote in message news:2n43aaFrq0ucU1@uni-berlin.de...
> Peter Olcott <olcott@worldnet.att.net> wrote:
> >
> >So by showing that one program can be screwed up,to produce
> >incorrect results, we conclude that this program (even producing
> >incorrect results) can not possibly exist. Since this program was
> >build from modifying another program, we also conclude that
> >the program used as a basis for this program can not exist.
>
> uh yeah sort of. it depends on what you mean by "screw up".
>
> >It sure does not seem to hook up correctly.
> >Maybe it just isn't clicking that returning the results of the analysis
> >is actually an error.
>
> 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.

> >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. This is how the Halting
Problem is defined.

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

(2) My reasoning can be applied to the diagonalization proof, thus
refuting this form as well.

> >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. We could have a
whole new problem (exactly?) analogous to the Halting Problem.
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.

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. At this time, this does seem to essentially represent all of the
key aspects of the Halting Problem accurately.

> essentially ignoring the original. In another case the rewriter might
> switch grades good for bad and bad for good. If we knew that the
> rewriter was this sor, we could compute the originally assessed grade.
>
> And anyway, none of this modification (in the analogous world of
> grades) says anything about the possibility of truth of the original
> assessment.
>
> Mitch
>

Relevant Pages

  • 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
    ... 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
    ... 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
    ... 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. ...
    (comp.theory)
  • 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)