| olcott <NoOne@NoWhere.com>: Jun 13 10:41PM -0500 On 6/13/2022 3:46 PM, Juha Nieminen wrote: > When it comes to theoretical computer science, you might want to ask > computer scientists rather than software engineers. *Sometimes* those > two coincide but not nearly always. The very weird problem in this case is that software engineering has caught a very subtle mistake that computer science textbooks have been making regarding the halting problem. My paper details this mistake in Appendix I. Without getting into the details that are outside of the scope of this forum all that I really need here is a step-by-step confirmation that H(P,P) correctly determines that the correct x86 emulation of its input would never reach the "ret" instruction of this input. *I know that it is already as obvious as Hell* #include <stdint.h> #define u32 uint32_t void P(u32 x) { if (H(x, x)) HERE: goto HERE; return; } int main() { Output("Input_Halts = ", H((u32)P, (u32)P)); } _P() [00001352](01) 55 push ebp [00001353](02) 8bec mov ebp,esp [00001355](03) 8b4508 mov eax,[ebp+08] [00001358](01) 50 push eax // push P [00001359](03) 8b4d08 mov ecx,[ebp+08] [0000135c](01) 51 push ecx // push P [0000135d](05) e840feffff call 000011a2 // call H [00001362](03) 83c408 add esp,+08 [00001365](02) 85c0 test eax,eax [00001367](02) 7402 jz 0000136b [00001369](02) ebfe jmp 00001369 [0000136b](01) 5d pop ebp [0000136c](01) c3 ret Size in bytes:(0027) [0000136c] _main() [00001372](01) 55 push ebp [00001373](02) 8bec mov ebp,esp [00001375](05) 6852130000 push 00001352 // push P [0000137a](05) 6852130000 push 00001352 // push P [0000137f](05) e81efeffff call 000011a2 // call H [00001384](03) 83c408 add esp,+08 [00001387](01) 50 push eax [00001388](05) 6823040000 push 00000423 // "Input_Halts = " [0000138d](05) e8e0f0ffff call 00000472 // call Output [00001392](03) 83c408 add esp,+08 [00001395](02) 33c0 xor eax,eax [00001397](01) 5d pop ebp [00001398](01) c3 ret Size in bytes:(0039) [00001398] machine stack stack machine assembly address address data code language ======== ======== ======== ========= ============= ...[00001372][0010229e][00000000] 55 push ebp ...[00001373][0010229e][00000000] 8bec mov ebp,esp ...[00001375][0010229a][00001352] 6852130000 push 00001352 // push P ...[0000137a][00102296][00001352] 6852130000 push 00001352 // push P ...[0000137f][00102292][00001384] e81efeffff call 000011a2 // call H Begin Local Halt Decider Simulation Execution Trace Stored at:212352 // H emulates the first seven instructions of P ...[00001352][0021233e][00212342] 55 push ebp // enter P ...[00001353][0021233e][00212342] 8bec mov ebp,esp ...[00001355][0021233e][00212342] 8b4508 mov eax,[ebp+08] ...[00001358][0021233a][00001352] 50 push eax // push P ...[00001359][0021233a][00001352] 8b4d08 mov ecx,[ebp+08] ...[0000135c][00212336][00001352] 51 push ecx // push P ...[0000135d][00212332][00001362] e840feffff call 000011a2 // call H // The emulated H emulates the first seven instructions of P ...[00001352][0025cd66][0025cd6a] 55 push ebp // enter P ...[00001353][0025cd66][0025cd6a] 8bec mov ebp,esp ...[00001355][0025cd66][0025cd6a] 8b4508 mov eax,[ebp+08] ...[00001358][0025cd62][00001352] 50 push eax // push P ...[00001359][0025cd62][00001352] 8b4d08 mov ecx,[ebp+08] ...[0000135c][0025cd5e][00001352] 51 push ecx // push P ...[0000135d][0025cd5a][00001362] e840feffff call 000011a2 // call H Local Halt Decider: Infinite Recursion Detected Simulation Stopped It is completely obvious that when H(P,P) correctly emulates its input that it must emulate the first seven instructions of P. Because the seventh instruction of P repeats this process we know with complete certainty that the correct and complete emulation of P by H would never reach the final "ret" instruction of P, thus never halts. ...[00001384][0010229e][00000000] 83c408 add esp,+08 ...[00001387][0010229a][00000000] 50 push eax ...[00001388][00102296][00000423] 6823040000 push 00000423 // "Input_Halts = " ---[0000138d][00102296][00000423] e8e0f0ffff call 00000472 // call Output Input_Halts = 0 ...[00001392][0010229e][00000000] 83c408 add esp,+08 ...[00001395][0010229e][00000000] 33c0 xor eax,eax ...[00001397][001022a2][00100000] 5d pop ebp ...[00001398][001022a6][00000004] c3 ret Number of Instructions Executed(15892) = 237 pages Halting problem undecidability and infinitely nested simulation (V5) https://www.researchgate.net/publication/359984584_Halting_problem_undecidability_and_infinitely_nested_simulation_V5 -- Copyright 2022 Pete Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer |
| Muttley@dastardlyhq.com: Jun 14 08:45AM On Mon, 13 Jun 2022 20:46:45 -0000 (UTC) >When it comes to theoretical computer science, you might want to ask >computer scientists rather than software engineers. *Sometimes* those >two coincide but not nearly always. Software engineer usually implies some form of CS knowledge/training whereas programmer or worse coder usually means someone self taught or moved over from another area with no formal training. Though as with most definitions its various shades of grey. These days though with every 3rd idiot trying to "code" (ie write some mickey most HTML/javascript) because they keep getting told it by vested interests wanting to sell their latest low/no-code software or clueless government types trying to push unsuitable people into IT we're going to find ever more of them in the industry with ever lower software standards. |
| olcott <NoOne@NoWhere.com>: Jun 14 09:23AM -0500 > wanting to sell their latest low/no-code software or clueless government types > trying to push unsuitable people into IT we're going to find ever more of > them in the industry with ever lower software standards. Here are the detailed required credentials: To fully understand this paper a software engineer must be an expert in: the C programming language, the x86 programming language, exactly how C translates into x86 and the ability to recognize infinite recursion at the x86 assembly language level. No knowledge of the halting problem is required. -- Copyright 2022 Pete Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer |
| Muttley@dastardlyhq.com: Jun 14 03:26PM On Tue, 14 Jun 2022 09:23:15 -0500 >the x86 programming language Most people call it assembler. But I guess you have to be different. |
| olcott <NoOne@NoWhere.com>: Jun 14 10:53AM -0500 > olcott <NoOne@NoWhere.com> wrote: >> the x86 programming language > Most people call it assembler. But I guess you have to be different. Most specifically is the the x86 assembly language contained in the COFF object files that are generated by the Microsoft C compiler when executed in 32-bit mode. The x86utm operating system that I wrote takes a 32-bit mode COFF object file as input. -- Copyright 2022 Pete Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer |
| Muttley@dastardlyhq.com: Jun 14 04:00PM On Tue, 14 Jun 2022 10:53:51 -0500 >object files that are generated by the Microsoft C compiler when >executed in 32-bit mode. The x86utm operating system that I wrote takes >a 32-bit mode COFF object file as input. Thats not a language, thats machine code. |
| olcott <NoOne@NoWhere.com>: Jun 14 11:41AM -0500 >> executed in 32-bit mode. The x86utm operating system that I wrote takes >> a 32-bit mode COFF object file as input. > Thats not a language, thats machine code. I adapted the x86 emulator to dis-assemble the machine language so that all the x86 source in the whole COFF file can be seen. The x86 execution trace also shows the x86 source-code of every line that is emulated. -- Copyright 2022 Pete Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer |
| Juha Nieminen <nospam@thanks.invalid>: Jun 14 04:57PM > programmer or worse coder usually means someone self taught or moved over > from another area with no formal training. Though as with most definitions > its various shades of grey. I think "software engineer" usually refers to a job title, not an acadmic title (those would be MSc, PhD, etc.) It's perfectly possible to be a really competent software engineer and have absolutely no idea what "computational complexity" means. |
| "daniel...@gmail.com" <danielaparker@gmail.com>: Jun 14 10:09AM -0700 On Tuesday, June 14, 2022 at 12:57:54 PM UTC-4, Juha Nieminen wrote: > It's perfectly possible to be a really competent software engineer and have > absolutely no idea what "computational complexity" means. The word "engineer" has unfortunately been much debased in the computer industry, particularly with that absurd title "Microsoft Solution Engineer". Real engineers were actually personally responsible for their work. Daniel |
| olcott <NoOne@NoWhere.com>: Jun 14 12:09PM -0500 On 6/14/2022 11:57 AM, Juha Nieminen wrote: > title (those would be MSc, PhD, etc.) > It's perfectly possible to be a really competent software engineer and have > absolutely no idea what "computational complexity" means. To fully understand this paper a software engineer must be an expert in: the C programming language, the x86 programming language, exactly how C translates into x86 and the ability to recognize infinite recursion at the x86 assembly language level. No knowledge of the halting problem is required. -- Copyright 2022 Pete Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer |
| red floyd <no.spam.here@its.invalid>: Jun 14 10:44AM -0700 On 6/13/2022 1:46 PM, Juha Nieminen wrote: > When it comes to theoretical computer science, you might want to ask > computer scientists rather than software engineers. *Sometimes* those > two coincide but not nearly always. Please remove comp.lang.c++ from this thread. It is off topic and clogging up c.l.c++. Thank you. |
| Mr Flibble <flibble@reddwarf.jmc>: Jun 14 06:44PM +0100 On Tue, 14 Jun 2022 11:41:22 -0500 > that all the x86 source in the whole COFF file can be seen. The x86 > execution trace also shows the x86 source-code of every line that is > emulated. Disassembly isn't source code. Also, it is quite telling when you say "no knowledge of the halting problem is required": this is correct as what you have has nothing to do with the halting problem as your H isn't a halting decider: it is an olcott simulation detector, a fairly useless widget. /Flibble |
| Richard Damon <Richard@Damon-Family.org>: Jun 13 08:40PM -0400 On 6/13/22 2:45 PM, olcott wrote: > complete emulation of the input would never stop running, or reach its > "ret" instruction then the SHD aborts its emulation and correctly > returns 0. You keep on missing that no such pattern exists in the emulation of P(P), as if H has a pattern that is seees in P(P) and aborts its simulation because of that, then when P(P) calls H(P,P) that H will emulate for a while, abort its emulation, and then return 0 to P which will Halt. Thus the P(P) when built with an H with that pattern shows that the pattern is not a correct non-halting behavior pattern, as a program with that pattern halts. So, a SHD based on that rule will just emulate for ever, doing a correct and complete emulatin, but not giving the 0 answers, because if at any finite point in time it aborts, it changes P to be Halting. FAIL. |
| olcott <NoOne@NoWhere.com>: Jun 13 07:47PM -0500 On 6/13/2022 7:40 PM, Richard Damon wrote: >> returns 0. > You keep on missing that no such pattern exists in the emulation of > P(P), Even Flibble see the pattern. -- Copyright 2022 Pete Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer |
| Richard Damon <Richard@Damon-Family.org>: Jun 13 09:15PM -0400 On 6/13/22 8:47 PM, olcott wrote: >>> returns 0. >> You keep on missing that no such pattern exists in the emulation of P(P), > Even Flibble see the pattern. Can you point to the message where he actually says that? (since he realized that halt decider doesn't actually need to simulate its input, only does it by choise in your case) |
| Paul N <gw7rib@aol.com>: Jun 14 04:47AM -0700 OK, I'll bite. Apologies to all those who would rather this conversation was not here. Firstly, I think it needs to be said that the Halting Problem only applies to an infinite machine. If a computer has only a finite number of states (as so many of them do) and moves between them at a constant rate, then a suitable emulator could work out whether a program terminates simply by looking for a repeated state. Either the program terminates, or after N states you must be back to a state you have already had, where N is the number of possible states. This may be where Mr Olcott is going wrong. On Monday, June 13, 2022 at 7:46:22 PM UTC+1, olcott wrote: > [00001362](03) 83c408 add esp,+08 > [00001365](02) 85c0 test eax,eax > [00001367](02) 7402 jz 0000136b This is a conditional jump past the next instruction > [00001369](02) ebfe jmp 00001369 Yes, if the program gets to this line, it will go into an infinite loop. We can't tell just from this code whether or not this will happen, as it is dependent on the jump above which is dependent on H, which you haven't shown us (at least not in this post), so the code itself does not answer the question. > seventh instruction of P repeats this process we can know with complete > certainty that the emulated P never reaches its final "ret" instruction, > thus never halts. Yes, it is clear to us humans watching it that the program is repeating itself. Thus we can appreciate that it will never reach the final "ret" - indeed, it won't even get to the infinite loop identified above. But does the computer itself know this? If the emulator simply emulates the instructions given, it will not realise that it is doing the same thing over and over again. If it does look out for this, spotting a repeated state, then it can tell that the program under consideration will not halt. The answer to whether it spots this lies in the emulator, which you haven't shown the code for. However, an emulator which does this is not accurately emulating the program in question. The emulator is stopping and saying it has found an infinite loop, whereas the program itself would do no such thing and would run forever. Thus their behaviours are different. You say that you have come to comp.lang.c and comp.lang.c++ is to check the points which relate to the language. I think what I have written above is probably about as much as you will be able to get from these groups. Your understanding of the language points appears to be correct. |
| olcott <NoOne@NoWhere.com>: Jun 14 09:30AM -0500 On 6/14/2022 6:47 AM, Paul N wrote: >> certainty that the emulated P never reaches its final "ret" instruction, >> thus never halts. > Yes, it is clear to us humans watching it that the program is repeating itself. Thus we can appreciate that it will never reach the final "ret" - indeed, it won't even get to the infinite loop identified above. But does the computer itself know this? H knows this and returns 0 on the basis. > If the emulator simply emulates the instructions given, it will not realise that it is doing the same thing over and over again. H has code that recognizes infinite behavior patterns. > If it does look out for this, spotting a repeated state, then it can tell that the program under consideration will not halt. The answer to whether it spots this lies in the emulator, which you haven't shown the code for. I have re-engineered the code to make it a pure function of its inputs. Not knowing how to do this prevented me from publishing the code. I have updated the algorithm so that it is a pure function of its inputs. As soon as P calls H for the first time, H (knowing its own machine address) is able to look though the prior execution trace and see that P is calling H with the same arguments that it was called with and there are no instructions in P that would break this cycle. > However, an emulator which does this is not accurately emulating the program in question. The emulator is stopping and saying it has found an infinite loop, whereas the program itself would do no such thing and would run forever. Thus their behaviours are different. The criterion measure for a simulating halt decider (SHD) When the correct partial x86 emulation of the input matches a non-halting behavior pattern such that it correctly determines that a complete emulation of the input would never stop running, or reach its "ret" instruction then the SHD aborts its emulation and correctly returns 0. > You say that you have come to comp.lang.c and comp.lang.c++ is to check the points which relate to the language. I think what I have written above is probably about as much as you will be able to get from these groups. Your understanding of the language points appears to be correct. Yes you did a very excellent job thanks. Thus you agree that H(P,P)==0 is correct. -- Copyright 2022 Pete Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer |
| Muttley@dastardlyhq.com: Jun 14 03:25PM On Tue, 14 Jun 2022 04:47:35 -0700 (PDT) >table emulator could work out whether a program terminates simply by lookin= >g for a repeated state. Either the program terminates, or after N states yo= >u must be back to a state you have already had, where N is the number of po= That only holds if there's no external input which cannot be known in advance that can affect its state. |
| olcott <NoOne@NoWhere.com>: Jun 14 10:36AM -0500 >> u must be back to a state you have already had, where N is the number of po= > That only holds if there's no external input which cannot be known in advance > that can affect its state. P is the input to H and P is the input to P. H uses a very powerful open source x86 emulator top emulate its input. The criterion measure for a simulating halt decider (SHD) When the correct partial x86 emulation of the input matches a non-halting behavior pattern such that it correctly determines that a complete emulation of the input would never stop running, or reach its "ret" instruction then the SHD aborts its emulation and correctly returns 0. void P(u32 x) { if (H(x, x)) HERE: goto HERE; return; } int main() { Output("Input_Halts = ", H((u32)P, (u32)P)); } _P() [00001352](01) 55 push ebp [00001353](02) 8bec mov ebp,esp [00001355](03) 8b4508 mov eax,[ebp+08] [00001358](01) 50 push eax // push P [00001359](03) 8b4d08 mov ecx,[ebp+08] [0000135c](01) 51 push ecx // push P [0000135d](05) e840feffff call 000011a2 // call H [00001362](03) 83c408 add esp,+08 [00001365](02) 85c0 test eax,eax [00001367](02) 7402 jz 0000136b [00001369](02) ebfe jmp 00001369 [0000136b](01) 5d pop ebp [0000136c](01) c3 ret Size in bytes:(0027) [0000136c] Halting problem undecidability and infinitely nested simulation (V5) https://www.researchgate.net/publication/359984584_Halting_problem_undecidability_and_infinitely_nested_simulation_V5 -- Copyright 2022 Pete Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer |
| Juha Nieminen <nospam@thanks.invalid>: Jun 14 04:54PM > the program terminates, or after N states you must be back to a > state you have already had, where N is the number of possible > states. This may be where Mr Olcott is going wrong. It is my understanding that whenever a question is posed about an algorithm or program in theoretical computer science, failure states caused by the running environment (eg. running out of RAM) are not part of the scenario, because that's irrelevant to the question at hand. In other words, we can always assume there's no external factor interfering with the program. For example, if the question is what's the computational complexity of a particular sorting algorithm, the question always assumes that the running environment doesn't pose any physical limits (eg. on memory amount). The question becomes a bit meaningless if we had to assume some upper limit in the running environment. Rather obviously the famous Halting Problem isn't asking if a program will halt or run forever in an x86-64 PC with 32 GB of RAM. That would make the question meaningless. Likewise if we are asking "does a program testing the Collatz conjecture eventually end when it finds a counter-example?" we are not asking "does the program eventually end with an 'out of memory' error because it's being run in a computer with limited RAM?" Incidentally, if the halting problem were answerable, that would automatically solve some of the biggest mathematical conjectures out there (like the Collatz conjecture). |
| olcott <NoOne@NoWhere.com>: Jun 14 12:08PM -0500 On 6/14/2022 11:54 AM, Juha Nieminen wrote: > Incidentally, if the halting problem were answerable, that would > automatically solve some of the biggest mathematical conjectures > out there (like the Collatz conjecture). There is a difference between undecidable: Neither Boolean value is correct because the decision problem is self-contradictory and undecided: The decision problem requires information that is currently unavailable. -- Copyright 2022 Pete Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer |
| Keith Thompson <Keith.S.Thompson+u@gmail.com>: Jun 14 10:12AM -0700 > OK, I'll bite. Apologies to all those who would rather this conversation was not here. olcott dominates comp.theory. You can interact with him there. You can also see multiple years of his posting history. -- Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com Working, but not speaking, for Philips void Void(void) { Void(); } /* The recursive call of the void */ |
| olcott <NoOne@NoWhere.com>: Jun 14 12:21PM -0500 On 6/14/2022 12:12 PM, Keith Thompson wrote: >> OK, I'll bite. Apologies to all those who would rather this conversation was not here. > olcott dominates comp.theory. You can interact with him there. You can > also see multiple years of his posting history. The people on comp.theory are unable to critique my work an the basis of software engineering: To fully understand this paper a software engineer must be an expert in: the C programming language, the x86 programming language, exactly how C translates into x86 and the ability to recognize infinite recursion at the x86 assembly language level. No knowledge of the halting problem is required. -- Copyright 2022 Pete Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer |
| Albert Arkwright <Albert.Arkwright@gmail.com>: Jun 14 06:28PM +0100 On 14/06/2022 18:21, olcott wrote: > The people on comp.theory are unable to critique my work an the basis > of software engineering: They are too smart for you. They have known you for years and you are on their kill-file for too long. It is a matter of time that C and C++ programmers will come to understand you more here and kill-file you after they have reported you to "abuse@giganews.com". Enough is enough and there is a limit how much they can take your crap. |
| olcott <NoOne@NoWhere.com>: Jun 14 12:40PM -0500 On 6/14/2022 12:28 PM, Albert Arkwright wrote: > programmers will come to understand you more here and kill-file you > after they have reported you to "abuse@giganews.com". Enough is enough > and there is a limit how much they can take your crap. Only people that baselessly reject what I say out-of-hand without review come to that conclusion. Anyone that correctly reviews my claim validates that it is correct. On 6/14/2022 6:47 AM, Paul N wrote: > Thus we can appreciate that it will never > reach the final "ret" - indeed, it won't > even get to the infinite loop identified above. #include <stdint.h> typedef void (*ptr)(); void P(ptr x) { if (H(x, x)) HERE: goto HERE; return; } int main() { Output("Input_Halts = ", H(P, P)); } _P() [00001352](01) 55 push ebp [00001353](02) 8bec mov ebp,esp [00001355](03) 8b4508 mov eax,[ebp+08] [00001358](01) 50 push eax // push P [00001359](03) 8b4d08 mov ecx,[ebp+08] [0000135c](01) 51 push ecx // push P [0000135d](05) e840feffff call 000011a2 // call H [00001362](03) 83c408 add esp,+08 [00001365](02) 85c0 test eax,eax [00001367](02) 7402 jz 0000136b [00001369](02) ebfe jmp 00001369 [0000136b](01) 5d pop ebp [0000136c](01) c3 ret Size in bytes:(0027) [0000136c] It is completely obvious that when H(P,P) correctly emulates its input that it must emulate the first seven instructions of P. Because the seventh instruction of P repeats this process we know with complete certainty that the correct and complete emulation of P by H would never reach the final "ret" instruction of P, thus never halts. -- Copyright 2022 Pete Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer |
| You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com. |
No comments:
Post a Comment