Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: dbush <dbush.mobile@gmail.com>
Newsgroups: comp.theory
Subject: Re: My reviewers think that halt deciders must report on the behavior
 of their caller
Date: Wed, 4 Jun 2025 23:41:01 -0400
Organization: A noiseless patient Spider
Lines: 89
Message-ID: <101r3kd$15d1h$8@dont-email.me>
References: <101nq32$99vd$1@dont-email.me> <101or6b$maj5$1@dont-email.me>
 <101pq02$ta6v$4@dont-email.me>
 <15abd00ec5b1e4a13892e85ee6ace9ac10d92c56@i2pn2.org>
 <101qu8f$15bg8$3@dont-email.me> <101qugc$15d1h$3@dont-email.me>
 <101r0au$15bg8$7@dont-email.me> <101r10f$15d1h$6@dont-email.me>
 <101r355$1adut$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Thu, 05 Jun 2025 05:41:02 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="0260837afa1e5d49ba06ebc772534096";
	logging-data="1225777"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18IEB2tzbn3vpsVC42tzv3w"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:AKK81iP+jNbHi4iYJG+Ti77hLnU=
In-Reply-To: <101r355$1adut$2@dont-email.me>
Content-Language: en-US

On 6/4/2025 11:32 PM, olcott wrote:
> On 6/4/2025 9:56 PM, dbush wrote:
>> On 6/4/2025 10:44 PM, olcott wrote:
>>> On 6/4/2025 9:13 PM, dbush wrote:
>>>> On 6/4/2025 10:09 PM, olcott wrote:
>>>>> On 6/4/2025 8:43 PM, Richard Damon wrote:
>>>>>> On 6/4/25 11:50 AM, olcott wrote:
>>>>>>> On 6/4/2025 2:04 AM, Mikko wrote:
>>>>>>>> On 2025-06-03 21:39:46 +0000, olcott said:
>>>>>>>>
>>>>>>>>> They all say that HHH must report on the behavior of
>>>>>>>>> direct execution of DDD()
>>>>>>>>
>>>>>>>> No, they don't say that. A halting decider (and a partial halting
>>>>>>>> decider when it reports) must report whether the direct execution
>>>>>>>> of the computation asked about terminates. Unless that computation
>>>>>>>> happens to be DDD() it must report about another behaviour instead
>>>>>>>> of DDD().
>>>>>>>>
>>>>>>>>> yet never bother to notice that the directly executed DDD() is
>>>>>>>>> the caller of HHH(DDD).
>>>>>>>>
>>>>>>>> To say that nobody has noticed that is a lie. Perhaps they have not
>>>>>>>> mentioned what is irrelevant to whatever they said. In particular,
>>>>>>>> whether DDD() calls HHH(DDD) is irrelevant to the requirement that
>>>>>>>> a halting decider must report about a direct exection of the
>>>>>>>> computation the input specifies.
>>>>>>>>
>>>>>>>
>>>>>>> *People have ignored this for 90 years*
>>>>>>> *People have ignored this for 90 years*
>>>>>>> *People have ignored this for 90 years*
>>>>>>>
>>>>>>> The only possible way that HHH can report on the
>>>>>>> direct execution of DDD() is for HHH to report on
>>>>>>> the behavior of its caller:
>>>>>>
>>>>>> So?
>>>>>>
>>>>>> It *IS* a fact that to be correct, it needs to answer about the 
>>>>>> direct executiom of the program that input represents.
>>>>>>
>>>>>> That is DEFINITION.
>>>>>>
>>>>>
>>>>> Likewise with the definition of Russell's Paradox
>>>>> until ZFC showed that this definition is complete
>>>>> nonsense.
>>>>>
>>>>
>>>> But unlike Russel's Paradox, which showed a contradiction in the 
>>>> axioms of naive set theory, there is no contradiction in the axioms 
>>>> of computation theory.  It follows from those axioms that no H 
>>>> exists that performs the below mapping, as you have *explicitly* 
>>>> agreed.
>>>>
>>>
>>> int main()
>>> {
>>>    DDD(); // comp theory does not allow HHH to
>>> }        // report on the behavior of its caller.
>>>
>>
>>
>> int main()
>> {
>>     DDD();     // this
>>     HHH(DDD);  // is not the caller of this: this is }              // 
>> asking what the above will do
> 
> That is just not the way that computation actually works.

Sure it is.  We don't care how the mapping is generated, only that it is 
generated.

// domain: integers from 1 to 3
int sum_1_to_3(int x, int y)
{
    int a[3][3] = {
       {2, 3, 4},
       {3, 4, 5},
       {4, 5, 6}
    };
    return a[x-1][y-1];
}

The above function correctly computes the sum of all integers between 1 
and 3.