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 16:47:31 -0500 Organization: A noiseless patient Spider Lines: 399 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 22:47:32 +0100 (CET) Injection-Info: dont-email.me; posting-host="2824c1e0c122bd29eea4e0491b46b547"; logging-data="1549110"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+jlpsB6D/B5f+LrjXbkSyt" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:N9kyBLp2dz+zBSD83JZv7n4FgnE= In-Reply-To: Content-Language: en-US Bytes: 18058 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. >>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>> Similarly: >>>>>>>>>>>>>>>>>> ========== REMAINDER OF ARTICLE TRUNCATED ==========