Halting problem proofs refuted on the basis of software engineering V2

[olcott]

No one can provide any "rebuttal" of my paper on any other basis
than

(1) disagreeing with the semantics of the x86 language
*x86 Instruction Set Reference* https://c9x.me/x86/

*or disagreeing with this necessarily true principle*
(2) 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.



This much more concise version of my paper focuses on the actual
execution of three fully operational examples.

H0 correctly determines that Infinite_Loop() never halts
H correctly determines that Infinite_Recursion() never halts
H(P,P) correctly determines that its input never halts

typedef void (*ptr)();

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

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

As shown below the above P and H have the required (halting problem)
pathological relationship to each other:

For any program H that might determine if programs halt, a
"pathological"
program P, called with some input, can pass its own source and its
input to
H and then specifically do the opposite of what H predicts P will
do. No H
can exist that handles this case.
https://en.wikipedia.org/wiki/Halting_problem


*Halting problem proofs refuted on the basis of software engineering*
https://www.researchgate.net/publication/361701808_Halting_problem_proofs_refuted_on_the_basis_of_software_engineering


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

On 7/4/2022 10:58 AM, Mr Flibble wrote:

> On Mon, 4 Jul 2022 09:45:45 -0500
> olcott <No...@NoWhere.com> wrote:
>
>> No one can provide any "rebuttal" of my paper on any other basis
>> than
>>
>> (1) disagreeing with the semantics of the x86 language
>> *x86 Instruction Set Reference* https://c9x.me/x86/
>>
>> *or disagreeing with this necessarily true principle*
>> (2) 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.
>>
>>
>>
>> This much more concise version of my paper focuses on the actual
>> execution of three fully operational examples.
>>
>> H0 correctly determines that Infinite_Loop() never halts
>> H correctly determines that Infinite_Recursion() never halts
>> H(P,P) correctly determines that its input never halts
>

> As I have shown with my signaling halting decider there is no need for
> a call to a simulation-based halting decider, H, from the input program
> to be recursive; this is compatible with [Strachey 1965] and
> associated proofs which are not recursive in nature. Your H is invalid
> as it aborts the simulation to prevent infinite recursion rather than
> returning an answer to its caller which results in it giving the wrong
> answer for a non-pathological input that calls H.
>
> /Flibble
>

YOU KEEP DISAGREEING WITH VERIFIED FACTS:
From a purely software engineering perspective (anchored in the
semantics of the x86 language) it is proven that H(P,P) correctly
predicts that its correct and complete x86 emulation of its input would
never reach the "ret" instruction (final state) of this input.

[Mr Flibble]

No it doesn't. What you have doesn't work.

/Flibble

[olcott]

Try and prove how foolish you are by attempting to refute the above
statement on the basis is this paper:

*Halting problem proofs refuted on the basis of software engineering*
https://www.researchgate.net/publication/361701808_Halting_problem_proofs_refuted_on_the_basis_of_software_engineering

[Mr Flibble]

On Mon, 4 Jul 2022 12:33:44 -0500

I don't have to consider your "paper"; the evidence is here for all to
see:

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.

[olcott]

Your trace always deceitfully leaves out key details.

_Px()
[00001192](01) 55 push ebp
[00001193](02) 8bec mov ebp,esp
[00001195](03) 8b4508 mov eax,[ebp+08]
[00001198](01) 50 push eax
[00001199](03) 8b4d08 mov ecx,[ebp+08]
[0000119c](01) 51 push ecx
[0000119d](05) e8d0fdffff call 00000f72
[000011a2](03) 83c408 add esp,+08
[000011a5](01) 5d pop ebp
[000011a6](01) c3 ret
Size in bytes:(0021) [000011a6]

_main()
[000011d2](01) 55 push ebp
[000011d3](02) 8bec mov ebp,esp
[000011d5](05) 6892110000 push 00001192
[000011da](05) 6892110000 push 00001192
[000011df](05) e88efdffff call 00000f72
[000011e4](03) 83c408 add esp,+08
[000011e7](01) 50 push eax
[000011e8](05) 68a3040000 push 000004a3
[000011ed](05) e800f3ffff call 000004f2
[000011f2](03) 83c408 add esp,+08
[000011f5](02) 33c0 xor eax,eax
[000011f7](01) 5d pop ebp
[000011f8](01) c3 ret
Size in bytes:(0039) [000011f8]

machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
[000011d2][00101f7f][00000000] 55 push ebp
[000011d3][00101f7f][00000000] 8bec mov ebp,esp
[000011d5][00101f7b][00001192] 6892110000 push 00001192
[000011da][00101f77][00001192] 6892110000 push 00001192
[000011df][00101f73][000011e4] e88efdffff call 00000f72

H: Begin Simulation Execution Trace Stored at:11202b
Address_of_H:f72
[00001192][00112017][0011201b] 55 push ebp
[00001193][00112017][0011201b] 8bec mov ebp,esp
[00001195][00112017][0011201b] 8b4508 mov eax,[ebp+08]
[00001198][00112013][00001192] 50 push eax
[00001199][00112013][00001192] 8b4d08 mov ecx,[ebp+08]
[0000119c][0011200f][00001192] 51 push ecx
[0000119d][0011200b][000011a2] e8d0fdffff call 00000f72
H: Infinitely Recursive Simulation Detected Simulation Stopped

[000011e4][00101f7f][00000000] 83c408 add esp,+08
[000011e7][00101f7b][00000000] 50 push eax
[000011e8][00101f77][000004a3] 68a3040000 push 000004a3
[000011ed][00101f77][000004a3] e800f3ffff call 000004f2
Input_Halts = 0
[000011f2][00101f7f][00000000] 83c408 add esp,+08
[000011f5][00101f7f][00000000] 33c0 xor eax,eax
[000011f7][00101f83][00000018] 5d pop ebp
[000011f8][00101f87][00000000] c3 ret
Number of Instructions Executed(880) == 13 Pages

[Mr Flibble]

On Mon, 4 Jul 2022 12:51:24 -0500

My trace only includes the pertinent details: namely that it gets the
halting decision wrong:

> > Input_Halts = 0

/Flibble

[olcott]

You continue under the false assumption that a function called in
infinite recursion must return to its caller. That you continue in the
false assumption after multiple corrections is a little nuts.

[Mr Flibble]

On Mon, 4 Jul 2022 13:00:21 -0500

There is no infinite recursion in [Strachey 1965] or associated proofs
and I have shown that there need not be any recursion when using a
simulation-based halting decider; if you have to abort your simulation
to avoid infinite recursion then that just goes to show that your
solution is wrong.

/Flibble

[olcott]

Only because no one bothered to ever fully examine applying a simulating
halt decider to the halting theorem counter-examples prior to:

comp.theory: [Solution to one instance of the Halting Problem]

On 3/14/2017 9:05 AM, peteolcott wrote:

> and I have shown that there need not be any recursion when using a
> simulation-based halting decider;

You have not shown this. One is not free to diverge from the semantics
specified by the C/x86 source-code. If infinite recursion is specified
in this source-code then infinite recursion must occur in the execution
trace until it is aborted.

> if you have to abort your simulation
> to avoid infinite recursion then that just goes to show that your
> solution is wrong.

Actually it proves that my solution is correct. A simulating halt
decider must always abort its simulation of every non-halting input.

>
> /Flibble

[Mr Flibble]

On Mon, 4 Jul 2022 14:09:32 -0500

I have shown this: see my recent post "An idea for a simulating halt
decider" in this forum.

>
> > if you have to abort your simulation
> > to avoid infinite recursion then that just goes to show that your
> > solution is wrong.
>
> Actually it proves that my solution is correct. A simulating halt
> decider must always abort its simulation of every non-halting input.

No, it proves your solution is incorrect.

/Flibble

[Richard Damon]

Rigth, so YOUR answer is wrong, as your simulator doesn't actually
simulate all of its input, since it doesn't simulate the code at the
results of the call H instruction, but replaces it with something that
is actually DIFFERENT then the actual H routine.

You have said that H(P,P) return 0, so a correct emulation of a call to
H with parameters P and P, needs to return 0.

>
>> if you have to abort your simulation
>> to avoid infinite recursion then that just goes to show that your
>> solution is wrong.
>
> Actually it proves that my solution is correct. A simulating halt
> decider must always abort its simulation of every non-halting input.

Except that if H(P,P) aborts its simulation and returns 0, then the
input is Halting.

Note H(P,P) must refer to P(P) or your P isn't defined per the
specification.

>
>>
>> /Flibble
>>
>
>