Path: ...!weretis.net!feeder9.news.weretis.net!news.quux.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Keith Thompson <Keith.S.Thompson+u@gmail.com>
Newsgroups: comp.theory
Subject: Re: Incorrect requirements --- Computing the mapping from the input to HHH(DD)
Date: Thu, 08 May 2025 22:31:05 -0700
Organization: None to speak of
Lines: 176
Message-ID: <87frhebbae.fsf@nosuchdomain.example.com>
References: <vv97ft$3fg66$1@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>
	<vvk1ha$2ibbd$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Date: Fri, 09 May 2025 07:31:06 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="302a6dd640940106301f9e87fdade96e";
	logging-data="2680540"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19eqlqiN9CYaFYzkIzuoNeA"
User-Agent: Gnus/5.13 (Gnus v5.13)
Cancel-Lock: sha1:jOFs4UuoPkbI1LGtYlVWKd2YX1o=
	sha1:n91F4xIqGk00TGlNb+eyis/tYs0=
Bytes: 9161

olcott <polcott333@gmail.com> writes:

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

I fail to see either the truth or the relevance of that statement.

We weren't even talking about halting.  You did use the C identifier
"Halt_Status", but I already told you that the spelling of an
identifier implies nothing about its meaning.  I said that you
hadn't said anything about the meaning of Halt_Status.  You declined
to explain.

You continue to use the term "return instruction".  There is no such
thing in C.  There is a return *statement*.  Do you have some reason to
insist on using incorrect terminology?

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

It's unlikely I'll continue paying attention long enough for it to get
interesting.

>> 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.
========== REMAINDER OF ARTICLE TRUNCATED ==========