Path: 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: Mon, 24 Feb 2025 17:16:04 -0600 Organization: A noiseless patient Spider Lines: 383 Message-ID: References: MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Tue, 25 Feb 2025 00:16:06 +0100 (CET) Injection-Info: dont-email.me; posting-host="5f1bdbe2bf9fd53383ef617592ba422f"; logging-data="1572686"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/biFZ8VlEiuROFL/ZFIElr" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:7mnaxIg0qjpHKMYJvxjXA++ECvQ= X-Antivirus: Norton (VPS 250224-8, 2/24/2025), Outbound message Content-Language: en-US In-Reply-To: X-Antivirus-Status: Clean On 2/24/2025 3:47 PM, dbush wrote: > On 2/24/2025 4:26 PM, olcott wrote: >> On 2/24/2025 9:03 AM, dbush wrote: >>> On 2/24/2025 9:48 AM, olcott wrote: >>>> 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. >>>>>>>>>>>>>>>>>>>> ========== REMAINDER OF ARTICLE TRUNCATED ==========