XPost: comp.theory, sci.logic, sci.math
On 6/23/22 2:14 PM, olcott wrote:
On 6/23/2022 3:19 AM, Malcolm McLean wrote:
On Wednesday, 22 June 2022 at 16:50:31 UTC+1, Ben Bacarisse wrote:
Malcolm McLean <malcolm.ar...@gmail.com> writes:
On Wednesday, 22 June 2022 at 13:16:36 UTC+1, olcott wrote:
On 6/22/2022 2:55 AM, Malcolm McLean wrote:
On Wednesday, 22 June 2022 at 04:10:45 UTC+1, olcott wrote:
On 6/21/2022 9:52 PM, Richard Damon wrote:
Right, and P(P) reaches the ret instruction of H(P,P) returns 0, >>>>>>>> so H
was incorrect in its mapping, since the behavior of P(P) is the >>>>>>>> DEFINITION of the behavior of H(P,P),
Linz and others were aware that: A halt decider must compute the >>>>>>> mapping
from its inputs to an accept or reject state on the basis of the >>>>>>> actual
behavior that is actually specified by these inputs.
Linz and others made the false assumption that the actual
behavior that
is actually specified by the inputs to a simulating halt decider >>>>>>> is not
the same as the direct execution of these inputs. They were
unaware of
this because no one previously fully examined a simulating halt
decider
ever before.
especially if that is what P calls
and P is claimed to be built by the Linz template.
So, either P isn't built right, or H isn't built fight, or H is >>>>>>>> wrong.
You've dry-run P(P) and it doesn't halt. Additionally the halt
decider H
reports it as non-halting. So it's reasonable to assume that H is
correct.
However, when run, P(P) halts. So what are we to conclude? That "the >>>>>> actual behaviour that is actually specified by the inputs to a
simulating
halt decider is not the same as the direct execution of these
inputs"?
That is an actual immutable verified fact.
That's your conclusion from your observations and reasoning. You've
dry-run P(P), and it doesn't halt. You've run H on P(P), and it
reports "non-halting". You've run P(P), and it halts. So one
explanation is the one you've given but, as I said, that explanation
has rather far-reaching consequences.
There is only one explanation. What you call the "dry-run" is not that
same as the P(P). We've known this since the "line 15 commented out"
days. There are two computations -- one that is not stopped and one
that is, the "dry-run" and the run, the "simulation of the input to
H(P,P)" and P(P). All PO is doing is trying to find words that hide
what's going on.
I'm a scientists, not a mathematician.
The example I always use is that you are doing an energy budget for
tigers.
You work how much they use on running about, lactating, maintaining their
body temperature, and so on.
Now let's say that you find that all results are within a few
percentage points
of a similar budget done for lions. You'd instantly accept this data.
Now let's say that the results are wildly different from a previous
budget done
for lions. You wouldn't just accept that data. You'd check. You'd want to
understand the reasons tigers spend far less energy on movement than
lions.
Now let's say that the result show that tigers use more energy than they
take in food. Would you instantly conclude that the law of
conservation of
energy must be incorrect?
The third is what PO is doing.
I rewrote this up so that sufficiently competent software engineers
would be able to confirm that the following is correct:
To fully understand this code a software engineer must be an expert in:
the C programming language, the x86 programming language, exactly how C translates into x86 and the ability to recognize infinite recursion at
the x86 assembly language level. No knowledge of the halting problem is required.
The ordinary semantics of standard C and the conventional x86 language
are the entire semantics required to conclusively prove that H(P,P) does correctly determine that its correct and complete x86 emulation of its
input would never reach the "ret" instruction of P.
In computer science terminology this means that complete and correct emulation P by H would never reach its final state and halt.
The dependency relationship that P(P) has on H(P,P) causes its behavior
to be quite different than the complete and correct x86 emulation of the input to H(P,P) that has no such dependency relationship.
As shown below because P(P) depends on the return value of H(P,P) it has different behavior than the correctly emulated input to H(P,P).
The correctly emulated input to H(P,P) remains stuck in recursive
emulation that never gets to the point of receiving a return value from
H, thus lacks the dependency of the executed P(P).
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
return;
}
int main()
{
P(P);
}
_P()
[000011f0](01) 55 push ebp
[000011f1](02) 8bec mov ebp,esp
[000011f3](03) 8b4508 mov eax,[ebp+08]
[000011f6](01) 50 push eax
[000011f7](03) 8b4d08 mov ecx,[ebp+08]
[000011fa](01) 51 push ecx
[000011fb](05) e820feffff call 00001020
[00001200](03) 83c408 add esp,+08
[00001203](02) 85c0 test eax,eax
[00001205](02) 7402 jz 00001209
[00001207](02) ebfe jmp 00001207
[00001209](01) 5d pop ebp
[0000120a](01) c3 ret
Size in bytes:(0027) [0000120a]
_main()
[00001210](01) 55 push ebp
[00001211](02) 8bec mov ebp,esp
[00001213](05) 68f0110000 push 000011f0
[00001218](05) e8d3ffffff call 000011f0
[0000121d](03) 83c404 add esp,+04
[00001220](02) 33c0 xor eax,eax
[00001222](01) 5d pop ebp
[00001223](01) c3 ret
Size in bytes:(0020) [00001223]
machine stack stack machine assembly
address address data code language
======== ======== ======== ========= ============= [00001210][00101fba][00000000] 55 push ebp [00001211][00101fba][00000000] 8bec mov ebp,esp [00001213][00101fb6][000011f0] 68f0110000 push 000011f0 // push P [00001218][00101fb2][0000121d] e8d3ffffff call 000011f0 // call P [000011f0][00101fae][00101fba] 55 push ebp // enter executed P
[000011f1][00101fae][00101fba] 8bec mov ebp,esp [000011f3][00101fae][00101fba] 8b4508 mov eax,[ebp+08] [000011f6][00101faa][000011f0] 50 push eax // push P
[000011f7][00101faa][000011f0] 8b4d08 mov ecx,[ebp+08] [000011fa][00101fa6][000011f0] 51 push ecx // push P
[000011fb][00101fa2][00001200] e820feffff call 00001020 // call H
Begin Simulation Execution Trace Stored at:21206e
Address_of_H:1020
[000011f0][0021205a][0021205e] 55 push ebp // enter emulated P
[000011f1][0021205a][0021205e] 8bec mov ebp,esp [000011f3][0021205a][0021205e] 8b4508 mov eax,[ebp+08] [000011f6][00212056][000011f0] 50 push eax // push P
[000011f7][00212056][000011f0] 8b4d08 mov ecx,[ebp+08] [000011fa][00212052][000011f0] 51 push ecx // push P
[000011fb][0021204e][00001200] e820feffff call 00001020 // call emulated H Infinitely Recursive Simulation Detected Simulation Stopped
H knows its own machine address and on this basis it can easily examine
its stored execution_trace of P (see above) to determine:
(a) P is calling H with the same arguments that H was called with.
(b) No instructions in P could possibly escape this otherwise infinitely recursive emulation.
(c) H aborts its emulation of P before its call to H is emulated.
[00001200][00101fae][00101fba] 83c408 add esp,+08 // return to executed P
[00001203][00101fae][00101fba] 85c0 test eax,eax [00001205][00101fae][00101fba] 7402 jz 00001209 [00001209][00101fb2][0000121d] 5d pop ebp [0000120a][00101fb6][000011f0] c3 ret // return from
executed P
[0000121d][00101fba][00000000] 83c404 add esp,+04 [00001220][00101fba][00000000] 33c0 xor eax,eax [00001222][00101fbe][00100000] 5d pop ebp [00001223][00101fc2][00000000] c3 ret // ret from main
Number of Instructions Executed(878) / 67 = 13 pages
(b) is invalid, so H is not correct.
H's criteria of being defined to deside on ITS OWN compelete and correct emulation is basicaly saying that cats that are dog can bark, thus there
exists cats that bark.
ANY simulating decider H that somehow decides that its input is
non-halting and stops its simulations doesn't do a complete and correct simulation, and thus it is WRONG to say that was a basis for its decision.
Until you can show how a simulator can simulate an unbounded number of
steps (aka infinite number) in a finite number of steps, you have an
impossible premise.
That means you need to find a computation system that can do infinite
work in finite time for your arguement to be valid.
YOU FAIL.
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)