Deutsch English Français Italiano |
<vpi0rc$14kaj$1@dont-email.me> View for Bookmarking (what is this?) Look up another Usenet article |
Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: olcott <polcott333@gmail.com> Newsgroups: comp.theory Subject: Re: DD specifies non-terminating behavior to HHH --- RECURSIVE CHAIN --- Saving Democracy Date: Mon, 24 Feb 2025 08:48:12 -0600 Organization: A noiseless patient Spider Lines: 306 Message-ID: <vpi0rc$14kaj$1@dont-email.me> References: <vo6420$3mpmf$1@dont-email.me> <vpd0e5$uj5$1@dont-email.me> <vpd3fg$irt$10@dont-email.me> <vpd4ih$2pvp$1@dont-email.me> <vpd6hp$2q85$3@dont-email.me> <vpd7s7$3e5k$1@dont-email.me> <vpd8pl$3h9q$1@dont-email.me> <vpd97q$3e5k$2@dont-email.me> <vpdaj5$3u9g$1@dont-email.me> <vpdatp$3e5k$3@dont-email.me> <vpddgj$3u9g$2@dont-email.me> <vpddqm$3e5k$4@dont-email.me> <vpdkhv$5kr2$1@dont-email.me> <vpdks8$5ga3$1@dont-email.me> <vpdqc8$6bqs$1@dont-email.me> <vpe1g3$7gnd$1@dont-email.me> <vpflv1$j7qb$1@dont-email.me> <vpfnhm$jena$1@dont-email.me> <vpgded$nkbd$1@dont-email.me> <vpgdn8$nlei$1@dont-email.me> <vpgh33$o4p7$1@dont-email.me> <vpghkq$o82o$1@dont-email.me> <vpgk2q$okhu$1@dont-email.me> <vpgo94$p8he$1@dont-email.me> <vpgoia$p9vl$1@dont-email.me> <vpgrdl$tdkf$1@dont-email.me> <vpgtb3$tiun$2@dont-email.me> <vpgth7$tdkf$3@dont-email.me> <vpgufr$truc$1@dont-email.me> <vpguru$tdkf$4@dont-email.me> <vpgvcv$tuuf$1@dont-email.me> <vphr67$13hrc$1@dont-email.me> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Mon, 24 Feb 2025 15:48:16 +0100 (CET) Injection-Info: dont-email.me; posting-host="25d8d92711a8745794ce62f7c908cd7e"; logging-data="1200467"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+WmX0uByPypedOtxsIVDGO" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:8shQ9vUpvzT+o0I/hWmqdoRLuKk= Content-Language: en-US X-Antivirus: Norton (VPS 250224-4, 2/24/2025), Outbound message In-Reply-To: <vphr67$13hrc$1@dont-email.me> X-Antivirus-Status: Clean On 2/24/2025 7:11 AM, dbush wrote: > On 2/24/2025 12:17 AM, olcott wrote: >> On 2/23/2025 11:08 PM, dbush wrote: >>> On 2/24/2025 12:01 AM, olcott wrote: >>>> On 2/23/2025 10:45 PM, dbush wrote: >>>>> On 2/23/2025 11:42 PM, olcott wrote: >>>>>> On 2/23/2025 10:09 PM, dbush wrote: >>>>>>> On 2/23/2025 10:20 PM, olcott wrote: >>>>>>>> On 2/23/2025 9:15 PM, dbush wrote: >>>>>>>>> On 2/23/2025 9:04 PM, olcott wrote: >>>>>>>>>> On 2/23/2025 7:22 PM, dbush wrote: >>>>>>>>>>> On 2/23/2025 8:13 PM, olcott wrote: >>>>>>>>>>>> On 2/23/2025 6:15 PM, dbush wrote: >>>>>>>>>>>>> On 2/23/2025 7:10 PM, olcott wrote: >>>>>>>>>>>>>> On 2/23/2025 11:57 AM, dbush wrote: >>>>>>>>>>>>>>> On 2/23/2025 12:30 PM, olcott wrote: >>>>>>>>>>>>>>>> On 2/22/2025 8:34 PM, dbush wrote: >>>>>>>>>>>>>>>>> On 2/22/2025 7:33 PM, olcott wrote: >>>>>>>>>>>>>>>>>> On 2/22/2025 4:59 PM, dbush wrote: >>>>>>>>>>>>>>>>>>> On 2/22/2025 5:53 PM, olcott wrote: >>>>>>>>>>>>>>>>>>>> On 2/22/2025 2:59 PM, dbush wrote: >>>>>>>>>>>>>>>>>>>>> On 2/22/2025 3:53 PM, olcott wrote: >>>>>>>>>>>>>>>>>>>>>> On 2/22/2025 2:09 PM, dbush wrote: >>>>>>>>>>>>>>>>>>>>>>> On 2/22/2025 3:03 PM, olcott wrote: >>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>> 01 int F(int i) >>>>>>>>>>>>>>>>>>>>>> 02 { >>>>>>>>>>>>>>>>>>>>>> 03 if (i > 10) >>>>>>>>>>>>>>>>>>>>>> 04 return 0; >>>>>>>>>>>>>>>>>>>>>> 05 else >>>>>>>>>>>>>>>>>>>>>> 06 return F(i+1); >>>>>>>>>>>>>>>>>>>>>> 07 } >>>>>>>>>>>>>>>>>>>>>> 08 >>>>>>>>>>>>>>>>>>>>>> 09 int no_numbers_greater_than_10() >>>>>>>>>>>>>>>>>>>>>> 10 { >>>>>>>>>>>>>>>>>>>>>> 11 return F(0); >>>>>>>>>>>>>>>>>>>>>> 12 } >>>>>>>>>>>>>>>>>>>>>> 13 >>>>>>>>>>>>>>>>>>>>>> 14 int main() >>>>>>>>>>>>>>>>>>>>>> 15 { >>>>>>>>>>>>>>>>>>>>>> 16 F((int)no_numbers_greater_than_10); >>>>>>>>>>>>>>>>>>>>>> 17 return 0; >>>>>>>>>>>>>>>>>>>>>> 18 } >>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>> So if the address of no_numbers_greater_than_10 >>>>>>>>>>>>>>>>>>>>>>> is greater than 10 then 0 is returned right away, >>>>>>>>>>>>>>>>>>>>>>> otherwise as most 10 recursive calls will be made >>>>>>>>>>>>>>>>>>>>>>> before the condition is matched and 0 is returned. >>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>> This doesn't change the fact that >>>>>>>>>>>>>>>>>>>>>>> no_numbers_greater_than_10 correctly >>>>>>>>>>>>>>>>>>>>>>> simulated by F cannot possibly return so >>>>>>>>>>>>>>>>>>>>>>> F(no_numbers_greater_than_10) >>>>>>>>>>>>>>>>>>>>>>> is correct to report non-halting, which means >>>>>>>>>>>>>>>>>>>>>>> that there is no natural >>>>>>>>>>>>>>>>>>>>>>> number greater than 10. >>>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>>> Agreed? >>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>> I think that you will find more bugs when you try to >>>>>>>>>>>>>>>>>>>>>> provide the line number by line number execution >>>>>>>>>>>>>>>>>>>>>> trace. >>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>>> #1 bug F never simulates anything. >>>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>>> It is a verified fact that >>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>>> F never simulates anything when i > 10. >>>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>> Remember, you agreed that the behavior of X simulated >>>>>>>>>>>>>>>>>>> by Y is defined by replacing the code of Y with an >>>>>>>>>>>>>>>>>>> unconditional simulator and running Y(X): >>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>> On 2/22/2025 1:02 PM, olcott wrote: >>>>>>>>>>>>>>>>>>> > On 2/22/2025 11:10 AM, dbush wrote: >>>>>>>>>>>>>>>>>>> >> On 2/22/2025 11:43 AM, olcott wrote: >>>>>>>>>>>>>>>>>>> >>> The first point is DD correctly simulated by HHH >>>>>>>>>>>>>>>>>>> cannot >>>>>>>>>>>>>>>>>>> >>> possibly terminate normally by reaching its own >>>>>>>>>>>>>>>>>>> "return" >>>>>>>>>>>>>>>>>>> >>> instruction. >>>>>>>>>>>>>>>>>>> >> >>>>>>>>>>>>>>>>>>> >> In other words, if the code of HHH is replaced >>>>>>>>>>>>>>>>>>> with an unconditional simulator then it can be shown >>>>>>>>>>>>>>>>>>> that DD is non- halting and therefore HHH(DD)==0 is >>>>>>>>>>>>>>>>>>> correct. >>>>>>>>>>>>>>>>>>> >> >>>>>>>>>>>>>>>>>>> > >>>>>>>>>>>>>>>>>>> > Wow finally someone that totally gets it. >>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>> So the behavior of no_numbers_greater_than_10 >>>>>>>>>>>>>>>>>>> simulated by F is defined by replacing the code of F >>>>>>>>>>>>>>>>>>> with an unconditional simulated and running >>>>>>>>>>>>>>>>>>> F(no_numbers_greater_than_10). >>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>> The finite string input to F proves that there are no >>>>>>>>>>>>>>>>>>> instructions in no_numbers_greater_than_10 that can >>>>>>>>>>>>>>>>>>> break the recursive simulation. >>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>> Try to show how no_numbers_greater_than_10 correctly >>>>>>>>>>>>>>>>>>> simulated by F can possibly halt. >>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>> Then is ceases to be analogous to HHH(DD) because >>>>>>>>>>>>>>>>>> no_numbers_greater_than_10() always terminates normally >>>>>>>>>>>>>>>>>> by reaching its own "return" instruction. >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>> In other words, when we actually run >>>>>>>>>>>>>>>>> no_numbers_greater_than_10() it reaches its own >>>>>>>>>>>>>>>>> "return" instruction. >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>> That means we've now established that the direct >>>>>>>>>>>>>>>>> execution of a program (which includes all the >>>>>>>>>>>>>>>>> functions it calls UNMODIFIED) defines whether or not >>>>>>>>>>>>>>>>> it halts. >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>> Likewise, when we actually run DD() unmodified it also >>>>>>>>>>>>>>>>> reaches its own "return" instruction. >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>> Therefore HHH(DD)==0 is wrong. >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> _DD() >>>>>>>>>>>>>>>> [00002133] 55 push ebp ; housekeeping >>>>>>>>>>>>>>>> [00002134] 8bec mov ebp,esp ; housekeeping >>>>>>>>>>>>>>>> [00002136] 51 push ecx ; make space for local >>>>>>>>>>>>>>>> [00002137] 6833210000 push 00002133 ; push DD >>>>>>>>>>>>>>>> [0000213c] e882f4ffff call 000015c3 ; call HHH(DD) >>>>>>>>>>>>>>>> [00002141] 83c404 add esp,+04 >>>>>>>>>>>>>>>> [00002144] 8945fc mov [ebp-04],eax >>>>>>>>>>>>>>>> [00002147] 837dfc00 cmp dword [ebp-04],+00 >>>>>>>>>>>>>>>> [0000214b] 7402 jz 0000214f >>>>>>>>>>>>>>>> [0000214d] ebfe jmp 0000214d >>>>>>>>>>>>>>>> [0000214f] 8b45fc mov eax,[ebp-04] >>>>>>>>>>>>>>>> [00002152] 8be5 mov esp,ebp >>>>>>>>>>>>>>>> [00002154] 5d pop ebp >>>>>>>>>>>>>>>> [00002155] c3 ret >>>>>>>>>>>>>>>> Size in bytes:(0035) [00002155] >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> When DD is correctly simulated by HHH according to the >>>>>>>>>>>>>>>> behavior >>>>>>>>>>>>>>>> that the above machine code specifies then the call from DD >>>>>>>>>>>>>>>> to HHH(DD) cannot possibly return and this correctly >>>>>>>>>>>>>>>> simulated >>>>>>>>>>>>>>>> DD cannot possibly terminate normally by reaching its >>>>>>>>>>>>>>>> own machine >>>>>>>>>>>>>>>> address 00002155. >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> Similarly: >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> 0000000000400534 <no_numbers_greater_than_10>: >>>>>>>>>>>>>>> 400534: 55 push %rbp >>>>>>>>>>>>>>> 400535: 48 89 e5 mov %rsp,%rbp >>>>>>>>>>>>>>> 400538: b8 34 05 40 00 mov $0x400534,%eax >>>>>>>>>>>>>>> 40053d: 48 89 c7 mov %rax,%rdi >>>>>>>>>>>>>>> 400540: e8 a8 ff ff ff callq 4004ed <F> >>>>>>>>>>>>>>> 400545: 5d pop %rbp ========== REMAINDER OF ARTICLE TRUNCATED ==========