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 20:04:10 -0600 Organization: A noiseless patient Spider Lines: 200 Message-ID: References: <8fa176d46bf5b8c36def9e32ced67a1a3f81bae1@i2pn2.org> <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 03:04:11 +0100 (CET) Injection-Info: dont-email.me; posting-host="977993bde206852866d0654995b93338"; logging-data="807486"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18bPv1lKMbuuOMO/jHIR/B5" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:FZSq3gnRrniQtLmTYyIB6CwiAPU= In-Reply-To: Content-Language: en-US X-Antivirus: Norton (VPS 250223-4, 2/23/2025), Outbound message X-Antivirus-Status: Clean Bytes: 10148 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 >>>>> >>>>> >>>>> When no_numbers_greater_than_10 is correctly simulated by F >>>>> according to the behavior that the above machine code specifies >>>>> then the call from no_numbers_greater_than_10  to >>>>> F(no_numbers_greater_than_10) cannot possibly terminate normally by >>>>> reaching its own machine address 400545 >>>>> >>>>> So F(no_numbers_greater_than_10)==0 is correct, and therefore no >>>>> natural number exists that is greater than 10 >>>>> >>>>> Agreed? >>>> >>>> I Only understand Intel format assembly language. >>>> >>> >>> It corresponds to the following C code: ========== REMAINDER OF ARTICLE TRUNCATED ==========