Path: ...!weretis.net!feeder9.news.weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: "Fred. Zwarts" <F.Zwarts@HetNet.nl>
Newsgroups: comp.lang.c++,comp.lang.c
Subject: Re: D correctly simulated by H never halts
Date: Tue, 28 May 2024 11:11:54 +0200
Organization: A noiseless patient Spider
Lines: 201
Message-ID: <v3474q$hf7u$1@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>
 <v323mi$29pd$3@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 28 May 2024 11:11:56 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="fbe328d3fbd40e243e4b25f396044ad5";
	logging-data="572670"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18nEcaDZqRP7B27y8K3A6xn"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:UvW+HA4ZLkDAQ8ryTiCcePJEas8=
In-Reply-To: <v323mi$29pd$3@dont-email.me>
Content-Language: en-GB
Bytes: 9056

Op 27.mei.2024 om 16:00 schreef olcott:
> 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

.... we see that H 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

(the line 06 is different in my example)

> 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

.... we correctly conclude that H correctly simulated by ...

> function H never reaches its simulated final state at its own line 06

(The line 06 is different in my example)

> 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

.... of H, then H never reaches its simulated final state
========== REMAINDER OF ARTICLE TRUNCATED ==========