Re: Exactly how the Peter Linz H correctly decides H_Hat

[olcott]

On 11/5/2020 8:50 PM, Ben Bacarisse wrote:
> olcott <No...@NoWhere.com> writes:
>
>> The correctness of any decider or partial decider can only be
>> correctly measured against the decision criteria of this decider or
>> partial decider.
>
> "It should do what it should do".
>
>> Any intuition to the contrary is necessarily incorrect.
>
> "Any idea that is shouldn't do what it should do is wrong".
>
>> All of the halting decisions of a partial halt decider that:
>> (a) Executes its input a single state transition at-a-time.
>>
>> (b) Stops the execution of all inputs that it decides would not
>> otherwise terminate: DOES_NOT_HALT
>>
>> (c) Allows the remaining inputs to continue until they terminate:
>> HALTS
>
> You have constrained your partial halt decider here. You have forced all
> the incorrect results into the (b) category (not that that matters).
>
>> Are necessarily correct for every computation that it correctly
>> decides to stop and every computation that it does not decide to stop
>> that terminates.
>
> That sounds like it's correct if it's correct. It would be clearer if
> you just said when you permit you partial decider to be wrong. But
> again, it doesn't matter because you consider only one case below.
>
>> Now we apply this principle to the Peter Linz H_Hat:
>>
>> void H_Hat(u32 P) // (bottom of page 319)
>> {
>> if (Aborted_Because_Non_Halting_Behavior_Detected(P, P))
>> HALT
>> else
>> HERE: goto HERE;
>> }
>>
>> // Linz calls this H (page 318)
>> bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I);
>
> No. Linz's H is not a partial halting decider. And Linz's H is
> supposed to be a Turing machine, not a function in some pseudo-code with
> a notion of "aborting". And Linz's H has a single string encoding a
> computation as its input. There are more differences than similarities.
>
> You should re-phrase the halting problem in terms of your chosen model
> of computation.
>
>> http://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
>>
>> Linz, Peter 1990. An Introduction to Formal Languages and Automata. Lexington/Toronto: D. C. Heath and Company.
>>
>> According to the above definition of a partial halt decider:
>> bool Aborted_Because_Non_Halting_Behavior_Detected(u32 P, u32 I);
>> correctly decides halting for the Peter Linz H_Hat
>
> I think you mean your H_Hat above because Linz's H^ is a Turing machine.
> And H_Hat is not something you can decide halting for (even incorrectly)
> because it's not a computation. You mean (or should mean) that the
> function with a silly name correctly decides halting for
>
> H_Hat(H_Hat)
>
> i.e. that Aborted_Because_Non_Halting_Behavior_Detected(H_Hat, H_Hat) is
> false if H_Hat(H_Hat) is a halting computation and true otherwise.
>
>> because within this definition of a partial halt decider the invocation of:
>> Aborted_Because_Non_Halting_Behavior_Detected(P, P);
>> would be infinitely recursive unless the halt decider terminates the
>> execution of H_Hat according to clause (b) of this definition.
>
> That's the least such a naive partial halt decider should do (more
> sophisticated ones might not need to emulate the given computation at
> all), but it's not enough to get the right answer. You won't be able to
> see that, though, unless you know what the right answer is, and despite
> the fact that you said you did know, I don't think you do. Do you know
> what the right answer is?
>
> But why do you care? A partial halt decider is allowed to get some
> instances wrong, so why worry about this particular one?
>

That I defined a partial halt decider that does correctly decide H_Hat
when H_Hat is in the Linz specified relation to its halt decider is self
evident from the original post.

To make it clear that H_Hat really is stuck in infinite recursion we
discard all of the halt deciding of H() and simply DebugTrace(H_Hat,
H_Hat);


void H_Hat(u32 P) // (bottom of page 319)
{
if (H(P, P))
HALT
else
HERE: goto HERE;
}


u32 H(u32 P, u32 I)
{
return DebugTrace(P, I);
}


int main()
H(H_Hat, H_Hat);



--
Copyright 2020 Pete Olcott

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