On 10/01/2024 07:16, immibis wrote:
> On 1/10/24 04:36, Mike Terry wrote:
>> On 09/01/2024 23:54, immibis wrote:
>>>
>>> Your simulator does an incorrect simulation because of the undeclared input of execution history
>>> into the inner simulation.
>>>
>>
>> I think you may be off base on your exact explanation here.
>>
>> It's some time since I looked in any detail at PO's code and traces, but when I last did that it
>> seemed to me that at the step-by-step x86 instruction level the simulation was ok.  The problem is
>> that H stops simulating before the simulated computation halts, on the grounds that it has spotted
>> the "PO infinitely recursive simulation pattern".
>
> Yes.
>
>> UP TO THAT POINT the simulation faithfully tracks the states of the actual computation, which
>> continues from that point for a while and then terminates normally.  [..as seen when running D(D)
>> "directly"]
>
> Well, sort of. The simulator refuses to simulate the simulator, and instead does something like
> incrementing a "simulation level" variable and then simulating the code the inner simulator would
> have simulated.

I think we diverge here. Perhaps... I would say PO's code "simulates the simulator" in a
reasonable way we could accept for current purposes. (At least for the purposes of discussing where
he is going wrong - IF he went as far as submitting a formal paper to a journal, all sorts of lesser
problems would need addressing regarding the validity of his approach and his x86utm design (sharing
the main code/data across all simulation levels, use of complex x86 instruction set etc.), but
that's never going to happen and meanwhile I don't believe these issues are the source of any actual
problems in his results. He has much simpler basic misunderstandings.)

The basic limitations of PO's x86utm design:
- all simulations share a single address space with shared code and data
- the x86-level instruction simulation is housed in x86utm.exe as opposed to
what I'll call the user (code/data) space, where H,D,H1, code and stack space and
(perhaps) global data reside
- simulation single-stepping etc. is provided as primitives by x86utm to user space code.
(since address space is shared, and register save space used by primitives is in the
user address space, simulators can monitor the progress of their simulations)
I think nested simulation works sort of ok given the above architecture - but also see my very final
comment below...

Also I think there's divergence among posters here re what counts as "simulation", so that might be
a source of misunderstanding? I prefer "simulation" to mean simply the act of calculating the state
changes in a computation, with the understanding that a program might simulate just (say) 10 steps
of a computation, and then stop for whatever reason. I'd say that simulation activity was "correct"
if those 10 steps were calculated correctly i.e. they track the first 10 actual computation steps.

The program will of course perform many other calculations and make other decisions (e.g. the
counting to 10 or other tests to decide when to stop simulating, deciding on its own return code) -
but I don't count those "simulating" or part of the simulator. I.e. the simulator is just a
component the program uses. If the program simulates 10 steps correctly then stops simulating, the
/simulation/ was correct, and if the program proceeds to announce that the computation would never
halt, when in fact it would, that doesn't change that it correctly simulated the 10 steps - the
fault lies in the non-simulating code of the program. [Well, that's how I'd express things...]

Perhaps you use "simulate" in a broader sense, e.g. to include ALL the code in H including what I'd
consider business logic (which for H I'd label "termination analysis")? So when you say "the
simulator /refuses/ to simulate the simulator", maybe you're just saying H is coded to abort its
simulation too early due to a false positive match with its unsound recursion test. [I agree with
that.] But to me I'm reading it as saying x86utm doesn't properly support nested simulation in some
way, whereas to me it seems it does!

E.g. suppose we run H1(D,D). [H1 is the copy of H, but with a modified abort condition that means
in effect it never matches when analysing (D,D) input...]
When H1 simulates D(D), it simulates:
- D calling H,
- H simulating D(D) - including the simulation primitives within H, and all the termination
analysis code such as PO's infinite recursion testing code, abort decision code and so on.
- the simulated simulation being aborted by the simulated H,
- H returning to D [telling simulated D that D(D) never halts!],
- D reaching its final ret, i.e. halting.

Perfect - no issues I can see with nesting of simulations or invalid secret data feeds to inner
simulations altering the course of the inner simulations or anything like that.

The problem when running H(D,D) is simply that while (correctly) simulating D(D), [outer] H spots
PO's "infinite recursion" pattern [which DOES NOT ACTUALLY TEST FOR INFINITE RECURSION despite PO's
name for the test] and aborts the simulation, announcing incorrectly that D(D) doesn't halt when it
does.

That's hardly the fault of the correct (partial) simulation - it's the fault of the faulty
termination analysis logic in H, namely relience use of PO's unsound "infinite recursion" pattern.
Er, that's it!

>
> A true simulation of the simulator would find that the simulator eventually detects the infinite
> recursion pattern, and then halts.

And it does, e.g. when we run H1(D,D) as above.

In my terminology, when running H(D,D) H "correctly" simulates D(D) for a while, but then applies an
unsound test that matches its generated simulation trace, so it incorrectly concludes its simulation
of D(D) "IF continued" would never halt. Actually I'm being sloppy: *H* assumes no such thing as
it's just code. The incorrect assumption is PO's, as the designer.

The point I'd make is that the /reason/ H1 sees simulated D(D) halt while H decides it never halts
is nothing to do with incorrect nested simulation implementation causing nested simulations to
behave differently from outer simulations - like due to invalid use of global data leaking in, or
whatever. AFAICT regardless of the simulation depth, all the simulations behave exactly the same
[up to the point the simulation is aborted of course]. This is where I suspect you diverge?

I think your "true simulator" = my "full simulator" = "simulates to completion"? PO's H is
obviously not a "true simulator" in that sense and PO has never claimed that. PO claims his H
"correctly simulates" D(D) which fits my usage, although his often repeated "..until H correctly
decides that its simulation would never end..." bit doesn't apply - H actually /incorrectly/ decides
blah blah, since it relied on his unsound infinite recursion test.

> Olcott's simulator instead behaves as if it knows that the
> simulator never halts, which is an obviously untrue fact and a self-delusion of Olcott.

Hmm. I'll read that as "PO's "H" behaves as if it knows...". But H is just code, and doesn't do
"as if" or "knowing" (of course). Those ideas may well be in PO's mind, as /designer/ for H, and
readers may benefit from that insight.

But what actually happens? H applies an unsound test which matches (a false-positive), leading it
to incorrectly announce that computation D(D) never halts. That seems a simple account of what's
going on.

>
>>
>> PO is really really really convinced (despite concrete evidence showing otherwise) that his
>> infinite recursion pattern gives a sound non-halting test, but he is just wrong - it does not
>> imply non-halting.
>
> Infinite recursion does imply non-halting, but it's detected in a way that is obviously incorrect.

Exactly. PO's "infinite recursive simulation" test is unsound. It can match both halting and
non-halting computations.

>
> If the simulator simulated the simulator, it would end up in an infinitely nested simulation stack
> that would obviously never finish. That would be obvious, and a human looking at the program could
> see that it could never finish (thus acting as a correct halting decider for this particular program).
>
> In actuality, the program behaves as if the nested simulation is launched with different parameters
> from the outer simulation. One way to interpret this is that the nested simulation is launched with
> some execution history, so that it will behave differently than specified if it detects that a
> nested simulator is launched inside it (a double-nested simulator).

I don't really follow much of that. x86utm design seems to me to allow correct simulation of the
simulating code and surrounding abort code etc.. I would say

"In actuality the program "behaves" exactly as it is coded :), with no imagined changed parameters,
and inner simulations behave just like their corresponding computations, except the simulation may
be partial due to outer code deciding to abort. The program H gives the wrong answer, because it
utilises an unsound abort test, and aborts before the D(D) final ret."

And the H1(D,D) example shows that "If the simulator simulated the simulator, it /wouldn't/ end up
in an infinitely nested simulation" necessarily. (Obviously this depends on the remaining
non-simulation code.)

I could be persuaded to say something like "PO /designed/ H with an incorrect understanding that
D(D) simulation would continue with infinite recursion, just as if H were called with different
parameters [e.g. as though it was called as H(D_FULL_SIMULATOR, D_FULL_SIMULATOR)]. But do we care
what PO believed when he designed H; it's what actually happens at run time, and why, that matters...

I expect everyone agrees D_FULL_SIMULATOR(D_FULL_SIMULATOR) never halts, but we know that's not the
D(D) computation. And FULL_SIMULATOR (D_FULL_SIMULATOR, D_FULL_SIMULATOR) never returns, so falls
at the first hurdle as a HD candidate. [If this is all you meant, I think your wording is confusing
to the point of, um, something really confusing that doesn't help anybody! :) ]

>
>   Other tests
>> coded in his H may (likely) be sound, such as a "tight loop test", but the one that matches in the
>> D(D) simulation by H is unsound.  Anyway, PO believes it is sound, so for PO there is no debate:
>> once H detects the pattern in the simulated D(D) trace that is (to PO) "proof" that D(D) (at least
>> "when correctly simulated by H" whatever that means) is non-halting.  Since he acknowledges that
>> D(D) run independently DOES halt, he has to invent further ridiculous explanations to explain that
>> away
>
> Yes, I find that to be the most ridiculous part. It's obvious that H(D,D) says it doesn't halt. It's
> obvious that D(D) does halt. Therefore it's obvious that H(D,D) is lying. This is an extremely basic
> and obvious fact which is staring Olcott in the face, but I suppose he can't just give up on 20
> years of bullshit in an instant.
>
> - all the stuff about "different questions depending on who is
>> being asked". To repeat my point above - regardless of who is asked, PO's simulation follows the
>> same correct sequence of steps UP TO THE POINT where askee stops the simulation.  No difference in
>> the simulated D(D) steps, only in the surrounding conditional code (e.g. in H) driving the
>> simulation steps.
>
> Actually I don't believe the simulator correctly simulates a nested simulation.

?? It seems to me that it does ok, and I have no unexplained observations. BUT since PO's current
H code aborts before deep nesting gets going, perhaps in the end you're right! At one point in PO's
development he had all simulation levels accessing the ENTIRE trace history, including history for
outer processes. That's a definite show stopper, but I understand (maybe incorrectly?) he fixed
that so that inner traces only saw their own simulation activity trace entries (and also those of
more deeply nested traces). Also I doubt current code is what I looked at 18 months ago.

Perhaps PO should confirm...

Mike.