XPost: comp.theory, comp.ai.philosophy, comp.software-eng

On 11/5/2020 8:50 PM, Ben Bacarisse wrote:

olcott <NoOne@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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)