XPost: comp.theory, sci.logic, sci.math
On 6/15/22 3:21 PM, olcott wrote:
#include <stdint.h>
typedef void (*ptr)();
void P(ptr x)
{
if (H(x, x))
HERE: goto HERE;
return;
}
int main()
{
Output("Input_Halts = ", H(P, P));
}
_P()
[00001352](01) 55 push ebp
[00001353](02) 8bec mov ebp,esp
[00001355](03) 8b4508 mov eax,[ebp+08]
[00001358](01) 50 push eax // push P [00001359](03) 8b4d08 mov ecx,[ebp+08]
[0000135c](01) 51 push ecx // push P [0000135d](05) e840feffff call 000011a2 // call H [00001362](03) 83c408 add esp,+08
[00001365](02) 85c0 test eax,eax
[00001367](02) 7402 jz 0000136b
[00001369](02) ebfe jmp 00001369
[0000136b](01) 5d pop ebp
[0000136c](01) c3 ret
Size in bytes:(0027) [0000136c]
(1) It is an easily verified fact that when we assume that H is only an
x86 emulator that the correctly emulated P never reaches its "ret" instruction.
Right, and such an H will never return 0 to say so,
(2) It is an easily verified fact that if H has been adapted to
correctly detect (in a finite number of steps) that the correct and
complete x86 emulation of its input would never each its "ret"
instruction that H could abort its emulation and return 0 to report this.
Except that when H has been modified like that, then the first fact is
no longer true. If H(P,P) DOES abort its simulation and return 0 because
it sees a pattern that it THINKS is a non-halting pattern, then a
CORRECT emualtion of this input will see the following:
P(P) goes through its first 7 instructions as you claim.
P(P) then calls H(P,P).
This H(P,P) will then emulate its input to the point that it THINK it
has seen the non-halting pattern.
This H(P,P) will then abort its simulation of the input tp H(P,P) and
return 0 to its caller
This causes P(P) to Halt, thus PROVING that the pattern is NOT actually
a non-halting pattern, but only was one under the INCORRECT assumption
that H was going to do a non-aborting emulation of its input as assumed
in (1). This is UNSOUND logic, as it actually does abort.
(3) When the halt status criteria is defined as correctly determining
whether or not an x86 emulated input would ever reach its "ret"
instruction then it becomes and easily verified fact H(P,P) could
correctly reject its input as non-halting.
So, you have to decide WHICH H you are going to make the H that is
supposed to get the right answer.
Is it the H that actually does the correct emulation, which creates the non-halting P(P), but never answers, or
Is it the H that actually aborts is emulation (and thus it isn't
correct) and returns the value 0 to ALL callers of H(P,P), and thus
makes P(P) a Halting Programs, and thus the 0 answer that H returned
wrong, or
Is this an H that doesn't return the same answer for the quesiton H(P,P)
and thus proves itself NOT to be a "pure function" or even a
"Computation" (according to Computaiton Theory) and thus not eligable to
be a decider in computation theory.
You get you choice, which way are you wrong.
Correct deductive inference proves that all of these things are true
without any need what-so-ever to see either the source-code or the
execution trace of H.
Nope. You have just proved that H can't actually be the thing you assume
it to be. If you want to argue the 3rd case, that H actually is a Pure
function of its input but somehow breaks the basic property of always
behaving the same to all callers, then you very much DO need to prove
this asserting, and show at least some code that actually does this.
This basic proof would be to show the error in the proof of this by
showing the first deterministic instruction in H that results in
differing results in the two paths.
Until you actually do this, it is just you claiming that your black cat
can be a white dog.
The one thing that is not proved is whether or not an actual encoded
H(P,P) does indeed correctly determine that is input would never reach
its "ret" instruction as a pure function of its inputs.
Halting problem undecidability and infinitely nested simulation (V5)
https://www.researchgate.net/publication/359984584_Halting_problem_undecidability_and_infinitely_nested_simulation_V5
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)