Re: The proof that I was referring to is on the website
From: Mitch Harris (harrisq_at_tcs.inf.tu-dresden.de)
Date: 08/01/04
- Next message: Mitch Harris: "Re: Foundation for a Formal Refutation of the Original Halting Problem?"
- Previous message: Simon G Best: "Re: Foundation for a Formal Refutation of the Original Halting Problem?"
- In reply to: Peter Olcott: "Re: The proof that I was referring to is on the website"
- Next in thread: Peter Olcott: "Re: The proof that I was referring to is on the website"
- Reply: Peter Olcott: "Re: The proof that I was referring to is on the website"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: 1 Aug 2004 19:38:00 GMT
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).
>> >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?
>(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.
>> >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
- Next message: Mitch Harris: "Re: Foundation for a Formal Refutation of the Original Halting Problem?"
- Previous message: Simon G Best: "Re: Foundation for a Formal Refutation of the Original Halting Problem?"
- In reply to: Peter Olcott: "Re: The proof that I was referring to is on the website"
- Next in thread: Peter Olcott: "Re: The proof that I was referring to is on the website"
- Reply: Peter Olcott: "Re: The proof that I was referring to is on the website"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
