Path: ...!npeer.as286.net!npeer-ng0.as286.net!3.eu.feeder.erje.net!feeder.erje.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: Can you see that D correctly simulated by H remains stuck in
 recursive simulation?
Date: Sun, 26 May 2024 13:01:59 +0200
Organization: A noiseless patient Spider
Lines: 91
Message-ID: <v2v4r7$3chkl$2@dont-email.me>
References: <v2ns85$1rd65$1@dont-email.me> <v2s46t$2pj9q$2@dont-email.me>
 <v2ud85$396ga$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sun, 26 May 2024 13:01:59 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="d39f79cd12346f2604f25f3fb37a1545";
	logging-data="3557013"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+8rZjz4Z3NKRP6Ei7fVMux"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:G2MooUYyLigBnZZxHdtzi5Y1yVE=
In-Reply-To: <v2ud85$396ga$1@dont-email.me>
Content-Language: en-GB
Bytes: 4902

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. A clear indication that 
a simulating decider is not a good idea, because it is required to halt, 
but H itself finds that H does not reach its final state.