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: Sat, 25 May 2024 09:32:45 +0200
Organization: A noiseless patient Spider
Lines: 74
Message-ID: <v2s46t$2pj9q$2@dont-email.me>
References: <v2ns85$1rd65$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 25 May 2024 09:32:45 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="94df5413293a0b9e5bf7a13fc9aeafcb";
	logging-data="2936122"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+YEr2z9nScMXYFGxGp3TAy"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:vQBIgQdM/CxeOdKsJMmpGSuRrYs=
In-Reply-To: <v2ns85$1rd65$1@dont-email.me>
Content-Language: en-GB
Bytes: 3603

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.