Path: news.eternal-september.org!eternal-september.org!feeder3.eternal-september.org!news.quux.org!news.nk.ca!rocksolid2!i2pn2.org!.POSTED!not-for-mail
From: Richard Damon <richard@damon-family.org>
Newsgroups: comp.theory
Subject: Re: Incorrect requirements --- Computing the mapping from the input
 to HHH(DD)
Date: Fri, 9 May 2025 07:21:09 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <1ffb883a3b414946707ff9cd9e09dcde21948764@i2pn2.org>
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> <87frhebbae.fsf@nosuchdomain.example.com>
 <vvk520$2j56g$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 9 May 2025 11:25:37 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="3792716"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
Content-Language: en-US
In-Reply-To: <vvk520$2j56g$1@dont-email.me>
X-Spam-Checker-Version: SpamAssassin 4.0.0

On 5/9/25 1:49 AM, olcott wrote:
> On 5/9/2025 12:31 AM, Keith Thompson wrote:
>> 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.
> 
> The "return" instruction marks the final halt state.

Which just shows that you are not reading what he is saying.

> The actual basis for halting: Reaching a Final Halt State
> The halting problem proofs have very specific specific parameters.

Which points out that you are not talking about the C language, but are 
just trying to abuse that connection.

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