XPost: comp.theory
Op 29.jul.2024 om 16:07 schreef olcott:
HHH(Infinite_Recursion) and HHH(DDD) show the same non-halting
behavior pattern in their derived execution traces of their
inputs.
Correct emulation is defined as emulating the machine language
input according to the x86 semantics specified by this input.
For DDD correctly emulated by HHH this includes HHH emulating
itself emulating DDD according to the x86 semantics of itself.
HHH(DDD) shows the exact same execution trace behavior pattern
as HHH(Infinite_Recursion) where 3-4 instructions are repeated
with no conditional branch instructions in this trace that could
prevent them from endlessly repeating.
void Infinite_Recursion()
{
Infinite_Recursion();
}
No, the HHH that aborts after N cycles has a similar behaviour as
void Finite_Recursion (int N) {
if (N > 0) Finite_Recursion (N - 1);
}
Both HHH and Finite_Recursion stop after N recursions and then halt.
Infinite recursion is only in your dreams.
_Infinite_Recursion()
[0000215a] 55 push ebp ; 1st line
[0000215b] 8bec mov ebp,esp ; 2nd line
[0000215d] e8f8ffffff call 0000215a ; 3rd line
[00002162] 5d pop ebp
[00002163] c3 ret
Size in bytes:(0010) [00002163]
*THREE lines repeat with no conditional branch instructions*
Begin Local Halt Decider Simulation Execution Trace Stored at:113934 [0000215a][00113924][00113928] 55 push ebp ; 1st line
[0000215b][00113924][00113928] 8bec mov ebp,esp ; 2nd line [0000215d][00113920][00002162] e8f8ffffff call 0000215a ; 3rd line [0000215a][0011391c][00113924] 55 push ebp ; 1st line
[0000215b][0011391c][00113924] 8bec mov ebp,esp ; 2nd line [0000215d][00113918][00002162] e8f8ffffff call 0000215a ; 3rd line
Local Halt Decider: Infinite Recursion Detected Simulation Stopped
Since HHH has conditional branch instructions, it can halt after N
recursions, when simulating itself.
The simulated HHH runs 1 cycle behind the simulating HHH. When the
simulating HHH aborts, the simulated HHH has only one cycle to go,
before it would also abort and halt.
If you cannot see that the above x86 machine code proves that
it will never halt then you can't possibly understand what I
have been saying.
We do not understand what you say, because it is contradictory. The
semantics of the x86 language does not allow to skip the last few
instructions of a halting program, the last cycle of its simulation.
Therefore, according to olcott's own criterion, the simulation is
incorrect, as follows from the semantics of the x86 language.
The first three lines of _Infinite_Recursion() repeat and there
are no conditional branch in that sequence that can possibly keep
it from repeating forever.
HHH(DDD) is the exact same pattern is shown below. The first
four lines of DDD repeat and there are are no conditional branch
in that sequence that can possibly keep it from repeating forever.
Only, because you hide the conditional branch instructions in HHH
between two successive starts of DDD.
void DDD()
{
HHH(DDD);
}
_DDD()
[00002177] 55 push ebp ; 1st line [00002178] 8bec mov ebp,esp ; 2nd line
[0000217a] 6877210000 push 00002177 ; push DDD
[0000217f] e853f4ffff call 000015d7 ; call HHH
[00002184] 83c404 add esp,+04
[00002187] 5d pop ebp
[00002188] c3 ret
Size in bytes:(0018) [00002188]
*FOUR lines repeat with no conditional branch instructions*
Because you are cheating by hiding that the call instruction goes into
HHH, which has conditional branch instructions.
Begin Local Halt Decider Simulation Execution Trace Stored at:113895 [00002177][00113885][00113889] 55 push ebp ; 1st line
[00002178][00113885][00113889] 8bec mov ebp,esp ; 2nd line [0000217a][00113881][00002177] 6877210000 push 00002177 ; push DDD [0000217f][0011387d][00002184] e853f4ffff call 000015d7 ; call HHH
[00002177][0015e2ad][0015e2b1] 55 push ebp ; 1st line
[00002178][0015e2ad][0015e2b1] 8bec mov ebp,esp ; 2nd line [0000217a][0015e2a9][00002177] 6877210000 push 00002177 ; push DDD [0000217f][0015e2a5][00002184] e853f4ffff call 000015d7 ; call HHH
Local Halt Decider: Infinite Recursion Detected Simulation Stopped
The programmer made an error by programming HHH to print this message.
There is no infinite recursion. There were only two recursions. Two is
not infinite. Something the programmer apparently does not understand.
Because HHH has no idea that it is calling itself HHH only sees
the same Infinite Recursion behavior pattern that it saw with Infinite_Recursion().
The programmer made the error to think that two recursions is enough to
decide that there are infinite recursion. The programmer also made the
error to ignore the conditional branch instructions in the simulated
input HHH.
DDD is a misleading and unneeded complication. It is easy to eliminate DDD:
int main() {
return HHH(main);
}
This has the same problem. This proves that the problem is not in DDD,
but in HHH, which halts when it aborts the simulation, but it decides
that the simulation of itself does not halt.
It shows that HHH cannot possibly simulate itself correctly.
Olcott repeats his belief again without any evidence.
No matter how much olcott wants it to be correct, or how many times
olcott repeats that it is correct, it does not change the fact that such
a simulation is incorrect, because it is unable to reach the end.
Olcott's own claim that the simulated HHH does not reach its end
confirms it. The trace he has shown also proves that HHH cannot reach
the end of its own simulation. So, his own claims prove that it is true
that HHH cannot possibly simulate itself up to the end, which makes the simulation incomplete and, therefore, incorrect.
Sipser would agree that this incorrect simulation cannot be used to
detect a non-halting behaviour.
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)