Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Halting problem proofs refuted on the basis of software engineering
60 views
Skip to first unread message
olcott
Jul 2, 2022, 11:34:56 AM7/2/22
to
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
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
Jul 2, 2022, 12:26:53 PM7/2/22
to
{
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
Jul 2, 2022, 12:46:44 PM7/2/22
to
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));
}
[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
Mr Flibble
Jul 2, 2022, 1:11:46 PM7/2/22
to
halt; the infinite recursion is a manifestation of your invalid
simulation-based halting decider. There is no recursion in [Strachey
1965].
/Flibble
olcott
Jul 2, 2022, 1:35:08 PM7/2/22
to
decider even though I conclusively proved that it does correctly
determine the halt status of: (see my new paper)
H0 correctly determines that Infinite_Loop() never halts
H correctly determines that Infinite_Recursion() never halts
H correctly determines that P() never halts
Every simulating halt decider that correctly simulates its input until
it correctly determines that this simulated input would never reach its
final state, correctly rejects this input as non-halting.
*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
Richard Damon
Jul 2, 2022, 2:40:19 PM7/2/22
to
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
> 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
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
Jul 2, 2022, 7:08:27 PM7/2/22
to
On 7/2/2022 1:40 PM, Richard Damon wrote:
> 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.
>
The following execution trace proves that you are wrong on the basis of
> 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.
>
the semantics of the x86 language. Disagreeing with the x86 language is
just like disagreeing with arithmetic.
void Px(u32 x)
{
H(x, x);
}
int main()
{
olcott
Jul 9, 2022, 9:16:51 AM7/9/22
to
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]
> [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
input, therefore T(Strachey_P) correctly rejects this input as non-halting.
> 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
> machine stack stack machine assembly
> address address data code language
> ======== ======== ======== ========= =============
> [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
Jul 12, 2022, 12:34:29 PM7/12/22
to
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
> 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
Jul 12, 2022, 1:48:52 PM7/12/22
to
Richard Damon
Jul 12, 2022, 7:06:29 PM7/12/22
to
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
Jul 16, 2022, 1:44:16 PM7/16/22
to
On 7/16/2022 10: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*.
>
The simulation that H(P,P) performs on its input is *incomplete* in the
same way that the simulation of H0(Infinite_Loop) is incomplete.
If H0 waited until the heat death of the universe before it aborted its
simulation this simulation would still be *incomplete*
*H0 correctly determines that Infinite_Loop() never halts*
void Infinite_Loop()
{
HERE: goto HERE;
}
int main()
{
Output("Input_Halts = ", H0(Infinite_Loop));
}
_Infinite_Loop()
[00001102](01) 55 push ebp
[00001103](02) 8bec mov ebp,esp
[00001105](02) ebfe jmp 00001105
[00001107](01) 5d pop ebp
[00001108](01) c3 ret
Size in bytes:(0007) [00001108]
*H0: Begin Simulation Execution Trace Stored at:211fac*
[00001103][00211f9c][00211fa0] 8bec mov ebp,esp
[00001105][00211f9c][00211fa0] ebfe jmp 00001105
[00001105][00211f9c][00211fa0] ebfe jmp 00001105
*H0: Infinite Loop Detected Simulation Stopped*
> 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 study the H(P,P) code you would see that the correct
simulation that H(P,P) performs on its input could never reach the
"return" instruction of P before the heat death of the universe.
*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
>
> Mike.
>
>>
>>> If we accept that the behavior of the executed P(P) is the behavior that
>>> H must report on then we are saying that H must report on the behavior
>>> that is not the actual behavior of its actual input.
>>
>> No, the two things are the same.
> 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*.
>
The simulation that H(P,P) performs on its input is *incomplete* in the
same way that the simulation of H0(Infinite_Loop) is incomplete.
If H0 waited until the heat death of the universe before it aborted its
simulation this simulation would still be *incomplete*
*H0 correctly determines that Infinite_Loop() never halts*
void Infinite_Loop()
{
HERE: goto HERE;
}
int main()
{
Output("Input_Halts = ", H0(Infinite_Loop));
}
_Infinite_Loop()
[00001102](01) 55 push ebp
[00001103](02) 8bec mov ebp,esp
[00001105](02) ebfe jmp 00001105
[00001107](01) 5d pop ebp
[00001108](01) c3 ret
Size in bytes:(0007) [00001108]
*H0: Begin Simulation Execution Trace Stored at:211fac*
machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
[00001102][00211f9c][00211fa0] 55 push ebp
address address data code language
======== ======== ======== ========= =============
[00001103][00211f9c][00211fa0] 8bec mov ebp,esp
[00001105][00211f9c][00211fa0] ebfe jmp 00001105
[00001105][00211f9c][00211fa0] ebfe jmp 00001105
*H0: Infinite Loop Detected Simulation Stopped*
> 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 study the H(P,P) code you would see that the correct
simulation that H(P,P) performs on its input could never reach the
"return" instruction of P before the heat death of the universe.
*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
>
>
>>
>>> If we accept that the behavior of the executed P(P) is the behavior that
>>> H must report on then we are saying that H must report on the behavior
>>> that is not the actual behavior of its actual input.
>>
>> No, the two things are the same.
Richard Damon
Jul 16, 2022, 1:56:41 PM7/16/22
to
simulator, Simulate(P,P) will halt, while Simulate(Infinite_Loop, 0)
will not.
The problems isn't per-se that H has an incomplete simulation, but that
it bases its answer on unsound rules that makes it THINK that a complete
simulation of the input (with THIS H in it) would never end.
You H is answer the wrong question, one based on a fantasy. It is
answering, If this Halt Decider wasn't a Halt Decider but an pure
simulator, (and any reference to it in the input program refered to that
version) would the input halt.
That ISN'T the question for a Halt Decider. The question is does the
input AS IT IS, Halt or not. Since H DOES abort its simulation of its
input for H(P,P) then the simulation of the input must consider that
behavior, or it isn't simulating the input correctly.
simulation when called by P, it won't when called by main, so it will
fail to answer.
You problem is it seems you don't actually have *A* H that you are
looking at but keep on playing shell games.
That is one reason you can't publish your code, if you do you need to
actually define which one you are talking about.
The H that doesn't abort and creates a non-halting P(P) but is wrong
because it fails to answer, or
The H that DOES abort and createas a HALTING P(P) that it thinks in
non-halting because it uses bad logic/incorrect simulation to decide and
gives the wrong answer.
olcott
Jul 16, 2022, 4:12:20 PM7/16/22
to
On 7/16/2022 2:28 PM, Mike Terry wrote:
> On 16/07/2022 17:40, Richard Damon wrote:
>> 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)
}
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
> On 16/07/2022 17:40, Richard Damon wrote:
>>> 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
>>> H(P,P)" differ - H simply stops simulating before P(P) terminates.
>>
>> 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));
return;
}
int main()
{
}
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
Jul 16, 2022, 9:24:15 PM7/16/22
to
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.
>> *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.
> On 7/16/22 8:18 PM, olcott wrote:
>>
>>> 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*
>>> 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.
>>
>> *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
Jul 16, 2022, 9:49:38 PM7/16/22
to
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
Jul 16, 2022, 10:09:16 PM7/16/22
to
actual underlying computation then the concept of a UTM fails to remain
coherent.
Richard Damon
Jul 16, 2022, 10:17:20 PM7/16/22
to
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
Jul 16, 2022, 10:39:05 PM7/16/22
to
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.
0 new messages