Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: Can D simulated by H terminate normally?
Date: Sun, 28 Apr 2024 11:23:26 +0300
Organization: -
Lines: 51
Message-ID: <v0l11u$ussl$1@dont-email.me>
References: <v0k4jc$laej$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sun, 28 Apr 2024 10:23:26 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="e0e91796f9a176abfbc86314386cddaa";
	logging-data="1012629"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18XB0JY3PyvpvydQeGNFLEz"
User-Agent: Unison/2.2
Cancel-Lock: sha1:ZoZYa2n9a6KCgNpJdKtXSsb/nQQ=
Bytes: 2448

On 2024-04-28 00:17:48 +0000, olcott said:

> Can D simulated by H terminate normally?

One should not that "D simulated by H" is not the same as
"simulation of D by H". The message below seems to be more
about the latter than the former. In any case, it is more
about the properties of H than about the properties of D.

> The x86utm operating system based on an open source x86 emulator.
> This system enables one C function to execute another C function
> in debug step mode. When H simulates D it creates a separate process
> context for D with its own memory, stack and virtual registers. H
> is able to simulate D simulating itself, thus the only limit to
> recursive simulations is RAM.
> 
> // The following is written in C
> //
> 01 typedef int (*ptr)(); // pointer to int function
> 02 int H(ptr x, ptr y)    // uses x86 emulator to simulate its input
> 03
> 04 int D(ptr x)
> 05 {
> 06   int Halt_Status = H(x, x);
> 07   if (Halt_Status)
> 08     HERE: goto HERE;
> 09   return Halt_Status;
> 10 }
> 11
> 12 void main()
> 13 {
> 14   D(D);
> 15 }
> 
> Execution Trace
> Line 14: main() invokes D(D)
> 
> keeps repeating (unless aborted)
> Line 06: simulated D(D) invokes simulated H(D,D) that simulates D(D)
> 
> Simulation invariant
> D correctly simulated by H cannot possibly reach its own line 09.
> 
> Is it dead obvious to everyone here when examining the execution
> trace of lines 14 and 06 above that D correctly simulated by H cannot
> possibly terminate normally by reaching its own line 09?


-- 
Mikko