Path: ...!weretis.net!feeder9.news.weretis.net!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:15:31 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <8903eb12be0c479064db4a0f13dafe89f15bb31e@i2pn2.org>
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>
 <vvk1ha$2ibbd$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:35 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="3792716"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
In-Reply-To: <vvk1ha$2ibbd$1@dont-email.me>
X-Spam-Checker-Version: SpamAssassin 4.0.0
Content-Language: en-US
Bytes: 8819
Lines: 176

On 5/9/25 12:49 AM, olcott wrote:
> 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.

And "Non-Halting" isn't the program being aborted before reaching the 
final state, but never reaching a final state even after an unbounded 
number of instructions have been run.

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

No, it isn't interesting, because it is based on errors. You need to fix 
those errors, at which point you prove a statement you then can't use 
for your next step, as it clearly applies to a different input then your 
actual decider is given.

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