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: Tue, 13 May 2025 12:10:44 +0300
Organization: -
Lines: 148
Message-ID: <vvv2ak$1nn58$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: Tue, 13 May 2025 11:10:45 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="750596557f20df3e002f3b81eee75bcc";
	logging-data="1825960"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19L597U8QGSKu/HOEpIePa8"
User-Agent: Unison/2.2
Cancel-Lock: sha1:Kg49OPoo3mfhMBAdwU/apOmwFWg=

On 2025-05-12 14:47:04 +0000, olcott said:

> 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.

You can't do that without violating your earlier statement that
HHH always means the code in halt7.c on your Github repository.

> The first HHH emulates one step the Nth HHH emulates N steps.
> No DDD of any HHH/DDD pair every reaches its own "ret"
> instruction final halt state.

They do. The HHH jsut does do that for the pair containing that
particular HHH. That you don't try another HHH does not mean
that it cannot be dane.

> Since every DDD element of every every HHH/DDD
> pair fails to halt therefore every HHH would be
> correct to reject its input as non-halting.

No, it is not correct to reject an input just because other deciders
reject other inputs.

-- 
Mikko