On 8/15/2021 9:46 AM, Mike Terry wrote:
> On 14/08/2021 22:20, Jeff Barnett wrote:
>> On 8/14/2021 2:43 PM, Ben Bacarisse wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> The P(P) of main() only halts because...
>>>
>>> As you say, P(P) halts.
>>>
>>>> *Halting computation* is any computation that eventually reaches its
>>>> own final state. This criteria divides computations that halt from
>>>> those that merely stop running because their simulation was aborted.
>>>
>>> No.  There is no "special kind of halting".  The computation M(I) either
>>> halts or it does not.  H(M, I) should be false if, and only if, M(I)
>>> does not halt.
>>>
>>>> void P(u32 x)
>>>> {
>>>>    if (H(x, x))
>>>>      HERE: goto HERE;
>>>> }
>>>
>>> P(P) halts, yet H(P, P) is false.  That's the wrong answer.
>>>
>>> Why are you still hiding H?  Is it because you have still not figured
>>> out how to nest a call to the simulator you are using?  Fortunately "we"
>>> (i.e. everyone but you) can see that H is wrong without even seeing the
>>> code.  Who is included in the "we" of the subject line?  Have you found
>>> someone else who thinks that false is the correct return from a partial
>>> halt decider called with arguments that represent a halting computation?
>>
>> I have questions about the PO simulator I hope someone can answer. It
>> perhaps concerns memory mapping:
>
>> First - is every instance of a use at different levels in its own
>> address space?
>
> I've tried to get PO to clarify that, and it always /seems/ that he is
> suggesting yes [while avoiding any direct answer] but I have no
> confidence whatsoever that he understands what everybody else would
> understand by "its own address space".
>

There is a single contiguous block of RAM that is used by all of the
virtual machine and the halt decider. Whenever H is called it creates a
separate context having its own Registers, RAM and stack space. It
performs its x86 emulation on its input virtual machine in the separate
process context. Just like recursion the executable code of every
instance of P and H are at the same fixed machine address.

> He has definitely said that each simulation has its own stack and
> registers, but my bet would be that they are more like your typical OS
> threads, running in the same address space.  (We could probably find out
> by quizzing him on sharing of globals etc. and giving him concrete
> examples which he could understand.  But it might take a lot of work,
> and for what at the end?  Or more reasonably, if he published all his
> source code as he maintained he would for around two years, we could
> answer these sorts of questions for ourselves...)
>

Until people quit refuting this very obvious truth they consistently
prove that they are far too disingenuous to deserve any additional
details that would only give them an excuse to make sure that they
always go off on tangents and dodge the key relevant points:

While H remains in pure simulation mode simulating the input to H(P,P)
this simulated input never stops running thus conclusively proving that
when H decides this input never halts it is correct.

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

_P()
[00000c36](01) 55 push ebp
[00000c37](02) 8bec mov ebp,esp
[00000c39](03) 8b4508 mov eax,[ebp+08] // 2nd Param
[00000c3c](01) 50 push eax
[00000c3d](03) 8b4d08 mov ecx,[ebp+08] // 1st Param
[00000c40](01) 51 push ecx
[00000c41](05) e820fdffff call 00000966 // call H
[00000c46](03) 83c408 add esp,+08
[00000c49](02) 85c0 test eax,eax
[00000c4b](02) 7402 jz 00000c4f
[00000c4d](02) ebfe jmp 00000c4d
[00000c4f](01) 5d pop ebp
[00000c50](01) c3 ret
Size in bytes:(0027) [00000c50]

_main()
[00000c56](01) 55 push ebp
[00000c57](02) 8bec mov ebp,esp
[00000c59](05) 68360c0000 push 00000c36 // push P
[00000c5e](05) 68360c0000 push 00000c36 // push P
[00000c63](05) e8fefcffff call 00000966 // call H(P,P)
[00000c68](03) 83c408 add esp,+08
[00000c6b](01) 50 push eax
[00000c6c](05) 6857030000 push 00000357
[00000c71](05) e810f7ffff call 00000386
[00000c76](03) 83c408 add esp,+08
[00000c79](02) 33c0 xor eax,eax
[00000c7b](01) 5d pop ebp
[00000c7c](01) c3 ret
Size in bytes:(0039) [00000c7c]

machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
[00000c56][0010172a][00000000] 55 push ebp
[00000c57][0010172a][00000000] 8bec mov ebp,esp
[00000c59][00101726][00000c36] 68360c0000 push 00000c36 // push P
[00000c5e][00101722][00000c36] 68360c0000 push 00000c36 // push P
[00000c63][0010171e][00000c68] e8fefcffff call 00000966 // call H(P,P)

Begin Local Halt Decider Simulation at Machine Address:c36
[00000c36][002117ca][002117ce] 55 push ebp
[00000c37][002117ca][002117ce] 8bec mov ebp,esp
[00000c39][002117ca][002117ce] 8b4508 mov eax,[ebp+08]
[00000c3c][002117c6][00000c36] 50 push eax // push P
[00000c3d][002117c6][00000c36] 8b4d08 mov ecx,[ebp+08]
[00000c40][002117c2][00000c36] 51 push ecx // push P
[00000c41][002117be][00000c46] e820fdffff call 00000966 // call H(P,P)

[00000c36][0025c1f2][0025c1f6] 55 push ebp
[00000c37][0025c1f2][0025c1f6] 8bec mov ebp,esp
[00000c39][0025c1f2][0025c1f6] 8b4508 mov eax,[ebp+08]
[00000c3c][0025c1ee][00000c36] 50 push eax // push P
[00000c3d][0025c1ee][00000c36] 8b4d08 mov ecx,[ebp+08]
[00000c40][0025c1ea][00000c36] 51 push ecx // push P
[00000c41][0025c1e6][00000c46] e820fdffff call 00000966 // call H(P,P)
Local Halt Decider: Infinite Recursion Detected Simulation Stopped

>> Second - if not, is there any way to know when an address is reported,
>> which simulator instance is being reported on?
>
> I suggested he needed to provide that last year.  And at one point he
> DID change his trace to show the emulation level, so it's not like
> there's any coding difficulty!  But then it was perfectly clear that he
> was correlating trace entries together from completely separate
> emulation levels, so the illusion that it was a "loop" in the normal
> (single) processor-trace sense was lessened.  He subsequently removed
> the column, claiming as excuse that it confused people.
>
> I'd say this is PO misunderstanding the difference between
> call-recursion and emulation-recursion.  The former can /only/ be broken
> by code at the deepest recursion level which then percolates up to the
> top level, like when we calculate n factorial recursively.
> Emulation-recursion /can/ also break out this way, but with emulation
> there is a second possibility - the break can be from the /top/ level
> which simply decides not to emulate any more.  The fact that the deepest
> inner emulations appear to be repeating doesn't mean that they will go
> on forever, because an outer level can always just give up emulating and
> get on with whatever is next.
>

If I did not understand this then I would have not explained it this
same way many dozens of times.

> I suppose without an emulation-id column we can probably work stuff out
> based on the overall flow of the trace together with knowledge about the
> program and what H is doing and so on.  (But why should this be required
> when it's an essential part of the meaning of a trace entry?)
>
>> When the dumb bunny (PO expression) notes that the same address is
>> reached a second time without a conditional branch being executed, is
>> there any assurance that the addresses are noted from the same
>> instance of the simulation?
>
> I can give you an assurance of exactly the opposite - they are
> definitely from /different/ emulation levels!  (I think you know that,
> right?) PO tries to present them to look as much as possible like a
> pattern of behaviour for a /single/ processor, because then he would
> have "call recursion" which can only break inner-to-outer, and his
> "processor trace" could provide some level of evidence that that won't
> happen. (Also I'm remebering his recent remarks about the processor
> "[..having no way to escape from the recursion..]" which might be
> explained as PO not understanding the call/recursion distinction...)
>

I want to eliminate the extra 396 pages of extraneous detail because
people here are finding it next to impossible to understand 7 lines of
x86 code when this code has been repeatedly explained to them hundreds
of times over many months. Providing an extra 396 pages of detail
certainly cannot possibly help in this case.

> In the past PO has said his rule applies equally for call-recursion and
> emulation-recursion, no difference, while repeating something about
> "equivalent computation", but he has no real /understanding/ of that
> phrase and certainly no /proof/ of soundness even for the simple
> call-recursion case, so it's just the usual unsupported claims.  (And
> there is no prospect of ever going further than this - PO is simply not
> capable of "proving" anything and I doubt he understands what that even
> means.)

The emulation recursion and the call recursion have computationally
equivalent halting behavior as proven by the following execution trace
compared to the above execution trace of the simulation of P on P.

void Infinite_Recursion()
{ Infinite_Recursion();
}

int main()
{ Output("Input_Halts = ", H0((u32)Infinite_Recursion));
}

_Infinite_Recursion()
[00000dc2](01) 55 push ebp
[00000dc3](02) 8bec mov ebp,esp
[00000dc5](05) e8f8ffffff call 00000dc2
[00000dca](01) 5d pop ebp
[00000dcb](01) c3 ret
Size in bytes:(0010) [00000dcb]

_main()
[00000e72](01) 55 push ebp
[00000e73](02) 8bec mov ebp,esp
[00000e75](05) 68c20d0000 push 00000dc2
[00000e7a](05) e873fdffff call 00000bf2
[00000e7f](03) 83c404 add esp,+04
[00000e82](01) 50 push eax
[00000e83](05) 6823030000 push 00000323
[00000e88](05) e8c5f4ffff call 00000352
[00000e8d](03) 83c408 add esp,+08
[00000e90](02) 33c0 xor eax,eax
[00000e92](01) 5d pop ebp
[00000e93](01) c3 ret
Size in bytes:(0034) [00000e93]

machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
....[00000e72][00101a85][00000000] 55 push ebp
....[00000e73][00101a85][00000000] 8bec mov ebp,esp
....[00000e75][00101a81][00000dc2] 68c20d0000 push 00000dc2
....[00000e7a][00101a7d][00000e7f] e873fdffff call 00000bf2

Begin Local Halt Decider Simulation at Machine Address:dc2
....[00000dc2][00211b29][00211b2d] 55 push ebp
....[00000dc3][00211b29][00211b2d] 8bec mov ebp,esp
....[00000dc5][00211b25][00000dca] e8f8ffffff call 00000dc2
....[00000dc2][00211b21][00211b29] 55 push ebp
....[00000dc3][00211b21][00211b29] 8bec mov ebp,esp
....[00000dc5][00211b1d][00000dca] e8f8ffffff call 00000dc2
Local Halt Decider: Infinite Recursion Detected Simulation Stopped

....[00000e7f][00101a85][00000000] 83c404 add esp,+04
....[00000e82][00101a81][00000000] 50 push eax
....[00000e83][00101a7d][00000323] 6823030000 push 00000323
---[00000e88][00101a7d][00000323] e8c5f4ffff call 00000352
Input_Halts = 0
....[00000e8d][00101a85][00000000] 83c408 add esp,+08
....[00000e90][00101a85][00000000] 33c0 xor eax,eax
....[00000e92][00101a89][00100000] 5d pop ebp
....[00000e93][00101a8d][00000044] c3 ret
Number_of_User_Instructions(18)
Number of Instructions Executed(823)

>> And finally, how can one determine if it's the same address twice
>> without doing some sort of compare and branch?
>
> OK, for PO's H, there are obviously hidden conditional branch
> instructions within H, which is why PO has to come up with some wording
> to convince himself that H can be totally ignored for whatever reason.

Because H only acts as a pure simulator of its input until after its
halt status decision has been made it has no behavior that can possibly
effect the behavior of its input. Because of this H screens out its own
address range in every execution trace that it examines. This is why we
never see any instructions of H in any execution trace after an input
calls H.

> But drilling down on this seems overkill when PO hasn't even presented
> any plausible argument (let alone proof!) that the detection rule being
> used is sound.

It is the same rule used in the Infinite_Recursion() shown above.

> What would we be trying to disprove and why? :)  PO has
> agreed that H^(H^) halts, and that H(H^,H^) returns not-halting, so
> that's it.
>

int main(){ P(P); } and int main(){ Simulate(P,P); } are computationally
equivalent and have the same halting behavior.

Because the P of H(P,P) is at a different point in the execution trace
than the above two cases it is not computationally equivalent to the
above two cases. Because it is not computationally equivalent it can
have different halting behavior.

> At least in the end it must be PO's responsibility to present /proofs/
> of anything he claims, but now we've gone like 100 miles beyond his
> capabilities - a complete non-starter...
>
> Mike.
>

When people point out any of my "mistakes" (besides typos) they are only
pointing out their own lack of understanding.

--
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein