On Sunday, 1 August 2021 at 13:41:25 UTC+1, Ben Bacarisse wrote:
Malcolm McLean <malcolm.ar...@gmail.com> writes:Consider this. H_Cap (similar to H_Hat but missing the invert step);
However the reasons PO's halt decider fails on H_Hat(H_Hat) have gotI don't follow. H_Hat(H_Hat) halts because H(H_Hat, H_Hat) == 0 making
nothing to do with the invert step of Linz' proof. This is maybe interesting,
but in a small way, it's not a revolutionary result which will turn computer
science upside down. But it's maybe worth mentioning.
that result the wrong one. If H(H_Hat, H_Hat) returned non-zero,
H_Hat(H_Hat) would not halt, making that the wrong result. Whilst I
don't like this sort of language, H fails on H_Hat(H_Hat) precisely
because of how H_Hat is constructed from H.
H_Cap(I)
{
return H(I, I):
}
Now if H is a "simulating halt decider" it must get this wrong. H is (skeleton
code)
H(I, I)
{
while(true)
{
Step(I, I);
if (tightloopdetected())
return Non_Halting;
else if (haltsofitsownaccord)
return Halting;
}
}
The question is how we write the function tightloopdetected(). If it returns true then H(H_Cap, H_Cap) the H(H_Cap, H_Cap) will terminate. If
it returns false, it wlll not. So H can never make the right decision for H_Cap(H_Cap).
We've elimiated the "invert the result" step from Linz's proof. We have to insist that H is a "simulating halt decider" to achieve this. But that seems to be a reasonable condition. We know there are many properties of Turing machines that cannot be determined other than by stepping them.
Sysop: | Keyop |
---|---|
Location: | Huddersfield, West Yorkshire, UK |
Users: | 365 |
Nodes: | 16 (2 / 14) |
Uptime: | 77:24:57 |
Calls: | 7,775 |
Calls today: | 1 |
Files: | 12,911 |
Messages: | 5,750,026 |