Re: Hypothetical possibilities --- Complete Proof

On 03/08/2024 00:12, Richard Damon wrote:

On 8/2/24 6:23 PM, Mike Terry wrote:

On 02/08/2024 19:25, Richard Damon wrote:

On 8/2/24 1:39 PM, Mike Terry wrote:

On 02/08/2024 11:12, Mikko wrote:

On 2024-08-01 13:29:24 +0000, olcott said:
>

On 8/1/2024 8:12 AM, Fred. Zwarts wrote:

Op 01.aug.2024 om 14:20 schreef olcott:

On 8/1/2024 3:10 AM, Fred. Zwarts wrote:

Op 31.jul.2024 om 23:23 schreef olcott:

On 7/31/2024 3:01 PM, Fred. Zwarts wrote:

Op 31.jul.2024 om 17:14 schreef olcott:

On 7/31/2024 3:44 AM, Fred. Zwarts wrote:

Op 31.jul.2024 om 06:09 schreef olcott:

>
  machine   stack     stack     machine    assembly
  address   address   data      code       language
  ========  ========  ========  =========  =============
[00002192][00103820][00000000] 55         push ebp
[00002193][00103820][00000000] 8bec       mov ebp,esp
[00002195][0010381c][00002172] 6872210000 push 00002172 ; push DDD
[0000219a][00103818][0000219f] e833f4ffff call 000015d2 ; call HHH(DDD)
New slave_stack at:1038c4
>
We don't show any of HHH and show the execution trace of
of just DDD assuming that HHH is an x86 emulator.

>
This assumption is incorrect if it means that HHH is an unconditional simulator that does not abort.

This algorithm is used by all the simulating termination analyzers:
<MIT Professor Sipser agreed to ONLY these verbatim words 10/13/2022>
     *If simulating halt decider H correctly simulates its input D*
     *until H correctly determines that its simulated D would never*
     *stop running unless aborted* then
>
     H can abort its simulation of D and correctly report that D
     specifies a non-halting sequence of configurations.
</MIT Professor Sipser agreed to ONLY these verbatim words 10/13/2022>

>
So, Sipser only agreed to a correct simulation, not with an incorrect simulation that violates the semantics of the x86 language by skipping the last few instructions of a halting program.
>

>
int DD()
{
   int Halt_Status = HHH(DD);
   if (Halt_Status)
     HERE: goto HERE;
   return Halt_Status;
}
>
int main()
{
   HHH(DD);
}
>
DD correctly emulated by HHH cannot possibly reach its own
second line. I switched to DDD correctly emulated by HHH

>
But it has been proven that no such HHH exists that simulates itself correctly. So, talking about a correct simulation by HHH is vacuous word salad.
>

because only C experts understood the above example and we
never had any of those here.

>
There are many C experts that looked at it, but you only got critic, because you keep hiding important properties of HHH, which made the conclusion impossible.

>
The following is all that is needed for 100% complete proof
that HHH did emulate DDD correctly according to the semantics
of the x86 language and did emulate itself emulating DDD
according to these same semantics.

>
You are repeating the same false claim with out any self-reflection. It has been pointed out that there are many errors in this proof.
Why repeating such errors?
>

>
_DDD()
[00002172] 55         push ebp      ; housekeeping
[00002173] 8bec       mov ebp,esp   ; housekeeping
[00002175] 6872210000 push 00002172 ; push DDD
[0000217a] e853f4ffff call 000015d2 ; call HHH(DDD)
[0000217f] 83c404     add esp,+04
[00002182] 5d         pop ebp
[00002183] c3         ret
Size in bytes:(0018) [00002183]
>
Begin Local Halt Decider Simulation   Execution Trace Stored at:1138cc
[00002172][001138bc][001138c0] 55         push ebp      ; housekeeping
[00002173][001138bc][001138c0] 8bec       mov ebp,esp   ; housekeeping
[00002175][001138b8][00002172] 6872210000 push 00002172 ; push DDD
[0000217a][001138b4][0000217f] e853f4ffff call 000015d2 ; call HHH(DDD)

>
The trace stops and hides what happens when 000015d2 is called.
Olcott is hiding the conditional branch instructions in the recursion.
>

>
*Here is the full trace where nothing is hidden*
https://liarparadox.org/HHH(DDD)_Full_Trace.pdf

>
On page 36 of that "trace"
    [0000128c][0010379f][00000018] e8e6f4ffff call 00000777
is not followed by the trace of 00000777. Instead the trace continues
with the next instruction after the return without any comment about
the omission. Meaning of 00000777 is not told.
>

>
777 is the address of Allocate, which is one of PO's "primative ops" within his "computing model". (Similar to his DebugStep().)
>
It is implemented inside x86utm.exe (his COFF obj code runner), not in the user code DDD/HHH/etc. in the obj file, and so we would not expect to see any trace entries for its internals.  When the op concludes, rax has the address of the allocated memory, which is consistent with how a normal function would have returned the address.
>
You can say correctly that PO has not explained this, but then he provided the full trace under protest, so it's understandable that he has not previously explained everything in it.  I'm surprised that his response to your post was both to ignore the question and accuse you of playing sadistic head games, as the question was perfectly sensible.
>
You can look up the 777 address in the listing at the start of the trace and it's there along with a bunch of other routines which appear to just return without doing anything - those are all PO's primitive ops.  If you feel a need to understand exactly what they do, you'll need to check his source code!  (Although for Allocate there is no big surprise...)
>
>
So your observation isn't really a problem beyond not being properly explained.  An actual problem seen in his trace data is that the simulation of DDD does not track the behaviour of the unsimulated DDD. I.e. his simulation is incorrect.  (PO knows about that but claims it doesn't matter, although on other occasions he still claims the simulation is correct.)
>
>
Mike.
>

>
But the bigger error that totally negates this trace is if you at where it begins, it is at program address 00002197, which just the page before is shown to be the address of _main.
>
Since HHH was not given the address of main to start with, this can not be the trace that HHH itself is generating and looking at, but is instead the trace of the running of that top level HHH.

>
Well, all PO's trace logs start with main!  Something has to set up the required computation [aka the required TM + input tape].  That could be HHH(DDD), or maybe DDD() or whatever.  PO might have done this through extra invocation arguments to x86utm.exe, and then there would have been no need to code a main() in his halt7.c user code file.  But that would be decidedly fiddly, so having a fixed entry function main() is an ok convenience I'd say.  The main() is not really part of his computation model, but x86utm traces the lot.
>
Normally when PO gives code snippets, he includes the main() routine. In this case it is main calling HHH(DDD), so HHH as you say is the outer level HHH.  (Later on in the trace we see simulated HHH entries...)
>

Since that shows the trace isn't what he claims it is, nothing it says means anything for his argument.

>
I can't see what PO claims the trace to be.  That trace was taken and published some weeks ago, and doesn't match up exactly with todays partial trace - e.g. the addresses of HHH/DDD don't match and so on.  If it's just wrong through being out of date, or because it has the main() trace on the front, that's not the worst of crimes...
>
I see upthread that someone pointed out that the filtered trace "..stops and hides what happens when 000015d2 is called."  Well, the full trace does show the instructions of HHH being executed [even if the data is a bit out of date], and of course there are loads of conditional branches... so everyone should be happy! :)
>

>
In fact, the way the trace is produced, it is clear that the tracing code doesn't care about what level of simulation it is working but calls to "DebugStep" just inject the data they trace as part of the code that is being traced, which isn't actually what is happening in the processor.

>
That's correct.  The full trace proceeds showing HHH executing its code as we would expect, and after some time HHH (actually a routine called by HHH) invokes a DebugStep op.  We can see that the DebugStep op stepped HHH's simulation one instruction, which also appears in trace. Here is where that happens:
>
,,,
[000011eb][00103783][00103863] 8b4d1c mov ecx,[ebp+1c]
[000011ee][00103783][00103863] 8b11 mov edx,[ecx]
[000011f0][0010377f][00103827] 52 push edx
[000011f1][0010377f][00103827] e8b1f5ffff call 000007a7     <=== DebugStep
[00002177][00113897][0011389b] 55 push ebp                  <=== simulated instruction
[000011f6][0010378b][90909090] 83c40c add esp,+0c           <=== next instructin after DebugStep
[000011f9][0010378b][90909090] e8e9f5ffff call 000007e7
...
>
The "push ebp" above is the first simulated instruction, and just appears in the trace straight after the call to DebugStep.  [Note the apparent discontinuities in IP address and ESP (cols 1&2 resp.)  Yeah I know, /why isn't there a simulation level column/ ?]
>
We could say that the trace as shown is a log of all the instructions x86utm "executes" in succession, so it is a merge of entries from all simulation levels - certainly it's not the x86 "processor trace" it might be taken to be.
>
Note - the "push ebp" instruction is the first simulated instruction of DDD(), which at least is the instruction we would expect it to be.  In PO's normal "filtered" log output, all the other instructions above wouldn't appear as they're not from DDD.
>
Of course these traces don't support PO's overall case he is claiming, because the (various) logs show that DDD halts, and that HHH(DDD) reports DDD as non-halting, exactly as Linz/Sipser argue. Er, that's about it!
>
Whether it supports some minutia of what PO is currently arguing about - you'd have to explain to me exactly what he is claiming!  (um, Please don't!)
>
>

>
This seems to be part of the source for his confusion, and the tool he uses to try to spread his lies.
>
such results should, at most, be inserted as a comment about what the results computed as meta-logic of the code just emulated did.
>
But of course, noting that this second layer is just meta-results, and that the original emulator always had the option of stopping its emulation ruins his argument that the recursion is necessarily infinite.

>
It's hard to pin down confusion sources.  I agree PO doesn't need x86utm logs to argue his case, and including them doesn't /prove/ anything, especially when he admits the simulated code uses mutable static data to modify the behaviour of the simulation so that it does not match the unsimulated (outer) computation.
>
I think PO views x86utm as some kind of "ultra authority" he can appeal to, to avoid having to actually prove his claims.  [Which is funny, because the logs don't support his claims, but for some reason that passes him by...]
>
Mike.
>

 The problem is that he calls them traces of the emulation that HHH does, and it should never see that main, as it isn't part of what he has defined as the input.

Does he?  I'm not convinced.  Perhaps that's just how you've always interpreted it.  Or perhaps that really is what PO claims.  Anyhow, PO knows his traces start at main().  Perhaps PO just claims or means that the trace /contains/ the simulation that HHH does - that would make sense.  We do need to be clear whether we're looking at simulation trace entries or outer HHH trace entries as they behave a differently (due to misused mutable static data).

 It is clear that this output is the output generated by x86utm,

That's perfectly correct.  X86utm "runs" starting from the main() from its input COFF (object) file which contains main() and everything it calls/simulates.  x86utm logs what it runs - BUT, generally deliberately skips logging of code outside of DDD itself.  This is similar but distinct filtering from HHH's "(global) trace table" which also happens to skip code outside of DDD, as explained below.

NOT just his HHH. As such, it is not the output he claims.

Not convinced, as above.

 It seems clear that he can't figure out how to get the x86UTM program to create just the trace of what HHH sees,

There are two separate concepts here:
-  there is the x86utm *LOG* of executed instructions.  (That's what PO publishes
    from time to time).  Entries are written by x86utm.exe
-  there is the HHH "global *TRACE table*" which is a static array, maintained
    by HHH and inner HHH's that HHH examines when it applies its Abort criteria.
    This is HHH application data within the virtual x86 address space.
The LOG is far more useful for working out definitively what is going on.  For a start, the TRACE table only needs to contain entries of interest for the HHH Abort criteria.  Since those criteria only require knowledge of what instructions within the bounds of C function DDD have done, only instructions within DDD go into the TRACE.  Even if PO LOGs instructions in HHH (as he did in his published "full log" .pdf file) it will still be the case that the TRACE table only contains DDD instructions.
 From the log entries it is clear what HHH will have in its trace table.  Conceptually, each HHH would have its own trace table /if PO hadn't messed up the nested simulation/, but there is just the one output log which (should) cover everything that goes on.

 He *CLAIMS* that HHH actually works on the full trace of DDD going into HHH, but apparently there is no way for him to show such a trace.

That depends on what you mean by "actually works on the full trace".
All the HHH's call DebugStep() to step their simulations, and inspect the result which is the result of the simulated instruction, which could be in HHH or a subroutine, or within the bounds of the C function DDD.  So HHH is "working on the full trace", right?  This is what I think PO says, in response to your claims that his simulations do not "simulate the simulator".
But having inspected the result of the simulated instruction, ONLY INSTRUCTIONS IN DDD are added to the global trace table.  And only the contents of that global trace table is inspected for the purposes of deciding whether to abort.  E.g. the abort criteria may include "no conditional branches between the two calls", but that means "no conditional branches between the two calls recorded in the GLOBAL TRACE TABLE", which in turn means "no conditional branches between the two calls made from within DDD bounds".  And similarly it implies that the two calls in question are within DDD bounds too.
Also, ONLY OUTER HHH uses the global trace table to test the abort criteria - simulated HHH's just skips that bit.

 WHen I last look in detail at the code, his H didn't actually trace into the decider itself, but just assumed that the decider was a emulator and started a nested emulation of it, just like he is currently showing. THe key point is he doesn't consider that the decider is a decider, but thinks of it as just an unconditional emuator, which is of course, and incorrect assumption.

Well, you can see the full published Log trace.  I would say that clearly shows HHH tracing into itself.  [Although as covered elsewhere, there is the issue that behaviour of HHH being traced does not match outer HHH as only outer HHH performs any abort tests.]  Perhaps what you remember is how it worked a long time ago?  [Perhaps when he had what he called the "Global halt decider" which was like moving the termination logic out of user code HHH into x86utm.]

 The problem he had with the version that tried to actually emulate the emulator but he needed the "illegal" static memory to let the decider know the recursion happened, so I suspect he just knows that he isn't actually doing what he claims, but is still using his old tricks, and just trying to hide it.

Hmm, there was H, which never did nested simulations, because H's abort criteria included use of H's own (unsimulated) address for judging its simulation behaviour.  So as soon as H gets to simulating D calling H (at simulation depth 1) it would abort!  Hence no need for handling nested simulations, and no need for a global table.  (I forget whether it actually had a global table, but it arguably didn't need one if the only cases we're interested in are H(D) and D().)
When you get to HH or HHH there will be nested simulations, and that's where PO introduced his "illegal" static memory - as a mechanism for outer to HHH's to receive simulation results from recursively simulated routines.  [More accurately from recursively simulated HHH's.  HHH1 has its own static variable separating its behaviour from HHH...]

 The code does still appear to detecting if it is the "root" decider or not, but I am not sure if the code actually is doing anything.

Yes.  He is still using it to modify the behaviour of simulated HHH's with the result that it does not match that of outer HHH.  You can see that in the .pdf file if you look closely enough.  [If you can be bothered, the key is to focus on the DebugStep() calls, and look at the following instruction which is the simulated instruction (which may itself be a DebugStep op, and so on).]
Mike.