Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.software-eng > #3498
| From | Mr Flibble <flibble@reddwarf.jmc> |
|---|---|
| Newsgroups | comp.theory, sci.logic, sci.math, comp.software-eng |
| Subject | Re: Halting problem proofs refuted on the basis of software engineering |
| Message-ID | <20220702182653.00003f52@reddwarf.jmc> (permalink) |
| References | <EPWdnbcVB5MW-F3_nZ2dnUU7_83NnZ2d@giganews.com> <20220702172644.00004e9c@reddwarf.jmc> <orWdnUMI9ukU6F3_nZ2dnUU7_8zNnZ2d@giganews.com> <20220702181010.000011c0@reddwarf.jmc> <S8idnfNU_avS4F3_nZ2dnUU7_8zNnZ2d@giganews.com> |
| Organization | Jupiter Mining Corp |
| Date | 2022-07-02 18:26 +0100 |
Cross-posted to 4 groups.
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
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