Re: Can D simulated by H terminate normally? --- Message-ID provided

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