Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: olcott Newsgroups: comp.theory Subject: Re: DD specifies non-terminating behavior to HHH --- RECURSIVE CHAIN --- Saving Democracy Date: Sun, 23 Feb 2025 23:17:19 -0600 Organization: A noiseless patient Spider Lines: 284 Message-ID: References: <2e999502c40f736a3f3579d23bdb2b42dc74e897@i2pn2.org> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Mon, 24 Feb 2025 06:17:20 +0100 (CET) Injection-Info: dont-email.me; posting-host="ad958933c7b8d1278b7f2c2f3e804b36"; logging-data="981967"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/Q1ZdXAaiZ5BjxwWIxiCdk" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:VWX/F52lxzUsqSq+SWNwmRcy750= X-Antivirus-Status: Clean Content-Language: en-US In-Reply-To: X-Antivirus: Norton (VPS 250223-4, 2/23/2025), Outbound message Bytes: 14019 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 : >>>>>>>>>>>>>    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 >>>>>>>>>>>>>    400545:    5d                       pop    %rbp >>>>>>>>>>>>>    400546:    c3                       retq >>>>>>>>>>>>> >>>>>>>>>>>>> ========== REMAINDER OF ARTICLE TRUNCATED ==========