Path: ...!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 12:57:25 +0200
Organization: A noiseless patient Spider
Lines: 92
Message-ID: <v2v4il$3chkl$1@dont-email.me>
References: <v2ns85$1rd65$1@dont-email.me> <v2s46t$2pj9q$2@dont-email.me>
 <v2shmg$2rm73$2@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 12:57:25 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="d39f79cd12346f2604f25f3fb37a1545";
	logging-data="3557013"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19Y8T/mfAR0oI8MZnFolQoV"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:3MGWrjiLxzbKrFhW6ih9UizRhNc=
In-Reply-To: <v2shmg$2rm73$2@dont-email.me>
Content-Language: en-GB
Bytes: 4560

Op 25.mei.2024 om 13:22 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.
>>
> 
> The simplification is valid.
> 01       int D(ptr p)
> 02       {
> 03         H(p, p);
> 04         return 0;
> 05       }
> 
> This is a better simplification because it now has an actual
> identifiable final state that can be separately referred to.
> It is not true that H never halts. H is required to be a pure
> function. https://en.wikipedia.org/wiki/Pure_function
> 
> 

If H finds that H never halts and a non-halting H is not allowed, that 
it is clear that the set of H that satisfy the requirements is empty.