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.theory,sci.logic
Subject: Re: Can you see that D correctly simulated by H remains stuck in
 recursive simulation?
Date: Fri, 24 May 2024 09:37:31 +0200
Organization: A noiseless patient Spider
Lines: 51
Message-ID: <v2pg3r$27s2r$2@dont-email.me>
References: <v2nsvh$1rd65$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 24 May 2024 09:37:32 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="6f460dec93d76c9c93a2bbcc2a51db60";
	logging-data="2355291"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19tQhkwFyGN2iSZW1+iepj1"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:j/MLdHPbx2ondPeLhzkYv6BgKWg=
In-Reply-To: <v2nsvh$1rd65$2@dont-email.me>
Content-Language: en-GB
Bytes: 3314

Op 23.mei.2024 om 19:04 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 pair
> 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.
> 
>     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.
> 

Of course this depends very much on the exact meaning of 'correct 
simulation', or 'correctly emulating'. E.g., take the call to H(p, p). 
If H recognizes that it is a call to a H with the same algorithm as is 
it using itself, and it knows that itself returns a certain integer 
value K, than it can be argued that it is a correct emulation to 
substitute the call to H with this integer value K, which is assigned to 
Halt_Status. Then the simulation of D can proceed to line 04.
What we need is an exact definition of 'correct simulation', in this 
case for the call instruction. Is it allowed to make assumptions for the 
result of a call, or is a call only correctly emulated by simulating the 
instructions of the called function?