Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: Why I need to cross-post to comp.lang.c --- CORRECTLY REFUTED
Date: Mon, 12 May 2025 10:45:24 +0300
Organization: -
Lines: 113
Message-ID: <vvs8uk$vu1r$1@dont-email.me>
References: <vvmudo$3dk35$1@dont-email.me> <vvnqes$3in62$5@dont-email.me> <vvppls$4155$1@dont-email.me> <vvqhoh$gldn$7@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 12 May 2025 09:45:25 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="d66022cf12555db523e1c5ad57a06eab";
	logging-data="1046587"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18o199dgFc/Y2Y+Inf4iuhe"
User-Agent: Unison/2.2
Cancel-Lock: sha1:1LwhYD3AO8ZVagDisnUovc0LWmE=

On 2025-05-11 16:03:29 +0000, olcott said:

> On 5/11/2025 4:12 AM, Mikko wrote:
>> On 2025-05-10 15:13:32 +0000, olcott said:
>> 
>>> On 5/10/2025 2:15 AM, Mikko wrote:
>>>> On 2025-05-09 03:01:40 +0000, olcott said:
>>>> 
>>>>> On 5/8/2025 9:23 PM, Keith Thompson wrote:
>>>>>> Richard Damon <richard@damon-family.org> writes:
>>>>>>> On 5/8/25 7:53 PM, olcott wrote:
>>>>>> [...]
>>>>>>>> void DDD()
>>>>>>>> {
>>>>>>>>   HHH(DDD);
>>>>>>>>   return;
>>>>>>>> }
>>>>>>>> We don't need to look at any of my code for me
>>>>>>>> to totally prove my point. For example when
>>>>>>>> the above DDD is correctly simulated by HHH
>>>>>>>> this simulated DDD cannot possibly reach its own
>>>>>>>> "return" instruction.
>>>>>>> 
>>>>>>> And thus not correctly simulatd.
>>>>>>> 
>>>>>>> Sorry, there is no "OS Exemption" to correct simulaiton;.
>>>>>> 
>>>>>> Perhaps I've missed something.  I don't see anything in the above that
>>>>>> implies that HHH does not correctly simulate DDD.  Richard, you've read
>>>>>> far more of olcott's posts than I have, so perhaps you can clarify.
>>>>>> 
>>>>>> If we assume that HHH correctly simulates DDD, then the above code is
>>>>>> equivalent to:
>>>>>> 
>>>>>> void DDD()
>>>>>> {
>>>>>> DDD();
>>>>>> return;
>>>>>> }
>>>>>> 
>>>>>> which is a trivial case of infinite recursion.  As far as I can tell,
>>>>>> assuming that DDD() is actually called at some point, neither the
>>>>>> outer execution of DDD nor the nested (simulated) execution of DDD
>>>>>> can reach the return statement.  Infinite recursion might either
>>>>>> cause a stack overflow and a probable program crash, or an unending
>>>>>> loop if the compiler implements tail call optimization.
>>>>>> 
>>>>>> I see no contradiction, just an uninteresting case of infinite
>>>>>> recursion, something that's well understood by anyone with a
>>>>>> reasonable level of programming experience.  (And it has nothing to
>>>>>> do with the halting problem as far as I can tell, though of course
>>>>>> olcott has discussed the halting problem elsewhere.)
>>>>>> 
>>>>>> Richard, what am I missing?
>>>>>> 
>>>>> *****
>>>>> Now you are seeing what I was talking about.
>>>>> Now you are seeing why I needed to cross post
>>>>> to comp.lang.c
>>>> 
>>>> What were you told in comp.lang.c that you were not told in comp.theory?
>>> 
>>> void DDD()
>>> {
>>>    HHH(DDD);
>>>    return;
>>> }
>>> 
>>> People quickly realize that when DDD is correctly
>>> simulated by HHH that DDD cannot possibly reach
>>> its "return" statement (final halt state).
>>> 
>>> Once you know this then you can see that the
>>> same thing applies to DD.
>>> 
>>> int DD()
>>> {
>>>    int Halt_Status = HHH(DD);
>>>    if (Halt_Status)
>>>      HERE: goto HERE;
>>>    return Halt_Status;
>>> }
>>> 
>>> Once you know this then you know that the halting
>>> problem's otherwise "impossible" input is non-halting.
>>> 
>>> Once you know this then you know that the halting
>>> problem proof has been correctly refuted.
>> 
>> You are lying again. Nothing above was told you in comp.lang.c.
> 
> On 5/8/2025 8:30 PM, Keith Thompson wrote:
>  > Assuming that HHH(DDD) "correctly simulates" DDD, and assuming it
>  > does nothing else, your code would be equivalent to this:
>  >
>  >      void DDD(void) {
>  >          DDD();
>  >          return;
>  >      }
>  >
>  > Then the return statement (which is unnecessary anyway) will never be
>  > reached.  In practice, the program will likely crash due to a stack
>  > overflow, unless the compiler implements tail-call optimization, in
>  > which case the program might just run forever -- which also means the
>  > unnecessary return statement will never be reached.
>  >

What he says is true. However, the assumptions that HHH does a correct
simulation and that it does nothing else are not.

-- 
Mikko