Re: Can D simulated by H terminate normally? --- Message_ID Provided

On 5/20/24 2:17 PM, olcott wrote:

On 5/20/2024 6:24 AM, Richard Damon wrote:

On 5/20/24 1:17 AM, olcott wrote:

On 5/19/2024 11:37 PM, immibis wrote:

On 19/05/24 15:06, olcott wrote:

On 5/19/2024 7:16 AM, immibis wrote:

On 19/05/24 05:59, olcott wrote:

On 5/18/2024 6:38 PM, Richard Damon wrote:

On 5/18/24 7:24 PM, olcott wrote:

On 5/18/2024 6:06 PM, Richard Damon wrote:

On 5/18/24 6:44 PM, olcott wrote:

On 5/18/2024 3:02 PM, Richard Damon wrote:

On 5/18/24 3:57 PM, olcott wrote:

On 5/1/2024 7:10 PM, Richard Damon wrote:

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.

>
Nice try but this has no effect on any D correctly simulated by H.
When the directly executed H aborts its simulation it only returns
to whatever directly executed it.

>
Why? My H does correctly simulate the D it was given.
>
You don't seem to understand how the C code actually works.
>

>
If the directly executed outermost H does not abort then none of
the inner simulated ones abort because they are the exact same code.
When the directly executed outermost H does abort it can only return
to its own caller.

>
WHAT inner simulatioin?
>
>
My H begins as:
>
int H(ptr x, ptr y) {
   static int flag = 0;
   if(flag) return 0;
   flag = 1;
>
followed by essentially your code for H, except that you need to disable the hack that doesn't simulate the call to H, but just let it continue into H where it will immediately return to D and D will then return.
>
>
Thus, your claim is shown to be wrong.
>

>
We are talking about every element of an infinite set where
H correctly simulates 1 to ∞ steps of D thus including 0 to ∞
recursive simulations of H simulating itself simulating D.
>
*At whatever point the directly executed H(D,D) stops simulating*
*its input it cannot possibly return to any simulated input*

>
And my H never stops simulating, so that doesn't apply. It will reach the final state.

>
*Show the error in my execution trace that I empirically*
*proved has no error by H correctly simulating D to the*
*point where H correctly simulates itself simulating D*
(Fully operational empirically code proved this)

>
See below:
>
>

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

>
For Reference
>
14 int H(ptr x, ptr y)
15 {
16   static int flag = 0
17   if (flag)
18      return 0
19   ... continuation of H that simulates its input
>

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

>
Line 03: Calls H (line 14)
Line 16: Static already inited, so not changed.
Line 17: Flag is 1, so
Line 18: Return 0
Line 03: Set Halt_Status to 0
Line 04: if (Halt_Status)      halts status is 0, so skip
Line 06: return Halt_Status
>
Simulation completed, program halted.
>
>

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

>
Nope. Not for this H
>
>

>
(a) That idea might work yet you did not say it correctly.
For example line 11 is the first one invoked.
(b) Computable functions cannot alter their behavior this way.
>
(1) the function return values are identical for identical arguments (no
variation with local static variables, non-local variables, mutable
reference arguments or input streams, i.e., referential transparency), and

>
Your function H works like Richard's function H. You just called the variable "execution trace" instead of "flag".

>
pages 4-5 (of a paper that I published 2021-09-26 09:39 AM)
Show H simulating P and H simulating itself simulating P.
>
The 395 pages of the execution trace of the simulated H are
screened out. No one here could ever understand the half page
trace so embedding that in 395 more pages would not help.

>
The fact that you took 395 pages to get to "if(flag) return 0;" does not mean that you didn't use "if(flag) return 0;"
>

>
That P is simulated correctly is proven by the fact that the
x86 assembly language instructions of P are correctly simulated
and they are simulated in the order that the assembly language
of P specifies.

>
This is a lie -> If every assembly instruction that was simulated is simulated correctly, the program was simulated correctly. <- This is a lie.
>

>
*Quoted from page 4 of the paper linked below*
// Simplified Linz Ĥ (Linz:1990:319)
// Strachey(1965) CPL translated to C
void P(u32 x)
{
   if (H(x, x))HERE:
    goto HERE;
}
>
int main()
{
   Output("Input_Halts = ", H((u32)P, (u32)P));
}
>
That P is correctly simulated by H is proven by the fact that
every assembly language instruction of P is correctly simulated
by H in the order specified by the x86 assembly language of P
even when H correctly simulates itself simulating P.

>
Which just means that you are admitting that you are using a non-standard definition of "Correct Simulation" from Computation theory, and thus can not link your simulations to non-halting.
>

 *It is not at all unsound and has an*
*an equivalent in computation theory*
That P is correctly simulated by H is proven by the fact that
every state specified in the Turing Machine Description of P
is correctly simulated by H in the order specified by the Turing
Machine Description of P.

But the ONLY simulation that says ANYTHING about the behavior of the machine described by the input is the UTM simulation, whih BY DEFINITION doesn't stop until it reaches a final state.

 For Linz like proofs where P includes an embedded copy of H
this includes H simulating P having this embedded copy of H
as the above specifies and may involve recursive simulations
of copies of P.
 

And, if the structure of H causes an "infinte loop", the problem is on H not P, as P is allowed to work off the specification that H WILL return an answer in a strictly finite number of steps.
If H can't do that, it is H's fault, not the input.
Note, for H to be able to say it is "Correctly" simulating the input P, then its its "simulation" of that embedded copy of H must EXACTLY match the behavior of the outer H doing the simulation, anything else is just not a correct simulation.
if H can't do that, then it just shows that H can't rely on "correctly simulating" its input to get the answer. There is NOTHING that says that any method, even simulation, is guaranteed to give the right answer. Something that seems beyond your understanding.