Path: ...!weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: olcott <polcott333@gmail.com>
Newsgroups: comp.lang.c++,comp.lang.c
Subject: D correctly simulated by H never halts
Date: Mon, 27 May 2024 09:00:50 -0500
Organization: A noiseless patient Spider
Lines: 173
Message-ID: <v323mi$29pd$3@dont-email.me>
References: <v2ns85$1rd65$1@dont-email.me> <v2s46t$2pj9q$2@dont-email.me>
 <v2ud85$396ga$1@dont-email.me> <v2v4r7$3chkl$2@dont-email.me>
 <v2vcud$3dtct$2@dont-email.me> <v2vhsr$3eilv$1@dont-email.me>
 <v2vl9s$3f6bi$1@dont-email.me> <v31hts$3uu5d$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 27 May 2024 16:00:51 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="458305845cd025bf1a433877c96321fe";
	logging-data="75565"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19IO/XaoIuch1CtjZCop3/q"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:F4Rv9IUhHbUQeyzT3tXh+c8YPDY=
In-Reply-To: <v31hts$3uu5d$1@dont-email.me>
Content-Language: en-US
Bytes: 8141

On 5/27/2024 3:57 AM, Fred. Zwarts wrote:
> Op 26.mei.2024 om 17:42 schreef olcott:
>> On 5/26/2024 9:43 AM, Fred. Zwarts wrote:
>>> Op 26.mei.2024 om 15:20 schreef olcott:
>>>> On 5/26/2024 6:01 AM, Fred. Zwarts wrote:
>>>>> Op 26.mei.2024 om 06:19 schreef olcott:
>>>>>> On 5/25/2024 2:32 AM, Fred. Zwarts wrote:
>>>>>>> Op 23.mei.2024 om 18:52 schreef olcott:
>>>>>>>> typedef int (*ptr)();  // ptr is pointer to int function in C
>>>>>>>> 00       int H(ptr p, ptr i);
>>>>>>>> 01       int D(ptr p)
>>>>>>>> 02       {
>>>>>>>> 03         int Halt_Status = H(p, p);
>>>>>>>> 04         if (Halt_Status)
>>>>>>>> 05           HERE: goto HERE;
>>>>>>>> 06         return Halt_Status;
>>>>>>>> 07       }
>>>>>>>> 08
>>>>>>>> 09       int main()
>>>>>>>> 10       {
>>>>>>>> 11         H(D,D);
>>>>>>>> 12         return 0;
>>>>>>>> 13       }
>>>>>>>>
>>>>>>>> The above template refers to an infinite set of H/D pairs where 
>>>>>>>> D is
>>>>>>>> correctly simulated by pure function H. This was done because many
>>>>>>>> reviewers used the shell game ploy to endlessly switch which H/D 
>>>>>>>> was
>>>>>>>> being referred to.
>>>>>>>>
>>>>>>>> *Correct Simulation Defined*
>>>>>>>> This is provided because every reviewer had a different notion of
>>>>>>>> correct simulation that diverges from this notion.
>>>>>>>>
>>>>>>>> In the above case a simulator is an x86 emulator that correctly 
>>>>>>>> emulates
>>>>>>>> at least one of the x86 instructions of D in the order specified 
>>>>>>>> by the
>>>>>>>> x86 instructions of D.
>>>>>>>>
>>>>>>>> This may include correctly emulating the x86 instructions of H 
>>>>>>>> in the
>>>>>>>> order specified by the x86 instructions of H thus calling H(D,D) in
>>>>>>>> recursive simulation.
>>>>>>>>
>>>>>>>> *Execution Trace*
>>>>>>>> Line 11: main() invokes H(D,D); H(D,D) simulates lines 01, 02, 
>>>>>>>> and 03 of
>>>>>>>> D. This invokes H(D,D) again to repeat the process in endless 
>>>>>>>> recursive
>>>>>>>> simulation.
>>>>>>>>
>>>>>>>
>>>>>>> Olcott's own words are that the simulation of D never reaches 
>>>>>>> past line 03. So the lines following line 03 do not play a role 
>>>>>>> and, therefore, can be removed without changing the claim. This 
>>>>>>> leads to:
>>>>>>>
>>>>>>> typedef int (*ptr)();  // ptr is pointer to int function in C
>>>>>>> 00       int H(ptr p, ptr i);
>>>>>>> 01       int D(ptr p)
>>>>>>> 02       {
>>>>>>> 03         return H(p, p);
>>>>>>> 04       }
>>>>>>> 05
>>>>>>> 06       int main()
>>>>>>> 07       {
>>>>>>> 08         H(D,D);
>>>>>>> 09         return 0;
>>>>>>> 10       }
>>>>>>>
>>>>>>>
>>>>>>> What we see is that the only property of D that is used is that 
>>>>>>> it is a parameter duplicator. (Is that why it is called D?). H 
>>>>>>> needs 2 parameters, but it can be given only one input parameter, 
>>>>>>> so the parameter duplicator is required to allow H to decide 
>>>>>>> about itself.
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> Of the infinite set of H that simulate at least one step, none of 
>>>>>>> them, when simulated by H, halts, because none of them reaches 
>>>>>>> its final state. Olcott's claim is equivalent to the claim of 
>>>>>>> non-halting behaviour of H.
>>>>>>> This means that a simulating halt-decider is a bad idea, because 
>>>>>>> the decider itself does not halt.
>>>>>>
>>>>>> Not at all.
>>>>>>     A simulator is an x86 emulator that correctly emulates 1 to N 
>>>>>> of the
>>>>>>     x86 instructions of D in the order specified by the x86 
>>>>>> instructions
>>>>>>     of D. This may include M recursive emulations of H emulating 
>>>>>> itself
>>>>>>     emulating D.
>>>>>>
>>>>>>     This means that D cannot possibly reach its own line 06 and halt
>>>>>>     in any finite steps of correct simulation. H is free to halt at
>>>>>>     any time after these N finite steps of correct simulation.
>>>>>>
>>>>>>
>>>>>
>>>>> D does not reach it own line 04 because the simulation of H does 
>>>>> not return to D. So, it shows that the simulation of H does not 
>>>>> reach it final state, which proves that H does not halt.
>>>>
>>>> Your transformation would have been acceptable if you retained the
>>>> fact that H is a pure function that always halts and returns some 
>>>> value.
>>>>
>>>
>>> Since H is required to halt, but H shows that H does not halt 
>>> (because the simulation of H never reaches its final state), the 
>>> conclusion must be that there is no such H.
>>
>>  >
>>
>> When D correctly simulated by pure simulator H remains stuck in infinite
>> recursive simulation then we also know that D never reaches its own line
>> 06 and halts in less than an infinite number of correctly simulated
>> steps.
>>
>> This is what I had in mind all along. Because I am a relatively terrible
>> communicator it takes me a very long time to translate my intuitions
>> into simple words.
>>
>>
> typedef int (*ptr)();  // ptr is pointer to int function in C
> 00       int H(ptr p, ptr i);
> 01       int D(ptr p)
> 02       {
> 03         return H(p, p);
> 04       }
> 05
> 06       int main()
> 07       {
> 08         H(D,D);
> 09         return 0;
> 10       }
> 
> We see that the requirements for H are contradictory. 

*Not at all, I just did not explain us clearly enough*

When we hypothesize that H is a pure simulator we see that D correctly
simulated by pure simulator H remains stuck in recursive simulation thus
never reaches its own simulated final state at its line 06 and halts. In
this case H does not halt, thus is neither a pure function nor a
decider.

 From this we correctly conclude that D correctly simulated by pure
function H never reaches its simulated final state at its own line 06
and halts in Less than an infinite (AKA finite) number of simulated
steps. Here is a concrete example of that:

https://en.wikipedia.org/wiki/Googolplex
When pure function H correctly simulates a Googolplex ^ Googolplex
number of steps of D, then D never reaches its simulated final state
at its own line 06 and halts. Pure function H halts after this finite
number of steps of correct simulation.

In other words when the *INPUT* to H(D,D) is correctly simulated by
either pure simulator H or pure function H this correctly simulated
*INPUT* never halts no matter what, thus the INPUT to H(D,D) is
definitely non halting.

*This is STEP ONE of my four step proof*

-- 
Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer