Re: Halting test example [ Correct refutation of Peter Linz proof ](Kaz)

[olcott]

On 12/5/2020 7:58 AM, Malcolm McLean wrote:
> On Saturday, 5 December 2020 at 11:50:11 UTC, Kaz Kylheku wrote:
>>
>> It's obvious that we can run all the halt-deciding calculation in a
>> monitored machine which will stop it under various conditions like "loop
>> detected" or "too many instructions executed" or whatever we like.
>> But in all such cases, the halt-deciding calculation has failed to
>> decide. The function H has not terminated with a true or false return
>> value, as required.
>>
> Yes. But the first point is that it is reasonable to run all programs under
> a simulator which terminates them when a tight infinite loop is detected.
> That's not really a computational theory argument, but it sets the scene.
> What PO is doing is not necessarily contrived.
>
> Additonaly, the supervisor is the same as "Halts". That muddies the waters
> even more, but doesn't fundamentally change things.
>
> The second point is that, if everything is being run under a supervisor,
> "Halts" can return a value to main when run directly, but be aborted by
> the supervisor when called from H_Hat. You'd have to write the supervisor
> carefully to avoid making it too obvious that this step is contrived, but the
> Linz challenge could be met.
>
> In a sense. Of course it is a cheat. But it's a new cheat, and that's all that
> any sensible person would ever have expected from these threads.
>

This is not any sort of a cheat what-so-ever it is a direct refutation
of the Peter Linz halting problem undecidability proof:

void H_Hat(u32 P)
{
u32 Input_Halts = H(P, P);
if (Input_Halts)
HERE: goto HERE;
else
HALT
}

int main()
{
Input_Halts = H((u32)H_Hat, (u32)H_Hat);
Output("H_Hat(H_Hat) Halts =", Input_Halts);
HALT;
}

Linz, Peter 1990. An Introduction to Formal Languages and Automata.
Lexington/Toronto: D. C. Heath and Company.

http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf


--
Copyright 2020 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein