Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: dbush <dbush.mobile@gmail.com>
Newsgroups: comp.theory
Subject: Re: Why I need to cross-post to comp.lang.c --- CORRECTLY REFUTED
Date: Mon, 12 May 2025 10:53:42 -0400
Organization: A noiseless patient Spider
Lines: 135
Message-ID: <vvt21l$143i8$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>
 <vvs8uk$vu1r$1@dont-email.me> <vvt1l8$14pca$4@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 16:53:42 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="d587ba6f088c47ed8fd2ad250ebfd646";
	logging-data="1183304"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/FtzkcZpBmqSK3zRFdfskR"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:fJwibQrGGQ1MGrRL0IrcFrC3/Tk=
In-Reply-To: <vvt1l8$14pca$4@dont-email.me>
Content-Language: en-US

On 5/12/2025 10:47 AM, olcott wrote:
> On 5/12/2025 2:45 AM, Mikko wrote:
>> 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.
>>
> 
> _DDD()
> [00002172] 55         push ebp      ; housekeeping
> [00002173] 8bec       mov ebp,esp   ; housekeeping
> [00002175] 6872210000 push 00002172 ; push DDD
> [0000217a] e853f4ffff call 000015d2 ; call HHH(DDD)
> [0000217f] 83c404     add esp,+04
> [00002182] 5d         pop ebp
> [00002183] c3         ret
> Size in bytes:(0018) [00002183]
> 
> We make an infinite set of purely hypothetical HHH pure
> x86 emulators each one is at machine address 000015d2
> thus called by DDD.

And each DDD is a distinct algorithm.

Changing the input is not allowed.