Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Re: Black box halt decider is NOT a partial decider [ Ĥ.qx(⟨Ĥ⟩,⟨Ĥ⟩) == Ĥ.qn ] [ succinct ][ GIGO ]

0 views
Skip to first unread message

olcott

unread,
Aug 1, 2021, 11:02:46 AM8/1/21
to
On 8/1/2021 7:41 AM, Ben Bacarisse wrote:
> Malcolm McLean <malcolm.ar...@gmail.com> writes:
>
>> On Sunday, 1 August 2021 at 11:54:57 UTC+1, Ben Bacarisse wrote:
>>>
>>> Here we can see that Ĥ applied to ⟨Ĥ⟩ halts. You can call your Ĥ's
>>> behaviour "correct". You can call it anything you like. But it's not
>>> "as in Linz". It does not say anything about Linz's proof. It does not
>>> do anything people would call impossible or even interesting.
>>>
>> It seems to be established that H(H_Hat, H_Hat) returns "non-halting"
>> whilst H_Hat(H_Hat) halts. So all is as Linz says it must be and no
>> theorems are refuted. Which you would expect. If results were consistent
>> it would have to be some cheap trick.
>
> I case there is some confusion, I mean that PO's Ĥ is not an Ĥ as
> specified in Linz. Yes, everything is in accordance with the truth as
> laid out in Linz and, indeed, in any textbook.
>
> I point this out to PO because he brings it up. He keeps posting the
> specification of what an Ĥ, as Linz specifies it, would do:
>
> Ĥ.q0 wM ⊢* Ĥ.qx wM wM ⊢* Ĥ.qn
> if (and only if) M applied to wM does not halt.
>
> He claims (or used to claim) that his Ĥ meets this specification for at
> least the one case where wM == ⟨Ĥ⟩:
>
> Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
> if (and only if) Ĥ applied to ⟨Ĥ⟩ does not halt.
>
> To remain relevant, he /must/ keep insisting that his Ĥ meets the
> requirements laid out in Linz, if only for this one key input.
>

Ĥ[0].q0 is taken to mean Ĥ<sub>0</sub>.q0 which is the Turing machine.

Ĥ[1].q0 is taken to mean Ĥ<sub>1</sub>.q0 which is the Turing machine
description input to Ĥ[0].q0

Ĥ[2].q0 is taken to mean Ĥ<sub>2</sub>.q0 which is first copy of the
Turing machine description input to Ĥ[0].q0

Ĥ[0].q0 ⟨Ĥ⟩ ⊢* Ĥ[0].qx ⟨Ĥ[1]⟩ ⟨Ĥ[2]⟩ ⊢* Ĥ[0].qn

It is neither a contradiction nor a paradox because there are three
different instances of Ĥ.

Because the only reason that the first instance halts is that Ĥ[0].qx
correctly determines that its input cannot possibly ever reach its final
state of Ĥ[1].qn or Ĥ[1].qy whether or not the simulating halt decider
aborts its simulation of this input, we know with 100% perfectly
justified logical certainty that the input to Ĥ[0].qx never halts.

>> However the reasons PO's halt decider fails on H_Hat(H_Hat) have got
>> 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.
>
> I don't follow. H_Hat(H_Hat) halts because H(H_Hat, H_Hat) == 0 making
> 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.
>

Garbage in derives garbage out that this garbage collector** recognizes
and rejects:

** Pathological self-reference(Olcott 2004) decider

// H and H2 are partial halt deciders
u32 PSR_Decider(u32 P, u32 I)
{
u32 Input_Halts1 = H((u32)P, (u32)I);
u32 Input_Halts2 = H2((u32)Simulate, (u32)P, (u32)I);
Output("Input_Halts1 = ", Input_Halts1);
Output("Input_Halts2 = ", Input_Halts2);
if (Input_Halts1 != Input_Halts2)
return 1;
return 0;
}


https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation


--
Copyright 2021 Pete Olcott

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