Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: dbush Newsgroups: comp.theory Subject: Re: DD specifies non-terminating behavior to HHH --- RECURSIVE CHAIN --- Saving Democracy Date: Mon, 24 Feb 2025 08:11:36 -0500 Organization: A noiseless patient Spider Lines: 296 Message-ID: References: MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Mon, 24 Feb 2025 14:11:36 +0100 (CET) Injection-Info: dont-email.me; posting-host="2824c1e0c122bd29eea4e0491b46b547"; logging-data="1165164"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+13/Ab/XpUqEePcejiYqCX" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:iXVPIjhLEoP8d7vhXpMOX9Q1BD0= In-Reply-To: Content-Language: en-US Bytes: 14449 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 : >>>>>>>>>>>>>>    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 ==========