Path: ...!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: olcott <polcott333@gmail.com>
Newsgroups: comp.theory,sci.logic
Subject: Re: Can D simulated by H terminate normally? --- Message-ID provided
Date: Sat, 18 May 2024 11:24:02 -0500
Organization: A noiseless patient Spider
Lines: 118
Message-ID: <v2akn3$2s4fs$1@dont-email.me>
References: <v0k4jc$laej$1@dont-email.me> <v0l11u$ussl$1@dont-email.me>
 <v0lh24$123q3$1@dont-email.me> <v0lic7$2g492$3@i2pn2.org>
 <v0lkas$12q0o$3@dont-email.me> <v0loq2$2g493$1@i2pn2.org>
 <v0lq7d$14579$2@dont-email.me> <v0ls98$2g492$7@i2pn2.org>
 <v0m29q$166o1$1@dont-email.me> <v0m37e$2gl1e$1@i2pn2.org>
 <v0m3v5$16k3h$1@dont-email.me> <v0m55t$2gl1f$3@i2pn2.org>
 <v0m5sn$172p4$1@dont-email.me> <v0m7em$2gl1f$5@i2pn2.org>
 <v0m7tq$17dpv$1@dont-email.me> <v0m8g9$2gl1e$6@i2pn2.org>
 <v0m978$17k7o$3@dont-email.me> <v0mko6$2hf3s$2@i2pn2.org>
 <v0n59h$1h98e$1@dont-email.me> <v0o037$2j1tu$3@i2pn2.org>
 <v0oc65$1q3aq$3@dont-email.me> <v0p9ts$2ki5r$6@i2pn2.org>
 <v0q1rk$2a3u1$1@dont-email.me> <v0qkti$2m1nf$1@i2pn2.org>
 <v0r4a3$2hb7o$6@dont-email.me> <v0rsbr$2m1nf$6@i2pn2.org>
 <v0segm$2v4oq$1@dont-email.me> <v0t8o9$2p3ri$2@i2pn2.org>
 <v0tpjf$3881i$5@dont-email.me> <v0ulma$2qov4$1@i2pn2.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 18 May 2024 18:24:04 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="95afb1fc0a4871125108def5044e156a";
	logging-data="3019260"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+TG1TZmWWLtlBhbEki/F7j"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:t2B/tFJkZHVpQmAMrytOBHWb97E=
Content-Language: en-US
In-Reply-To: <v0ulma$2qov4$1@i2pn2.org>
Bytes: 6706

On 5/1/2024 7:10 PM, Richard Damon wrote:
> On 5/1/24 12:11 PM, olcott wrote:
>> On 5/1/2024 6:23 AM, Richard Damon wrote:

On 5/18/2024 8:13 AM, Richard Damon wrote:
 > (4) Message-id: <v0ulma$2qov4$1@i2pn2.org>

<snip so that lookup by message ID won't truncate>

> The first method has been discussed here by Flibble. While the final 
> answer he got to doesn't fit the requirements, the first part of the 
> method DOES show that it is possible for an H to simulate to past line 3.
> 
> THe basic idea is that if H(M,d) finds that its simulation of M(d) get 
> to a call to H(M,d) then rather that your idea of just saying it will 
> get stuck and declair the input invalid, since there ARE a number of 
> possible inputs that there is a "correct" answer that H can give to 
> match the behavior of the direct execution of M(d), what H does is fork 
> its simulation into two threads.
> 
> Thread 1 continues the simulation assuming that the call to H(M,d) will 
> return a 1, and if that simulation reaches a halting state, then 1 is 
> the answer, and thread 2 can be abandoned.
> 
> Thread 2 continues the simulation assuming that the call to H(M,d) will 
> return a 0, and if that simulation reaches a provable non-halting 
> pattern, then 0 is the answer, and thread 1 can be abandoned.
> 
> It may be the case that BOTH answer could be correct, in which case 
> depending on exactly how the forking works and how long it takes each to 
> get to the answer, either answer might be given, but then, both are 
> correct.
> 
> It may be the case that neither answer can be shown correct, if Thread 
> one can prove that it will be non-halting and Thread 2 halts, then the 
> decider has proven the machine to be "contrary" to it. But it might be 
> the case that it never can figure that out, and it just doesn't answer.
> 
> But, in all cases, it gets past the call to H(M,d), so your criteria, 
> that NO H can get there is not meet.
> 
> 
> The second method uses the fact that you have not restricted what H is 
> allowed to do, and thus H can remember that it is simulating, and if a 
> call to H shows that it is currently doing a simulation, just 
> immediately return 0. Thus, H can actually correct simulate the 
> instruction at the call to H, as they will execute just a few 
> instructions testing that condition and returning, and thus not run into 
> the problem you ran into where H just couldn't simulate itself because 
> it got bogged down.
> 
> In this case it is actually true that the direct execution of D(D) 
> differs from the correct simulation of the input by H, as H is no longer 
> a "Computation" per the rules of Computation Theory, but you have 
> admitted that you are abandoning those, so it doesn't matter (of course 
> that make trying to get your results to apply to something similar 
> harder, but that is why you need to try to come up with some actual 
> definitons.)
> 
> So, by the rules of Compuation Theory, your H is not correct, but by 
> your lack of rules, your conclusion that H can not simulate past the 
> call are incorrect, so you proof is also broken.
> 

The following only refers to every H/D pair matching the following 
template where 1 to ∞ steps of D are correctly simulated by H.

*Your words above diverge from this precise specification*
*Your words above diverge from this precise specification*
*Your words above diverge from this precise specification*

typedef int (*ptr)();  // ptr is pointer to int function
00 int H(ptr x, ptr y);
01 int D(ptr x)
02 {
03   int Halt_Status = H(x, x);
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 }

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);

keeps repeating (unless aborted)
Line 01
Line 02
Line 03: simulated D(D) invokes simulated H(D,D) that simulates D(D)

Simulation invariant:
D correctly simulated by H cannot possibly reach past its own line 03.

The key thing to note is that no D simulated correctly by any H of every
H/D pair specified by the above template ever reaches its own line 06 
and halts.

The above is self-evidently true to anyone having sufficient
knowledge of the semantics of the C programming language.


-- 
Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer