Path: ...!news.misty.com!weretis.net!feeder9.news.weretis.net!news.quux.org!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: Sun, 23 Feb 2025 12:57:10 -0500 Organization: A noiseless patient Spider Lines: 148 Message-ID: References: <855e571c6668207809e1eb67138de6af48d164fa@i2pn2.org> <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: Sun, 23 Feb 2025 18:57:10 +0100 (CET) Injection-Info: dont-email.me; posting-host="a3d0437002d06bb71b23761906f180bc"; logging-data="637674"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18CwDkO9nkglJ2WLNc6U9rY" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:TE7PrPL2g7Pr7yY0kC+y1NZqfsg= In-Reply-To: Content-Language: en-US Bytes: 7490 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?