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 22:13:32 -0400
Organization: A noiseless patient Spider
Lines: 68
Message-ID: <101qugc$15d1h$3@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>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Thu, 05 Jun 2025 04:13:33 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="0260837afa1e5d49ba06ebc772534096";
	logging-data="1225777"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19q8JmsmG9MK77BQEIuyTDa"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:f2cE2THiU9yf7K0ACjLEJYLwzHM=
Content-Language: en-US
In-Reply-To: <101qu8f$15bg8$3@dont-email.me>

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.


On 6/3/2025 10:34 PM, olcott wrote:
 > On 6/3/2025 9:12 PM, dbush wrote:
 >>
 >> Given any algorithm (i.e. a fixed immutable sequence of 
instructions) X described as <X> with input Y:
 >>
 >> A solution to the halting problem is an algorithm H that computes 
the following mapping:
 >>
 >> (<X>,Y) maps to 1 if and only if X(Y) halts when executed directly
 >> (<X>,Y) maps to 0 if and only if X(Y) does not halt when executed 
directly
 >>
 >
 > Yes there is no algorithm that does that