Halting problem proofs refuted on the basis of software engineering

[olcott]

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 correctly determines that P() never halts

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

int main()
{
Output("Input_Halts = ", H((u32)P, (u32)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

I really need software engineers to verify that H does correctly predict
that its complete and correct x86 emulation of its input would never
reach the "ret" instruction of this input.

*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

[Mr Flibble]

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]

Your false assumptions are directly contradicted by the semantics of the
x86 programming language.

*x86 Instruction Set Reference* https://c9x.me/x86/

void Px(u32 x)
{
H(x, x);
return;
}

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

_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 // push Px
[00001199][00112013][00001192] 8b4d08 mov ecx,[ebp+08]
[0000119c][0011200f][00001192] 51 push ecx // push Px
[0000119d][0011200b][000011a2] e8d0fdffff call 00000f72 // call H(Px,Px)
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 Px (see above) to determine:
(a) Px is calling H with the same arguments that H was called with.
(b) No instructions in Px could possibly escape this otherwise
infinitely recursive emulation.
(c) H aborts its emulation of Px before its call to H is emulated.

[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

[Richard Damon]

On 7/2/22 11:34 AM, olcott wrote:
> 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 correctly determines that P() never halts

Except that if H(P,P) actually returns 0, then P(P) will halt, so H is
wrong.

You can't just define the wrong answer to be right. And, your dishonest
dodge that H(P,P) doesn't actually refer to P(P) says that P isn't the
program you claim, as the P is DEFINED to ask H about ITSELF with its
input, so if H(P,P) doesn't mean that, then you have defined something
wrong.

The problem is your logic doesn't actually correctly consider the
behavior of the H being called, so doesn't actually do a correct x86
emulation of its input.

[olcott]

On 7/8/2022 5:48 PM, olcott wrote:
> On 7/8/2022 1:09 AM, dklei...@gmail.com wrote:
>> On Thursday, July 7, 2022 at 9:48:17 PM UTC-7, olcott wrote:
>>> On 7/7/2022 11:35 PM, dklei...@gmail.com wrote:
>>>
>>>> int Strachey_P(void) {
>>>> if (T(&Strachey_P)) return 1;
>>>> else return 0; }
>>>>
>>>> int main() {
>>>> if (T(&Strachey_P)) Output("Halts");
>>>> else Output ("Does not halt");}
>>>>
>>>> Without the definition of T this is just boiler plate.
>>>
>>> Yours is incorrect:
>>
>> How? I assume C89.
>
> typedef void (*ptr)();
>
> int Strachey_P2(void) {
> if (T(&Strachey_P2)) return 1;
> else return 0; }
>
> int main()
> {
>  if (T(Strachey_P2)) OutputString("Halts\n");
>  else OutputString("Does not halt\n");
> }
>
> _Strachey_P2()
> [0000134e](01)  55         push ebp
> [0000134f](02)  8bec       mov ebp,esp
> [00001351](05)  684e130000 push 0000134e
> [00001356](05)  e893fbffff call 00000eee
> [0000135b](03)  83c404     add esp,+04
> [0000135e](02)  85c0       test eax,eax
> [00001360](02)  7409       jz 0000136b
> [00001362](05)  b801000000 mov eax,00000001
> [00001367](02)  eb04       jmp 0000136d
> [00001369](02)  eb02       jmp 0000136d
> [0000136b](02)  33c0       xor eax,eax
> [0000136d](01)  5d         pop ebp
> [0000136e](01)  c3         ret
> Size in bytes:(0033) [0000136e]
>
> _main()
> [0000137e](01)  55         push ebp
> [0000137f](02)  8bec       mov ebp,esp
> [00001381](05)  684e130000 push 0000134e
> [00001386](05)  e863fbffff call 00000eee
> [0000138b](03)  83c404     add esp,+04
> [0000138e](02)  85c0       test eax,eax
> [00001390](02)  740f       jz 000013a1
> [00001392](05)  6817050000 push 00000517
> [00001397](05)  e8c2f1ffff call 0000055e
> [0000139c](03)  83c404     add esp,+04
> [0000139f](02)  eb0d       jmp 000013ae
> [000013a1](05)  681f050000 push 0000051f
> [000013a6](05)  e8b3f1ffff call 0000055e
> [000013ab](03)  83c404     add esp,+04
> [000013ae](02)  33c0       xor eax,eax
> [000013b0](01)  5d         pop ebp
> [000013b1](01)  c3         ret
> Size in bytes:(0052) [000013b1]

>
>  machine   stack     stack     machine    assembly
>  address   address   data      code       language
>  ========  ========  ========  =========  =============

> [0000137e][001022be][00000000] 55         push ebp
> [0000137f][001022be][00000000] 8bec       mov ebp,esp
> [00001381][001022ba][0000134e] 684e130000 push 0000134e
> [00001386][001022b6][0000138b] e863fbffff call 00000eee
>
> T: Begin Simulation   Execution Trace Stored at:11236a
> Address_of_T:eee
> [0000134e][0011235a][0011235e] 55         push ebp
> [0000134f][0011235a][0011235e] 8bec       mov ebp,esp
> [00001351][00112356][0000134e] 684e130000 push 0000134e
> [00001356][00112352][0000135b] e893fbffff call 00000eee
> T: Infinitely Recursive Simulation Detected Simulation Stopped
>
> [0000138b][001022be][00000000] 83c404     add esp,+04
> [0000138e][001022be][00000000] 85c0       test eax,eax
> [00001390][001022be][00000000] 740f       jz 000013a1
> [000013a1][001022ba][0000051f] 681f050000 push 0000051f
> [000013a6][001022ba][0000051f] e8b3f1ffff call 0000055e
> Does not halt
> [000013ab][001022be][00000000] 83c404     add esp,+04
> [000013ae][001022be][00000000] 33c0       xor eax,eax
> [000013b0][001022c2][00000018] 5d         pop ebp
> [000013b1][001022c6][00000000] c3         ret
> Number of Instructions Executed(539) == 8 Pages
>

*THIS IS IRREFUTABLY CORRECT*
From a purely software engineering perspective T(Strachey_P) does

correctly predict that its complete and correct x86 emulation of its

input would never reach the "ret" instruction (final state) of this
input, therefore T(Strachey_P) correctly rejects this input as non-halting.

[olcott]

Richard Damon <Ric...@Damon-Family.org> Wrote in message:r
> On 7/2/22 11:34 AM, olcott wrote:> 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 correctly determines that P() never haltsExcept that if H(P,P) actually returns 0, then P(P) will halt, so H is wrong.You can't just define the wrong answer to be right. And, your dishonest dodge that H(P,P) doesn't actually refer to P(P) says that P isn't the program you claim, as the P is DEFINED to ask H about ITSELF with its input, so if H(P,P) doesn't mean that, then you have defined something wrong.The problem is your logic doesn't actually correctly consider the behavior of the H being called, so doesn't actually do a correct x86 emulation of its input.> > void P(u32 x)> {> if (H(x, x))> HERE: goto HERE;> return;> }> > int main()> {> Output("Input_Halts = ", H((u32)P, (u32)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> > I really need software engineers to verify that H does correctly predict > that its complete and correct x86 emulation of its input would never > reach the "ret" instruction of this input.> > *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 > >

You are simply not bright enough to understand that every function
called (what is essentially) infinite never returns any value to
it's caller.

--


----Android NewsGroup Reader----
https://piaohong.s3-us-west-2.amazonaws.com/usenet/index.html

[Bonita Montero]

Come back when you've got sth. that's really related to C or C++.

[Richard Damon]

And you seem to think that what at first seems to be infinite recursion,
might not be because H is "smart" enough to abort its simulation, but
not smart enough to understand that the H that P/D calls will too.

Since one copy of H does this, all copies will, or H isn't a
computation/pure function.

Tht, or H is just plain incorrect about what its input does, because it
uses incorrect logic about what copies of it does (since in never
actually sees what those copies will do).

[olcott]

On 7/16/2022 2:28 PM, Mike Terry wrote:
> On 16/07/2022 17:40, Richard Damon wrote:
>> On 7/16/22 11:54 AM, Mike Terry wrote:
>>> On 16/07/2022 12:23, Paul N wrote:
>>>> On Friday, July 15, 2022 at 5:26:49 PM UTC+1, olcott wrote:
>>>>> On 7/15/2022 11:17 AM, Paul N wrote:
>>>>>> On Friday, July 15, 2022 at 3:35:47 PM UTC+1, olcott wrote:
>>>>>>> On 7/15/2022 7:34 AM, Paul N wrote:
>>>>>>>> Do you accept that if H were required to report on the behaviour
>>>>>>>> of the direct execution of P(P) then it would not be possible to
>>>>>>>> write such an H?
>>>>>>> That would require H to be a mind reader and report on something
>>>>>>> other
>>>>>>> than the actual behavior of its actual input.
>>>>>>
>>>>>> There's no mind involved. If P is a computer program then P(P) is
>>>>>> perfectly well defined. Either H can work out what it will do, or
>>>>>> it can't.
>>>>
>>>> You haven't said in what way a "mind" is involved in the direct
>>>> execution of P(P).
>>>>
>>>>> It is like you ask your wife to go to the store and buy "a dozen eggs"
>>>>> fully expecting her to understand that what you mean by "a dozen eggs"
>>>>> is {a half gallon of grape juice}. When she gets back with the eggs
>>>>> you
>>>>> ask her where is the grape juice?
>>>>
>>>> No, you are the one who is twisting the meaning of words. When I
>>>> talk about the actual behaviour of P(P) I mean what actually happens
>>>> when P(P) is executed. That's what the words "actual" and
>>>> "behaviour" mean.
>>>>
>>>> You are using the words "actual behavior" to mean something else
>>>> which is clearly different. It seems to relate to some sort of
>>>> simulator, which you simultaneously claim to be correct while
>>>> acknowledging it produces different results from executing P(P)
>>>> directly.
>>>>
>>>> Can you tell us if that "actual behavior" does actually happen in
>>>> any circumstances, or is it (despite the name) just a theoretical
>>>> thing?
>>>>
>>>>> 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.
>>>>
>>>> Yes, where the actual behaviour is the behaviour that actually happens.
>>>>
>>>>> It is common knowledge that a correct simulation of a program is a
>>>>> correct measure of the behavior of this program.
>>>>
>>>> Yes, if the simulation is correct. You've insisted numerous times
>>>> that your own simulator is incorrect.
>>>
>>> PO's simulation is correct at the individual instruction level.  His
>>> H steps the simulation forward a number of steps, and each of those
>>> steps exactly matches the P(P) calculation steps.  At some point
>>> before the final P RET instruction, his H decides to stop stepping
>>> (for whatever reason), so H's simulation is *incomplete*.
>>>
>>> That is the only sense in which P(P) and "the simulated input to
>>> H(P,P)" differ - H simply stops simulating before P(P) terminates.
>>
>> But "incomplete" is incorrect if your logic assumes that the
>> simulation not reaching the final state PROVES non-halting.
>
> I don't believe PO thinks that, irrespective of how badly he explains
> things.  I think he believes that the simulation would never halt
> *because his never-halting-abort test matched*, NOT simply as a
> consequence of aborting.  E.g. he seems to understand that a simulator
> that steps 10 steps then stops regardless, does not imply that the
> simulated computation does not halt.
>
> Although... he doesn't properly understand what halting means, and gets
> hopelessly confused by various wordings, so discussing any of this with
> him is quite futile.  Seriously - just don't bother!!
>
>> "Simulation" as a word by itself implies complete and correct, and
>> "Correct Simulation" implies Complete in normal English usage.
>
> That's an opinion, and it's one way to go.  To me "simulating" is an
> /activity/ that H performs - it means calcultating succesive steps of a
> given computation.  (Without implied /completeness/.)
>>
>> Yes, to be very precise we could everywhere say complete and correct
>> simulation, but that gets wordy.
>
> No need - everywhere in these threads where "H simulates..." is used,
> the meaning is nearly always my interpretation, not yours.  I don't
> agree yours is the default/correct interpretation - at least it's not
> the useful one.  In the event that you want to refer to a complete
> simulation, you can just say "full simulation" or "complete simulation",
> but that IMO hardly ever arises.  (Or we could make the most common
> scenario more wordy, by always emphasising "partial simulation".)
> Anyway, this seems to be a non-issue...
>
>>
>> The key point is that H stops its simulating, AND THEN PRESUMES that
>> this simulation, if continued correctly, would never halt.
>
> Yes, all the regulars here understand this mistake, if not it's origin.
> BUT THERE IS NO POINT TRYING TO EXPLAIN THE PROBLEM TO PO - HE IS
> INTELLECTUALLY INCAPABLE OF FOLLOWING ABSTRACT REASONING OR
> UNDERSTANDING THE REQUIRED CONCEPTS.  Surely you must have come to this
> conclusion after all this time?
>

A computation is said to terminate normally when it completes all of its
steps by reaching its last instruction. It is shown below that P
essentially calls H in infinite recursion and is rejected by H as
non-halting on that basis.

*Mike doesn't seem to comprehend this*
*Mike doesn't seem to comprehend this*
*Mike doesn't seem to comprehend this*
*Mike doesn't seem to comprehend this*

typedef void (*ptr)();
int H(ptr p, ptr i); // simulating halt decider

void P(ptr x)
{
int Halt_Status = H(x, x);
if (Halt_Status)

HERE: goto HERE;
return;
}

int main()
{

Output("Input_Halts = ", H(P, P));
}

When simulating halt decider H(P,P) simulates its input it can see that:
(1) Function H() is called from P().
(2) With the same arguments to H().
(3) With no instructions in P preceding its invocation of H(P,P) that
could escape repeated simulations.

The above shows that the simulated P cannot possibly (reachs it “return”
instruction and) terminate normally. H(P,P) simulates its input then P
calls H(P,P) to simulate itself again. When H sees that this otherwise
infinitely nested simulation would never end it aborts its simulation of
P and rejects P as non-halting.

Halting problem proofs refuted on the basis of software engineering

[olcott]

On 7/16/2022 7:38 PM, Richard Damon wrote:
> On 7/16/22 8:18 PM, olcott wrote:

>> This review was very helpful thanks.

>>
>>> That is the only sense in which P(P) and "the simulated input to
>>> H(P,P)" differ - H simply stops simulating before P(P) terminates.
>>

>> *If you carefully examine this you will see that the simulated P cannot*
>> *possibly ever terminate normally by reaching its "return" instruction*
>
>
> Which just doesn't matter as Halting is defined based on the actual
> machine and not a simulation.
>

Then the whole idea of a UTM would be totally bogus.

[Richard Damon]

Why? Just because Halting is defined by the actual machine, why does
that make a UTM bogus?

Note, since a UTM, BY DEFINITION, generates the equivalent output as the
machine it is simuating, you can use valid logic between them, so if
UTM(M,x) Halts, then you can use the definition of a UTM to say that
this means that M(x) will halt too.

That doesn't change the fact that Halting is DEFINED by the machine, it
just says you don't base things on what the UTM said, you base it on
what the UTM proves the machine will say.

Big Note, that equivalence ONLY holds for something that IS a UTM, and
not something based on a UTM that might chose to stop it processing,
then you need to find logic rules that deal with that case.

This is why halting isn't based on the results of the simulaiton by the
Halting decider, since BY DEFINITION, a halting decider must answer in
finite time, a simulation by a Halt Decider can NEVER, by itself, prove
non-halting. It might provide evidence based on valid rules to let you
prove non-halting, but that deduction will be able to be tested by
running the actual machine (or simulation by an actual UTM which by
definition gives the same answer).

There is no wouldn't halt unless the halt decider aborted, as since the
halt decider WILL abort in that case, there never was the case that the
halt decider didn't abort, since that isn't the machine we are looking at.

[olcott]

If the correct simulation of a machine description does not specify the
actual underlying computation then the concept of a UTM fails to remain
coherent.

[Richard Damon]

The issue is what you have been running into, defining what "correct
simulation" means. The definition of Halting says it is the behavior of
the actual machine that matters, and "correct simulation" means that
simulation matched that behavior, so can be also used.

This is your fundamental problem, you keep on trying to claim that the
input to H(P,P) doesn't actually match the machine it is supposed to be
the description of, all that means is that your simulation isn't correct.

By making the DEFINITION the actual machine, games like that become
impossible, as the machine IS the machine.

Remeber: By design P(P) WILL Halt if H(P,P) rejects, therefore since the
definition of a correct halt decider is that H is will accept halting
inputs, H gave the wrong answer and is not a correct halt decider.

That is just simple DEFINITIONS.

We don't need to worry if your rules that you try to use to prove that H
is corrct are right or not, the defined test is run the machine.

Since P(P) halts when H(P,P) returns 0, H was just wrong.

[olcott]

Mike already correctly addressed this in his reply to Paul N:

On 7/16/2022 10:54 AM, Mike Terry wrote:
> On 16/07/2022 12:23, Paul N wrote:
> PO's simulation is correct at the individual instruction level.
> His H steps the simulation forward a number of steps, and each
> of those steps exactly matches the P(P) calculation steps.