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: Sat, 22 Feb 2025 14:40:44 -0500 Organization: A noiseless patient Spider Lines: 110 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: Sat, 22 Feb 2025 20:40:43 +0100 (CET) Injection-Info: dont-email.me; posting-host="71441c56d83220426f9b7c1ba6da31b6"; logging-data="112820"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18aWCCBwA7wIUYPJLh00XeK" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:JP0IoE5pvqcV8XTI2NLtmAqsAms= Content-Language: en-US In-Reply-To: Bytes: 5736 On 2/22/2025 2:33 PM, olcott wrote: > On 2/22/2025 1:17 PM, dbush wrote: >> On 2/22/2025 1:54 PM, olcott wrote: >>> On 2/22/2025 12:21 PM, dbush wrote: >>>> On 2/22/2025 1:02 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 >>>>> 10 int no_numbers_greater_than_10() >>>>> 11 { >>>>> 12      return F(0); >>>>> 13 } >>>>> 14 >>>>> 15 int main() >>>>> 16 { >>>>> 17   no_numbers_greater_than_10(); >>>>> 18   return 0; >>>>> 19 } >>>> >>>> Actually, let's update main: >>>> >>>> int main() >>>> { >>>>     F((int)no_numbers_greater_than_10); >>>>     return 0; >>>> } >>>> >>>>>> >>>>>> The function no_numbers_greater_than_10() checks if any natural >>>>>> number exists that is greater than 10.  It does this by checking >>>>>> all natural numbers one at a time.  If one such number exists it >>>>>> halts and return 0.   If no such number exists, it will run >>>>>> forever as no such number will satisfy the condition. >>>>>> >>>>> >>>>> Your code is incomplete. I added main() with line numbers. >>>>> >>>>>> We can see that no_numbers_greater_than_10 correctly simulated by >>>>>> F cannot possibly terminate normal by reaching its own "return" >>>>>> instruction.  This means that F correctly reports that >>>>>> no_numbers_greater_than_10 is non-halting.  It further means, >>>>>> since no_numbers_greater_than_10  doesn't halt that there is no >>>>>> natural number greater than 10. >>>>>> >>>>>> Agreed? >>>>> >>>>> Here the execution trace that I see: >>>>> 15, 16, 17, 10, 11, 12, 01, 02, 03, 04, 12, 18, 19 >>>>> >>>> >>>> Just as you say we're not talking about the direct execution of DD, >>>> we're also not talking about the direct execution of >>>> no_numbers_greater_than_10.  We're talking about >>>> no_numbers_greater_than_10 correctly simulated by F. >>>> >>>> It's a verified 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? >>>> >>> >>> Leaving out main() made this difficult. >>> We can assume that the address of no_numbers_greater_than_10 > 10. >>> This will emulate no_numbers_greater_than_10 at incorrect byte offsets >>> causing it to crash. This may or may not make F crash depending >>> on how robust its emulator is. >>> >> >> Let's make a small change so that wraparound is well defined: >> >> int F(uintptr_t i) >> { >>       if (i<10) { >>           return 0; >>       } else { >>           return F(i+1); >>       } >> } >> >> This ensures that F((uintptr_t)no_numbers_greater_than_10) returns 0. >> >> 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 starts out as the address of > no_numbers_greater_than_10 > Then causes the emulation to crash. > If that address is greater than 10 then F returns 0 right away, otherwise it makes at most 10 recursive calls before returning 0, so there would be no crash. So you agree that no_numbers_greater_than_10 correctly simulated by F (i.e. if the body of the function F is replaced by an unconditional simulator as you said is correct) cannot possibly return?