Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: olcott <polcott333@gmail.com>
Newsgroups: comp.theory
Subject: Re: Incorrect requirements --- Computing the mapping from the input
 to HHH(DD)
Date: Thu, 8 May 2025 23:49:46 -0500
Organization: A noiseless patient Spider
Lines: 167
Message-ID: <vvk1ha$2ibbd$1@dont-email.me>
References: <vv97ft$3fg66$1@dont-email.me> <vvgr22$1ag3a$2@dont-email.me>
 <vvgt36$1auqp$2@dont-email.me> <vvgtbe$1b0li$1@dont-email.me>
 <vvguot$1auqp$3@dont-email.me> <vvh0t2$1b939$1@dont-email.me>
 <vvhap5$1hp80$1@dont-email.me> <vvhf20$1ihs9$1@dont-email.me>
 <vvhfnd$1hvei$3@dont-email.me> <vvil99$1ugd5$1@dont-email.me>
 <vvinvp$1vglb$1@dont-email.me> <vviv75$222r6$1@dont-email.me>
 <vvj1fp$22a62$1@dont-email.me> <vvj2j6$23gk7$1@dont-email.me>
 <as9TP.251456$lZjd.93653@fx05.ams4> <87msbmeo3b.fsf@nosuchdomain.example.com>
 <vvjcge$27753$2@dont-email.me> <87a57mek8r.fsf@nosuchdomain.example.com>
 <vvjgh7$28g5i$4@dont-email.me> <87seled0zy.fsf@nosuchdomain.example.com>
 <vvjobj$28g5i$11@dont-email.me> <87zffmbeyt.fsf@nosuchdomain.example.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Fri, 09 May 2025 06:49:50 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="b8226b0a928845ead4a9adb4b3b34c7d";
	logging-data="2698605"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX187ix8BbGcBmZ7uJQiZ5ZYq"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:pl94XaFxt2JdsKFLADhQ7u1Aj9E=
X-Antivirus-Status: Clean
X-Antivirus: Norton (VPS 250508-4, 5/8/2025), Outbound message
In-Reply-To: <87zffmbeyt.fsf@nosuchdomain.example.com>
Content-Language: en-US

On 5/8/2025 11:11 PM, Keith Thompson wrote:
> olcott <polcott333@gmail.com> writes:
>> On 5/8/2025 8:30 PM, Keith Thompson wrote:
>>> olcott <polcott333@gmail.com> writes:
>>>> On 5/8/2025 6:49 PM, Keith Thompson wrote:
>>>>> olcott <polcott333@gmail.com> writes:
>>>>> [...]
>>>>>> void DDD()
>>>>>> {
>>>>>>      HHH(DDD);
>>>>>>      return;
>>>>>> }
>>>>>>
>>>>>> If you are a competent C programmer then you
>>>>>> know that DDD correctly simulated by HHH cannot
>>>>>> possibly each its own "return" instruction.
>>>>> "cannot possibly each"?
>>>>> I am a competent C programmer (and I don't believe you can make
>>>>> the same claim).  I don't know what HHH is.  The name "HHH" tells
>>>>> me nothing about what it's supposed to do.  Without knowing what
>>>>> HHH is, I can't say much about your code (or is it pseudo-code?).
>>>>>
>>>>
>>>> For the purpose of this discussion HHH is exactly
>>>> what I said it is. It correctly simulates DDD.
>>> Does HHH correctly simulate DDD *and do nothing else*?
>>> Does HHH correctly simulate *every* function whose address is passed
>>> to it?  Must the passed function be one that takes no arguments
>>> and does not return a value?
>>> Can HHH just *call* the function whose address is passed to it?
>>> If it's a correct simulation, there should be no difference between
>>> calling the function and "correctly simulating" it.
>>> My knowledge of C tells me nothing about *how* HHH might simulate
>>> DDD.
>>
>> HHH can only simulate a function that take no arguments
>> and has no return value. HHH also simulates the entire
>> chain of functions that this function calls. These can
>> take arguments or not and have return values or not.
>>
>> Thus HHH ends up simulating itself (and everything
>> that HHH calls) simulating DDD in an infinite
>> sequence of recursive emulation until OOM error.
>>
>>>> We need not know anything else about HHH to
>>>> know that DDD correctly simulated by HHH cannot
>>>> possibly REACH its own "return" instruction.
>>> 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;
>>>       }
>>
>> Exactly. None of these people on comp.theory could
>> get that even after three years.
> 
> I find that difficult to believe.
> 
>>> Then the return statement (which is unnecessary anyway) will never be
>>> reached.
>>
>> It is only there to mark a final halt state.
> 
> The closing "}" does that equally well.
> 
>>> 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.
>>>
>>
>> Yes you totally have this correctly.
>> None of the dozens of comp.theory people could
>> ever achieve that level of understanding even
>> after three years. That is why I needed to post
>> on comp.lang.c.
> 
> I'll note that I've posted in comp.theory, not in comp.lang.c.
> I never see anything you post in comp.lang.c.
> 
>>> This conclusion relies on my understanding of what you've said about
>>> your code, which I consider to be unreliable.
>>
>> I am not even talking about my code. I am
>> talking about the purely hypothetical code
>> that you just agreed to.
> 
> Do not overestimate what I've agreed to.  I must still consider the
> possibility that I've been led into a logical trap of some sort,
> and that I've missed some subtle flaw.
> 
>>> No doubt you believe that there is some significance to the
>>> apparent fact that the return statement will never be reached,
>>> assuming that's a correct and relevant conclusion.  I don't know
>>> what that significance might be.
>>
>> I will tell you that later after you understand
>> some prerequisite ideas first.
>>
>> int DD()
>> {
>>    int Halt_Status = HHH(DD);
>>    if (Halt_Status)
>>      HERE: goto HERE;
>>    return Halt_Status;
>> }
> 
> So now HHH returns an int result, and you store that result
> in a variable named "Halt_Status".  You haven't said here what
> the meaning of that result might be, and I decline to make any
> assumptions based on what you've called it.  You could rename
> "Halt_Status" to "Foo" and have effectively identical code.
> 
> Previously DDD would "correctly simulate" the function whose address is
> passed to it.  Now it does that and returns an int result.
> 
> If you want to say anything about the meaning of the result returned
> by HHH, feel free to say it.
> 
>> The same thing that applied to DDD equally
>> applies to the more complicated DD.
>>
>> When 1 or more instructions of DD are correctly
>> simulated by HHH the correctly simulated DD
>> cannot possibly get past its call to HHH(DD).
>> Thus DD also never reaches its "return" instruction.
> 
> Now you're talking about simulating "1 or more instructions"
> of DD.  I thought that HHH was supposed to "accurately simulate"
> the function whose argument is passed to it.  Emulating just "1 or
> more instructions" is not accurate simulation.
> 
> If HHH *fully* simulates the execution of DD, then your code above
> exhibits endless recursion, 

In computer science "halting" is not merely stopping running.
"Halting" is reaching a final halt state such as the "return"
instruction.

> which is not particularly interesting,
> and it never reaches the "if (Halt_Status)".  (DD calls HHH, which
> simulates DD; HHH, in simulating DD, must do the equivalent of
> calling HHH, and so on.)
> 

It turns out to be very interesting you merely need
to grok a few details first.

> You've introduced the idea of simulating only some finite number
> of instructions of the simulated functions, but you haven't really
> said how that happens (except perhaps in some x86 code that I
> don't understand).  You've implied that a sufficient knowledge of C
> would let someone understand your arguments, but part of what you're
> saying seems to depend on x86 assembly and/or machine code (which I'm
> not going to learn for the sake of this discussion).
> 
> If I would need to understand x86 code to understand your claims, then
> let's just stop here.
> 
> [SNIP]
> 


-- 
Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer