Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.software-eng > #3501
| Date | 2022-07-02 13:41 -0500 |
|---|---|
| Subject | Re: Halting problem proofs refuted on the basis of software engineering |
| Newsgroups | comp.theory, sci.logic, sci.math, comp.software-eng |
| References | (3 earlier) <20220702181010.000011c0@reddwarf.jmc> <S8idnfNU_avS4F3_nZ2dnUU7_8zNnZ2d@giganews.com> <20220702182653.00003f52@reddwarf.jmc> <r_qdndMhfIEBHV3_nZ2dnUU7_8xh4p2d@giganews.com> <20220702192847.00000807@reddwarf.jmc> |
| From | olcott <NoOne@NoWhere.com> |
| Message-ID | <3O2dnX_5sOHXDF3_nZ2dnUU7_81g4p2d@giganews.com> (permalink) |
Cross-posted to 4 groups.
On 7/2/2022 1:28 PM, Mr Flibble wrote:
> On Sat, 2 Jul 2022 12:30:03 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> On 7/2/2022 12:26 PM, Mr Flibble wrote:
>>> On Sat, 2 Jul 2022 12:15:58 -0500
>>> olcott <NoOne@NoWhere.com> wrote:
>>>
>>>> On 7/2/2022 12:10 PM, Mr Flibble wrote:
>>>>> On Sat, 2 Jul 2022 11:42:48 -0500
>>>>> olcott <NoOne@NoWhere.com> wrote:
>>>>>
>>>>>> On 7/2/2022 11:26 AM, Mr Flibble wrote:
>>>>>>> On Sat, 2 Jul 2022 10:34:34 -0500
>>>>>>> olcott <NoOne@NoWhere.com> 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
>>>>>>>>
>>>>>>>> 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
>>>>>>>>
>>>>>>>
>>>>>>> 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
>>>>>>>
>>>>>>
>>>>>> 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
>>>>>
>>>>> If H wasn't a simulation-based halting decider then Px() would
>>>>> always halt; the infinite recursion is a manifestation of your
>>>>> invalid simulation-based halting decider. There is no recursion
>>>>> in [Strachey 1965].
>>>>>
>>>>> /Flibble
>>>>
>>>> In other words you are rejecting the concept of a simulating halt
>>>> decider even though I conclusively proved that it does correctly
>>>> determine the halt status of: (see my new paper)
>>>
>>> No I am rejecting your simulating halt decider as it gets the answer
>>> wrong for Px() which is not a pathological input. Px() halts.
>>>
>>> /Flibble
>>>
>>
>> I just proved that H(Px,Px) does correctly predict that its complete
>> and correct x86 emulation of its input would never reach the "ret"
>> instruction of this input because of the pathological relationship
>> between H and Px.
>
> Wrong. Px() is not a pathological input as defined by the halting
> problem and [Strachey 1965] as it does not try to do the opposite of
> what H decides.
>
> /Flibble
>
Your lack of comprehension does not actually count as any rebuttal at all.
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
--
Copyright 2022 Pete Olcott
"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer
Back to comp.software-eng | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Halting problem proofs refuted on the basis of software engineering olcott <NoOne@NoWhere.com> - 2022-07-02 10:34 -0500
Re: Halting problem proofs refuted on the basis of software engineering Mr Flibble <flibble@reddwarf.jmc> - 2022-07-02 17:26 +0100
Re: Halting problem proofs refuted on the basis of software engineering olcott <NoOne@NoWhere.com> - 2022-07-02 11:42 -0500
Re: Halting problem proofs refuted on the basis of software engineering olcott <NoOne@NoWhere.com> - 2022-07-02 12:15 -0500
Re: Halting problem proofs refuted on the basis of software engineering Mr Flibble <flibble@reddwarf.jmc> - 2022-07-02 18:26 +0100
Re: Halting problem proofs refuted on the basis of software engineering olcott <NoOne@NoWhere.com> - 2022-07-02 12:30 -0500
Re: Halting problem proofs refuted on the basis of software engineering Mr Flibble <flibble@reddwarf.jmc> - 2022-07-02 19:28 +0100
Re: Halting problem proofs refuted on the basis of software engineering olcott <NoOne@NoWhere.com> - 2022-07-02 13:41 -0500
Re: Halting problem proofs refuted on the basis of software engineering Mr Flibble <flibble@reddwarf.jmc> - 2022-07-02 19:44 +0100
Re: Halting problem proofs refuted on the basis of software engineering olcott <NoOne@NoWhere.com> - 2022-07-02 16:26 -0500
Re: Halting problem proofs refuted on the basis of software engineering Mr Flibble <flibble@reddwarf.jmc> - 2022-07-02 23:05 +0100
Re: Halting problem proofs refuted on the basis of software engineering olcott <NoOne@NoWhere.com> - 2022-07-02 17:13 -0500
Re: Halting problem proofs refuted on the basis of software engineering Mr Flibble <flibble@reddwarf.jmc> - 2022-07-03 15:27 +0100
Re: Halting problem proofs refuted on the basis of software engineering olcott <NoOne@NoWhere.com> - 2022-07-03 09:57 -0500
Re: Halting problem proofs refuted on the basis of software engineering Mr Flibble <flibble@reddwarf.jmc> - 2022-07-03 16:21 +0100
Re: Halting problem proofs refuted on the basis of software engineering olcott <NoOne@NoWhere.com> - 2022-07-03 10:30 -0500
Re: Halting problem proofs refuted on the basis of software engineering Mr Flibble <flibble@reddwarf.jmc> - 2022-07-03 16:45 +0100
Re: Halting problem proofs refuted on the basis of software engineering olcott <NoOne@NoWhere.com> - 2022-07-03 10:48 -0500
Re: Halting problem proofs refuted on the basis of software engineering Mr Flibble <flibble@reddwarf.jmc> - 2022-07-03 16:51 +0100
Re: Halting problem proofs refuted on the basis of software engineering olcott <NoOne@NoWhere.com> - 2022-07-03 11:05 -0500
Re: Halting problem proofs refuted on the basis of software engineering Mr Flibble <flibble@reddwarf.jmc> - 2022-07-03 17:07 +0100
Re: Halting problem proofs refuted on the basis of software engineering olcott <NoOne@NoWhere.com> - 2022-07-04 11:57 -0500
Re: Halting problem proofs refuted on the basis of software engineering olcott <NoOne@NoWhere.com> - 2022-07-04 14:17 -0500
Re: Halting problem proofs refuted on the basis of software engineering olcott <NoOne@NoWhere.com> - 2022-07-04 14:21 -0500
Re: Halting problem proofs refuted on the basis of software engineering [ Curry–Howard correspondence ] olcott <NoOne@NoWhere.com> - 2022-07-04 18:08 -0500
Re: Halting problem proofs refuted on the basis of software engineering [ Curry–Howard correspondence ] olcott <NoOne@NoWhere.com> - 2022-07-05 14:31 -0500
Re: Halting problem proofs refuted on the basis of software engineering [ Curry–Howard correspondence ] olcott <NoOne@NoWhere.com> - 2022-07-05 15:42 -0500
Re: Halting problem proofs refuted on the basis of software engineering [ Curry–Howard correspondence ] Richard Damon <Richard@Damon-Family.org> - 2022-07-05 19:29 -0400
Re: Halting problem proofs refuted on the basis of software engineering [ Curry–Howard correspondence ] olcott <NoOne@NoWhere.com> - 2022-07-05 19:01 -0500
Re: Halting problem proofs refuted on the basis of software engineering [ Curry–Howard correspondence ] olcott <NoOne@NoWhere.com> - 2022-07-06 16:13 -0500
Re: Halting problem proofs refuted on the basis of software engineering [ Curry–Howard correspondence ] olcott <NoOne@NoWhere.com> - 2022-07-07 16:08 -0500
Re: Halting problem proofs refuted on the basis of software engineering [ Curry–Howard correspondence ] olcott <NoOne@NoWhere.com> - 2022-07-07 20:34 -0500
Re: Halting problem proofs refuted on the basis of software engineering [ Curry–Howard correspondence ] olcott <NoOne@NoWhere.com> - 2022-07-07 23:48 -0500
Re: Halting problem proofs refuted on the basis of software engineering [ Irrefutably Correct ] olcott <NoOne@NoWhere.com> - 2022-07-09 13:40 -0500
Re: Halting problem proofs refuted on the basis of software engineering [ Irrefutably Correct ] Richard Damon <Richard@Damon-Family.org> - 2022-07-09 15:06 -0400
Re: Halting problem proofs refuted on the basis of software engineering [ Curry–Howard correspondence ] olcott <NoOne@NoWhere.com> - 2022-07-05 19:50 -0500
Re: Halting problem proofs refuted on the basis of software engineering [ Curry–Howard correspondence ] olcott <NoOne@NoWhere.com> - 2022-07-05 21:37 -0500
Re: Halting problem proofs refuted on the basis of software engineering olcott <NoOne@NoWhere.com> - 2022-07-05 07:59 -0500
Re: Halting problem proofs refuted on the basis of software engineering olcott <NoOne@NoWhere.com> - 2022-07-05 08:00 -0500
Re: Halting problem proofs refuted on the basis of software engineering Richard Damon <Richard@Damon-Family.org> - 2022-07-05 19:31 -0400
Re: Halting problem proofs refuted on the basis of software engineering olcott <NoOne@NoWhere.com> - 2022-07-13 14:37 -0500
Re: Halting problem proofs refuted on the basis of software engineering olcott <NoOne@NoWhere.com> - 2022-07-13 15:51 -0500
Re: Halting problem proofs refuted on the basis of software engineering olcott <NoOne@NoWhere.com> - 2022-07-13 19:10 -0500
Re: Halting problem proofs refuted on the basis of software engineering Richard Damon <Richard@Damon-Family.org> - 2022-07-13 21:29 -0400
Re: Halting problem proofs refuted on the basis of software engineering Richard Damon <Richard@Damon-Family.org> - 2022-07-13 19:29 -0400
Re: Halting problem proofs refuted on the basis of software engineering olcott <NoOne@NoWhere.com> - 2022-07-15 11:26 -0500
Re: Halting problem proofs refuted on the basis of software engineering olcott <NoOne@NoWhere.com> - 2022-07-16 19:18 -0500
Re: Halting problem proofs refuted on the basis of software engineering Richard Damon <Richard@Damon-Family.org> - 2022-07-16 20:38 -0400
Re: Halting problem proofs refuted on the basis of software engineering olcott <NoOne@NoWhere.com> - 2022-07-16 20:19 -0500
Re: Halting problem proofs refuted on the basis of software engineering [thanks Mike] olcott <NoOne@NoWhere.com> - 2022-07-17 12:00 -0500
Re: Halting problem proofs refuted on the basis of software engineering [thanks Mike] Richard Damon <Richard@Damon-Family.org> - 2022-07-17 13:06 -0400
csiph-web