Path: ...!weretis.net!feeder6.news.weretis.net!feeder9.news.weretis.net!i2pn.org!i2pn2.org!.POSTED!not-for-mail
From: Richard Damon <richard@damon-family.org>
Newsgroups: comp.theory
Subject: Re: Can D simulated by H terminate normally?
Date: Sun, 28 Apr 2024 09:19:03 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <v0lic7$2g492$3@i2pn2.org>
References: <v0k4jc$laej$1@dont-email.me> <v0l11u$ussl$1@dont-email.me>
 <v0lh24$123q3$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 13:19:03 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="2625826"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
X-Spam-Checker-Version: SpamAssassin 4.0.0
In-Reply-To: <v0lh24$123q3$1@dont-email.me>
Content-Language: en-US
Bytes: 3456
Lines: 69

On 4/28/24 8:56 AM, olcott wrote:
> On 4/28/2024 3:23 AM, Mikko wrote:
>> 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.
>>
> 
> D specifies what is essentially infinite recursion to H.
> Several people agreed that D simulated by H cannot possibly
> reach past its own line 03 no matter what H does.

Nope, it is only that if H fails to be a decider.

Since you claim H to be a decider, D can not have infinite recursion, 
because H must return in finite time.

Yes, we get two different, and contradictory, sets of results depending 
on which facts we look at. The cause of this is the principle of 
explosion, that somewhere in our setup we have a false premise, and that 
turns out to be that there can exist an H that can correctly determine 
the halting status of its input, or in particular, the input built by 
this formula.

> 
>>> 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?
>>
>>
>