H(P,P)==0 as a pure function of its inputs is fully operational

1 view
Skip to first unread message

olcott

unread,
Jun 17, 2022, 10:07:40 PMJun 17
to
When a simulating halt decider rejects all inputs as non-halting
whenever it correctly detects (in a finite number of steps) that its
correct and complete simulation of its input would never reach the final
state of this input that all [these] inputs (including pathological
inputs) are decided correctly.

*computation that halts* … the Turing machine will halt whenever it
enters a final state. (Linz:1990:234)

Linz, Peter 1990. An Introduction to Formal Languages and Automata.
Lexington/Toronto: D. C. Heath and Company. (317-320)

void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
return;
}

int main()
{
Output("Input_Halts = ", H((u32)P, (u32)P));
}

_P()
[0000127e](01) 55 push ebp
[0000127f](02) 8bec mov ebp,esp
[00001281](03) 8b4508 mov eax,[ebp+08]
[00001284](01) 50 push eax
[00001285](03) 8b4d08 mov ecx,[ebp+08]
[00001288](01) 51 push ecx
[00001289](05) e820feffff call 000010ae
[0000128e](03) 83c408 add esp,+08
[00001291](02) 85c0 test eax,eax
[00001293](02) 7402 jz 00001297
[00001295](02) ebfe jmp 00001295
[00001297](01) 5d pop ebp
[00001298](01) c3 ret
Size in bytes:(0027) [00001298]

_main()
[0000129e](01) 55 push ebp
[0000129f](02) 8bec mov ebp,esp
[000012a1](05) 687e120000 push 0000127e
[000012a6](05) 687e120000 push 0000127e
[000012ab](05) e8fefdffff call 000010ae
[000012b0](03) 83c408 add esp,+08
[000012b3](01) 50 push eax
[000012b4](05) 680f040000 push 0000040f
[000012b9](05) e8a0f1ffff call 0000045e
[000012be](03) 83c408 add esp,+08
[000012c1](02) 33c0 xor eax,eax
[000012c3](01) 5d pop ebp
[000012c4](01) c3 ret
Size in bytes:(0039) [000012c4]

machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
...[0000129e][0010201f][00000000] 55 push ebp
...[0000129f][0010201f][00000000] 8bec mov ebp,esp
...[000012a1][0010201b][0000127e] 687e120000 push 0000127e // push P
...[000012a6][00102017][0000127e] 687e120000 push 0000127e // push P
...[000012ab][00102013][000012b0] e8fefdffff call 000010ae // call H

*Begin Local Halt Decider Simulation* Execution Trace Stored at:2120d3
...[0000127e][002120bf][002120c3] 55 push ebp
...[0000127f][002120bf][002120c3] 8bec mov ebp,esp
...[00001281][002120bf][002120c3] 8b4508 mov eax,[ebp+08]
...[00001284][002120bb][0000127e] 50 push eax // push P
...[00001285][002120bb][0000127e] 8b4d08 mov ecx,[ebp+08]
...[00001288][002120b7][0000127e] 51 push ecx // push P
...[00001289][002120b3][0000128e] e820feffff call 000010ae // call H
*Infinitely Recursive Simulation Detected Simulation Stopped*

H knows its own machine address and on this basis
H recognizes that P is calling H with its same arguments that it
was called with and there are no instructions preceding this call that
could possibly escape infinitely recursive emulation so H aborts its
emulation of P before P even makes its first call to H.

...[000012b0][0010201f][00000000] 83c408 add esp,+08
...[000012b3][0010201b][00000000] 50 push eax
...[000012b4][00102017][0000040f] 680f040000 push 0000040f
---[000012b9][00102017][0000040f] e8a0f1ffff call 0000045e
Input_Halts = 0
...[000012be][0010201f][00000000] 83c408 add esp,+08
...[000012c1][0010201f][00000000] 33c0 xor eax,eax
...[000012c3][00102023][00100000] 5d pop ebp
...[000012c4][00102027][00000004] c3 ret
Number of Instructions Executed(1134) == 17 pages



Halting problem undecidability and infinitely nested simulation (V5)

https://www.researchgate.net/publication/359984584_Halting_problem_undecidability_and_infinitely_nested_simulation_V5

olcott

unread,
Jun 17, 2022, 10:15:03 PMJun 17
to
H knows its own machine address and on this basis:
(a) H recognizes that P is calling H with its same arguments that it was
called with.
(b) There are no instructions in P that could possibly escape this
infinitely recursive emulation.
(c) H aborts its emulation of P before P even makes its first call to H.

> ...[000012b0][0010201f][00000000] 83c408     add esp,+08
> ...[000012b3][0010201b][00000000] 50         push eax
> ...[000012b4][00102017][0000040f] 680f040000 push 0000040f
> ---[000012b9][00102017][0000040f] e8a0f1ffff call 0000045e
> Input_Halts = 0
> ...[000012be][0010201f][00000000] 83c408     add esp,+08
> ...[000012c1][0010201f][00000000] 33c0       xor eax,eax
> ...[000012c3][00102023][00100000] 5d         pop ebp
> ...[000012c4][00102027][00000004] c3         ret
> Number of Instructions Executed(1134) == 17 pages
>
>
>
> Halting problem undecidability and infinitely nested simulation (V5)
>
> https://www.researchgate.net/publication/359984584_Halting_problem_undecidability_and_infinitely_nested_simulation_V5
>


--
Copyright 2022 Pete Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer

olcott

unread,
Jun 17, 2022, 10:20:20 PMJun 17
to
(c) H aborts its emulation of P before P its call to H is invoked.

olcott

unread,
Jun 17, 2022, 10:31:24 PMJun 17
to

Richard Damon

unread,
Jun 17, 2022, 11:18:22 PMJun 17
to
On 6/17/22 10:07 PM, olcott wrote:
> When a simulating halt decider rejects all inputs as non-halting
> whenever it correctly detects (in a finite number of steps) that its
> correct and complete simulation of its input would never reach the final
> state of this input that all [these] inputs (including pathological
> inputs) are decided correctly.
>
> *computation that halts* … the Turing machine will halt whenever it
> enters a final state. (Linz:1990:234)

Right, so for H to have CORRECTLY decided non-halting, then the TURING
MACHINE that it was deciding on must not halt. Since H(P,P) is defined
to be deciding on P(P) (or P was built wrong) and since P(P) as a
directly run function returns if H(P,P) returns 0, that can not be a
correct answer.

Your claim that this isn't what H(P,P) means, just says that you lied
that P was built by the Linz formula and your whole proof just becomes a
lie.
But that isn't the criteria. The criteria is will the funtion provided
as an input return when called with the second parameter.

It doesn't matter that the code in the C function doesn't have any
stopping code, it is enough that H contains it, since that H is part of
the mathematical/computatinal function P and part of its behaivor.

If H doesn't have a condition to stop it, the H fails to be a decider.

Which way does H fail?

Mr Flibble

unread,
Jun 18, 2022, 9:23:38 AMJun 18
to
void Px(u32 x)
{
H(x, x);
return;
}

int main()
{
Output("Input_Halts = ", H((u32)Px, (u32)Px));
}

...[000013e8][00102357][00000000] 83c408 add esp,+08
...[000013eb][00102353][00000000] 50 push eax
...[000013ec][0010234f][00000427] 6827040000 push 00000427
---[000013f1][0010234f][00000427] e880f0ffff call 00000476
Input_Halts = 0
...[000013f6][00102357][00000000] 83c408 add esp,+08
...[000013f9][00102357][00000000] 33c0 xor eax,eax
...[000013fb][0010235b][00100000] 5d pop ebp
...[000013fc][0010235f][00000004] c3 ret
Number of Instructions Executed(16120)

It gets the answer wrong, i.e. input has not been decided correctly.
QED.

/Flibble

olcott

unread,
Jun 18, 2022, 9:35:41 AMJun 18
to
(X) H(P,P) correctly determines (in a finite number of steps) that the
correct and complete x86 emulation of its input would never reach the
"ret" instruction (AKA final state) of this input.

(Y) computation that halts … the Turing machine will halt whenever it
enters a final state. (Linz:1990:234)

(Z) H(P,P) has correctly determined that its input is non-halting.

When we know that X & Y proves Z and we know X & Y then Z is proved.
*Failing to agree with this last line is sufficient evidence of dishonesty*



Linz, Peter 1990. An Introduction to Formal Languages and Automata.
Lexington/Toronto: D. C. Heath and Company. (317-320)


Mr Flibble

unread,
Jun 18, 2022, 9:53:29 AMJun 18
to

olcott

unread,
Jun 18, 2022, 9:59:41 AMJun 18
to
Sufficient evidence of dishonesty!

Richard Damon

unread,
Jun 18, 2022, 10:14:51 AMJun 18
to
Except that you haven't actually established X, not for the H that you
are talking about no, so you are the one being dishonest to claim it.

You are being intentionally deceitful by calling two different
algorithms the same name, and ignoring that they are actually different
algorithms.

You have the H that is really Hn that never aborts, but is a pure
emulator, and you have the H that is really Ha that does abort and
assumes that the P it is given that is supposed to be calling Ha is
actually calling Hn, and thus either H isn't a pure functions as it
switches between the algorithm of Hn and Ha depending on things not part
of its input, or it isn't based on a correct emulation as it "sees" Ha
as Hn.

FAIL.

olcott

unread,
Jun 19, 2022, 2:24:51 PMJun 19
to
On 6/17/2022 9:07 PM, olcott wrote:
All of the code including several halt deciders that use different
methods for pathological inputs and take 0,1,2 arguments, along with the
complete x86 emulator fits in a 131K zip file and is configured as a
visual studio project. *I just got this done right now*

The prior pathological input decider required static local data that was
stored directly in the function body. it construed infinitely nested
simulation as infinite recursion.

The current pathological input decider is a pure function of its inputs.
The infinite loop and infinite recursion deciders remain the same.

This is the the design of the pathological input decider :

H knows its own machine address and on this basis:
(a) H recognizes that P is calling H with the same arguments that H was
called with.
(b) There are no instructions in P that could possibly escape this
infinitely recursive emulation.
(c) H aborts its emulation of P before P its call to H is invoked.


Richard Damon

unread,
Jun 19, 2022, 2:36:47 PMJun 19
to
The problem is your rule is incorrect, P doesn't need an instruction in
the code in P before the call to H to terminate the recurssion, because
the instruction to terminate the recursion exists in H,

If H aborts its simulation and returns the 0 to P, then P halts, and
thus H was wrong to decide its input was non-halting.

In all the cases, P is asking H to decide on what it will itself with
the input it was given, and it does the opposite.

The parameters given to H don't actually ask that question, then you
formed P incorrectly, so your "proof" is invalid.

If you CAN'T ask H that question, then H fails to even pretend to be a
universal halt decider, not even being able to be asked the key question
that shows that a universal halt decider can't exist.

Thus, your proof doesn't actually show what you claim, because you are
using an incorrect criteria.

The ONLY valid criteria is will the computation represented by the input
Halt when run as an unfettered computation, and P (your name for H^)
makes sure that H doesn't give the right answer. Alternate criteria can
be used, but only if they exactly agree with the actual definition.
Since yours doesn't, you can't use it.

FAIL.
Reply all
Reply to author
Forward
0 new messages