|
|
![[parent]](http://images.planetmath.org:8080/images/uparrow.png) Viewing Message
|
|
|
| ``Re: Self reference''
by John Allsup on 2005-02-17 09:55:19 |
|
| To elaborate:
The current Break algorithm reads:
Break(x) {
if Halt(Break,x) then
while true do nothing
else
return true
fi
}
modify it to:
Break(x) {
if IsValidCode(x) and Halt(x,x) then
while true do nothing
else
return true
fi
}
This no longer references itself. Let Break be some encoding of the
program Break(x). Consider Break(Break). IsValidCode(Break) is certainly true. Now if Halt(Break,Break) is true then Break(Break) gets stuck in the while loop, so doesn't halt. If Halt(Break,Break) is false, then the if branches to the return true statement and the Break(Break) halts after all. Thus the given program Halt(x,y) is not a solution to the halting problem (since it gives the wrong result for the particular case of Break given above.)
|
| | [ reply | up | top ] |
|
|
|
|
|
|
