Software engineers of extremely high technical competence [ halting problem proof refutation ]

4 views
Skip to first unread message

olcott

unread,
Jun 20, 2022, 8:12:54 PMJun 20
to
#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]

Every sufficiently competent software engineer can easily verify that
the complete and correct x86 emulation of the input to H(P,P) by H would
never reach the "ret" instruction of P.




Software engineers with extremely high technical competence will be able
to verify that H correctly determines (in a finite number of steps) that
its complete and correct x86 emulation of its input would never reach
the "ret" instruction of P on this basis:

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 at its machine address [0000135d].

(b) There are no instructions in P that could possibly escape this
otherwise infinitely recursive emulation.

(c) H aborts its emulation of P before its call to H is invoked.

H does do this in fully operational code that is executed in the fully
operational x86utm operating system that is based on an very robust x86
emulator having decades of development effort.


--
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 20, 2022, 8:53:22 PMJun 20
to
Except that an H that does report that doesn't do a complete and correct
x86 emulation of its input.

>
> Software engineers with extremely high technical competence will be able
> to verify that H correctly determines (in a finite number of steps) that
> its complete and correct x86 emulation of its input would never reach
> the "ret" instruction of P on this basis:

How? Since the resutl s WRONG and IMPOSSIBLE.

IF H(P,P) returns 0, as you later claim, then it is clear that P(P) will
call that H(P,P) and get the 0 return value and return, thus making the
non-halting answer incorrect.

>
> 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 at its machine address [0000135d].
>
> (b) There are no instructions in P that could possibly escape this
> otherwise infinitely recursive emulation.
>
> (c) H aborts its emulation of P before its call to H is invoked.

So, since H will abort its emulation, that stops the infinite loop.

You have yet to show who we need to blaim for this incorrect rule
besides you.


>
> H does do this in fully operational code that is executed in the fully
> operational x86utm operating system that is based on an very robust x86
> emulator having decades of development effort.
>
>

Just because you started with an accurate emulator, by adding code that
stops it, H no long actually is a complete and correct emulation, so
presuming it is, just creates unsound logic.

Yes, if H just does a pure emulation of its input, the P(P) will never
halt, but that H fails to decide so is incorrecct.

YOU are the one with a mental problem to think that ONE algorthm can
generate TWO DIFFERENT results when applied to the same input.

That just shows that you logic has created an inconsistent system, and
thus FALSE to provide Truth.

olcott

unread,
Jun 20, 2022, 9:00:18 PMJun 20
to
On 6/20/2022 7:48 PM, wij wrote:
> Excuse again? Assertion about H without H defined?
>

Software engineers of extremely high technical competence will
understand that I did sufficiently define H above. I did this so
succinctly that this definition is way too terse for most people.

> From the HP proof: A (correct) halting decider cannot exist.
> No matter how he tried, olcott repeatedly shows he cannot provide a real
> halting decider except a verbal (or fake) one, if any.

Richard Damon

unread,
Jun 20, 2022, 9:17:27 PMJun 20
to
But it is defined in a contradictory manner. H is defined to BOTH do a
complete and correct emulation of its input, but also stop that
emulation and return 0 when it sees that the input won't stop.

The problem is that for inputs like P, you can't do both, not even
close. Some inputs you can actually PROVE that they won't stop with
valid and sound logic. The problem with doing this with H, is that due
to the depence of P on H, when ever H presumes that it has has proven
that P won't halt, P is one step ahead of it, and will stop a bit later.

So, H is NOT defined in a consistent manner, it presumes, INCORRECTLY,
that the H in P will not abort its simulation, when it will, and thus it
gets the wrong answer.

H did NEITHER a complete or a correct emulation, as it imputes the wrong
behavior into the copy of H it sees in P. Maybe the 7 instructions of P
it emulated corrretly, but then fell flat when it didn't emulate H but
replaced it in its logic with a DIFFERENT computation, and thus failed
to be correct.

olcott

unread,
Jun 21, 2022, 8:41:09 AMJun 21
to
On 6/20/2022 7:48 PM, wij wrote:
> On Tuesday, 21 June 2022 at 08:12:54 UTC+8, olcott wrote:
> Excuse again? Assertion about H without H defined?
>

#define JMP 0xEB // Simplifed OpCode for all forms of JMP
#define CALL 0xE8 // Simplifed OpCode for all forms of CALL
#define JCC 0x7F // Simplifed OpCode for all forms of Jump on Condition
#define RET 0xC3 // Simplifed OpCode for all forms of Return
#define PUSH 0x68 // Simplifed OpCode for all forms of PUSH

typedef struct Decoded
{
u32 Address;
u32 ESP; // Current value of ESP
u32 TOS; // Current value of Top of Stack
u32 NumBytes;
u32 Simplified_Opcode;
u32 Decode_Target;
} Decoded_Line_Of_Code;

Software engineers with extremely high technical competence will be able
to verify that H correctly determines (in a finite number of steps) that
its complete and correct x86 emulation of its input would never reach
the "ret" instruction of P on this criterion measure basis:

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 at its machine address [0000135d].

(b) There are no instructions in P that could possibly escape this
otherwise infinitely recursive emulation.

(c) H aborts its emulation of P before its call to H is invoked.

Software engineers with extremely high technical competence could
translate the above criterion measure into working code on the basis of
an execution_trace list of Decoded_Line_Of_Code of the x86 emulated
first seven instructions of P.

> From the HP proof: A (correct) halting decider cannot exist.
> No matter how he tried, olcott repeatedly shows he cannot provide a real
> halting decider except a verbal (or fake) one, if any.


Mr Flibble

unread,
Jun 21, 2022, 12:24:41 PMJun 21
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


Mr Flibble

unread,
Jun 21, 2022, 12:26:39 PMJun 21
to
void Px(u32 x)
{
H(x, x);
return;
}

int main()
{
Reply all
Reply to author
Forward
0 new messages