Proving that H(P,P) is a correct P never reaches "ret" determiner (AKA P never halts)

2 views
Skip to first unread message

olcott

unread,
Jun 23, 2022, 9:48:26 PMJun 23
to
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.

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 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


--
Copyright 2022 Pete Olcott

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

Richard Damon

unread,
Jun 23, 2022, 10:07:13 PMJun 23
to

On 6/23/22 9:48 PM, olcott wrote:
> 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.
>

Actually, no knowledge of the halting problem is ALLOWED, since it is
based on INCORRECT definitions.

> 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.

Yes, *IF* H does a complete and correct x86 emulation of its input, then
this will never reach the return instruction. Note, condition.

>
> In computer science terminology this means that complete and correct
> emulation P by H would never reach its final state and halt.

Right, FOR AN H that meets the above requirement.
But by (c) H negates all of the previous information.

Note, your (b) also break if H is allowed to have conditionality in its
emulation.

>
> [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
>
>

Proves nothing, since you haven't actually shown that anything is
actually non-halting.

by your (c), your (b) is no longer proof of non-halting, as the PROGRAM
P includes the code in H which has the needed conditional in the loop if
you look at the actual rule you are thinking of.

If you wish to provide a reference to some accepted source that accepts
your (b) as you are using it, please do, otherwise, since this has been
pointed out numerous times before, it is just proof that you are totally
ignorant of the field and how to do actual logic.

Halting is defined for PROGRAMS or COMPUTATIONS, which include ALL the
code that is executed as part of that operation, thus for P includes H.

YOU FAIL.

Mr Flibble

unread,
Jun 24, 2022, 5:34:25 PMJun 24
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)

As can be seen above Olcott's H decides that Px does not halt but it is
obvious that Px should always halt if H is a valid halt decider that
always returns a decision to its caller (Px). Olcott's H does not
return a decision to its caller (Px) and is thus invalid.

/Flibble


olcott

unread,
Jun 24, 2022, 5:53:39 PMJun 24
to
You keep confusing an abnormal termination when the emulated input to
H(P,P) has been aborted with the normal halting termination of the
emulated input reaching the its "ret" instruction (AKA final state).

When I blocked Richard it erased everything that he said in my copy of
his posts in Thunderbird. If I have to keep correcting you I will block
you too.

*The key requirement to avoid getting blocked is to prove that*
*you want an honest dialogue and are not just playing head games*

Richard Damon

unread,
Jun 24, 2022, 9:51:04 PMJun 24
to
THen you better change how you treat others, because YOU are the one not
looking for "Honest Dialog".

And if you have blocked me, then you have just made it so that the world
will see my rebutalls without you even making your worthless retorts
about them.

It isn't that the emulation of the input H(P,P) "halts" because it was
aborted, but because the ACURRATE, and COMPLETE emulation of the input
will reach the ret instruction. The ONLY reason H didn't get there, was
because it aborted its simulation before it got there.

Yes, it HAD to abort there, because that is how it is programmed, but if
we do an ACTUAL complete and correct emulation of that input, we see it
Halts.

Mr Flibble

unread,
Jun 25, 2022, 10:55:53 AMJun 25
to
You don't keep correcting me as I am not incorrect; I do keep
correcting you however:

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)

As can be seen above Olcott's H decides that Px does not halt but it is
obvious that Px should always halt if H is a valid halt decider that
always returns a decision to its caller (Px). Olcott's H does not
return a decision to its caller (Px) and is thus invalid.

I have told you before: I don't give a fuck if you block me or not as
it will not stop me reposting the above whenever you repeat your
same old bullshit.

/Flibble



olcott

unread,
Jun 25, 2022, 11:15:01 AMJun 25
to
Unless and until you expressly acknowledge that the correct and complete
x86 emulation of the input to H(Px,Px) by H would never reach the "ret"
instruction of Px you will remain dismissed as lacking the required
prerequisite knowledge:

To fully understand this paper a software engineer must be an expert in:
(a) The C programming language.
(b) The x86 programming language.
(c) Exactly how C translates into x86 (how C function calls are
implemented in x86).
(d) The ability to recognize infinite recursion at the x86 assembly
language level.

If you paraphrase the first paragraph and use this paraphrase as the
basis of your "rebuttal" you will be dismissed for attempting to get
away for the strawman deception.

straw man
An intentionally misrepresented proposition that is set up because it is
easier to defeat than an opponent's real argument.
https://www.lexico.com/en/definition/straw_man

I will continue to glance at what you say to verify that you have
switched to an honest dialogue.

Richard Damon

unread,
Jun 25, 2022, 1:30:53 PMJun 25
to
Except that your first paragraph IS a straw man in and of itself.

Since the H that returns 0 didn't (and CAN'T) do a correct and complete
x86 emulation of its input, the statement is just an imposssible fantasy.

No H can exist that meets your definition, so it doesn't provide a
counter example to the Halting Problem.

In fact, based on YOUR definition, no H can ever validly return 0 for
what is a non-halting computation, because theere is no complete and
correct emulation done by H of that input to validate the results with.

Your argument seems to be based on there being TWO DIFFERENT H's in
view, one that does a complete and corrects emulation and one that does
the deciding, but that makes P incorrect, as P needs to call the one
that does the deciding, since that is the one that is deciding on P.

Simple arguement, let us add a parameter to H to say which on it is, so
H(M,x,f) is define that if f == 0, then H(M,x,0) will do a complete and
correct emulation of its input, and for f == 1, then H(M,x,1) will
return 1 if H(M,x,0) will return in finite time, or 0 if H(M,x,0) will
never return.

Thus, P(x) needs to be designed as:

void P(u32 x) {
if(H(x,x,1)) {
Here: goto Here;
}
}

The issue is your analysis is based on looking at H(x,x,1) as if it was
actually P(x,x,0) which isn't what the code in P actually is.

In fact, NO "user" code will ever call H with an f of 0, and actually H
can't either (or get caught in an infinite loop) so H doesn't actually
need the parameter, and just define like currently being done that
H(M,x) is the DECIDER version, and we have a seperate function S(P,x)
that does the pure complete and correct emulation.

Now, we KNOW that if H(P,P) return 0, that S(P,P) will see P call H(P,P)
which will return 0 (unless H isn't actually the required and claimed
pure function) and thus return, so H(P,P) returns 0, is is incorrect as
S(P,P) halts.

The point here is that S is NOT H, even though it is what your initial
statement (incorrectly) assumed H to be. if S IS H, then H can't abort
and return 0 and still be a pure function.
Reply all
Reply to author
Forward
0 new messages