Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: How do simulating termination analyzers work?
Date: Sat, 28 Jun 2025 14:50:39 +0300
Organization: -
Lines: 154
Message-ID: <103okuf$ra6d$1@dont-email.me>
References: <102sjg5$2k3e9$1@dont-email.me> <1607e7860c899b930b87d371c747708dbeaf1062@i2pn2.org> <102t67r$2o80a$1@dont-email.me> <d2413b15420503b75be7b81f32a96e9a72c251fa@i2pn2.org> <102ugc3$35emj$2@dont-email.me> <vzD4Q.1265580$lZjd.937261@fx05.ams4> <1030bat$3nqlm$1@dont-email.me> <1030cm3$3o34h$2@dont-email.me> <10337ev$lrcj$1@dont-email.me> <103453k$4ms9$6@dont-email.me> <1035vgs$10dm8$1@dont-email.me> <1036qhv$16lpk$4@dont-email.me> <1038gqh$eb9o$1@dont-email.me> <1039l7p$n1od$2@dont-email.me> <103auui$13u7i$1@dont-email.me> <103c0r8$1cme6$3@dont-email.me> <103dp9t$1tq4v$1@dont-email.me> <103eemj$22250$13@dont-email.me> <103g6es$2kbf2$1@dont-email.me> <103h1p3$2q86f$6@dont-email.me> <103j49s$3cq9r$1@dont-email.me> <103n9af$e9sp$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 28 Jun 2025 13:50:39 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="c8d5052e20e3e23be335e6ec8fa34256";
	logging-data="895181"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/j+hsAoRXlVKz/5DpXuey4"
User-Agent: Unison/2.2
Cancel-Lock: sha1:9lkVkT8YHoJLJzr3GlpSVUsR7/s=

On 2025-06-27 23:26:07 +0000, olcott said:

> On 6/26/2025 4:35 AM, Mikko wrote:
>> On 2025-06-25 14:40:35 +0000, olcott said:
>> 
>>> On 6/25/2025 1:54 AM, Mikko wrote:
>>>> On 2025-06-24 15:02:43 +0000, olcott said:
>>>> 
>>>>> On 6/24/2025 3:57 AM, Mikko wrote:
>>>>>> On 2025-06-23 16:53:59 +0000, olcott said:
>>>>>> 
>>>>>>> On 6/23/2025 2:15 AM, Mikko wrote:
>>>>>>>> On 2025-06-22 19:23:37 +0000, olcott said:
>>>>>>>> 
>>>>>>>>> On 6/22/2025 4:02 AM, Mikko wrote:
>>>>>>>>>> On 2025-06-21 17:35:58 +0000, olcott said:
>>>>>>>>>> 
>>>>>>>>>>> On 6/21/2025 4:54 AM, Mikko wrote:
>>>>>>>>>>>> On 2025-06-20 17:17:40 +0000, olcott said:
>>>>>>>>>>>> 
>>>>>>>>>>>>> On 6/20/2025 3:51 AM, Mikko wrote:
>>>>>>>>>>>>>> On 2025-06-19 07:02:27 +0000, olcott said:
>>>>>>>>>>>>>> 
>>>>>>>>>>>>>>> On 6/19/2025 1:39 AM, Mikko wrote:
>>>>>>>>>>>>>>>> On 2025-06-18 18:28:43 +0000, Mr Flibble said:
>>>>>>>>>>>>>>>> 
>>>>>>>>>>>>>>>>> On Wed, 18 Jun 2025 08:53:07 -0500, olcott wrote:
>>>>>>>>>>>>>>>>> 
>>>>>>>>>>>>>>>>>> On 6/18/2025 6:01 AM, Richard Damon wrote:
>>>>>>>>>>>>>>>>>>> On 6/17/25 9:54 PM, olcott wrote:
>>>>>>>>>>>>>>>>>>>> On 6/17/2025 8:19 PM, Richard Damon wrote:
>>>>>>>>>>>>>>>>>>>>> On 6/17/25 4:34 PM, olcott wrote:
>>>>>>>>>>>>>>>>>>>>>> void Infinite_Recursion()
>>>>>>>>>>>>>>>>>>>>>> {
>>>>>>>>>>>>>>>>>>>>>>    Infinite_Recursion();
>>>>>>>>>>>>>>>>>>>>>>    return;
>>>>>>>>>>>>>>>>>>>>>> }
>>>>>>>>>>>>>>>>>>>>>> 
>>>>>>>>>>>>>>>>>>>>>> void Infinite_Loop()
>>>>>>>>>>>>>>>>>>>>>> {
>>>>>>>>>>>>>>>>>>>>>>    HERE: goto HERE; return;
>>>>>>>>>>>>>>>>>>>>>> }
>>>>>>>>>>>>>>>>>>>>>> 
>>>>>>>>>>>>>>>>>>>>>> void DDD()
>>>>>>>>>>>>>>>>>>>>>> {
>>>>>>>>>>>>>>>>>>>>>>    HHH(DDD);
>>>>>>>>>>>>>>>>>>>>>>    return;
>>>>>>>>>>>>>>>>>>>>>> }
>>>>>>>>>>>>>>>>>>>>>> 
>>>>>>>>>>>>>>>>>>>>>> When it is understood that HHH does simulate itself simulating DDD
>>>>>>>>>>>>>>>>>>>>>> then any first year CS student knows that when each of the above are
>>>>>>>>>>>>>>>>>>>>>> correctly simulated by HHH that none of them ever stop running
>>>>>>>>>>>>>>>>>>>>>> unless aborted.
>>>>>>>>>>>>>>>>>>>>> 
>>>>>>>>>>>>>>>>>>>>> WHich means that the code for HHH is part of the input, and thus
>>>>>>>>>>>>>>>>>>>>> there is just ONE HHH in existance at this time.
>>>>>>>>>>>>>>>>>>>>> 
>>>>>>>>>>>>>>>>>>>>> Since that code aborts its simulation to return the answer that you
>>>>>>>>>>>>>>>>>>>>> claim, you are just lying that it did a correct simulation (which in
>>>>>>>>>>>>>>>>>>>>> this context means complete)
>>>>>>>>>>>>>>>>>>>>> 
>>>>>>>>>>>>>>>>>>>>> 
>>>>>>>>>>>>>>>>>>>> *none of them ever stop running unless aborted* *none of them ever
>>>>>>>>>>>>>>>>>>>> stop running unless aborted* *none of them ever stop running unless
>>>>>>>>>>>>>>>>>>>> aborted*
>>>>>>>>>>>>>>>>>>>> 
>>>>>>>>>>>>>>>>>>>> Do you agree or can you refute THIS EXACT POINT?
>>>>>>>>>>>>>>>>>>>> Do you agree or can you refute THIS EXACT POINT?
>>>>>>>>>>>>>>>>>>>> Do you agree or can you refute THIS EXACT POINT?
>>>>>>>>>>>>>>>>>>>> 
>>>>>>>>>>>>>>>>>>>> 
>>>>>>>>>>>>>>>>>>>> 
>>>>>>>>>>>>>>>>>>> How about the fact that if they abort, they never did a correct
>>>>>>>>>>>>>>>>>>> simulation,
>>>>>>>>>>>>>>>>>> 
>>>>>>>>>>>>>>>>>> *You are not addressing THE EXACT POINT*
>>>>>>>>>>>>>>>>>> 
>>>>>>>>>>>>>>>>>> *When HHH never aborts any of the above functions then*
>>>>>>>>>>>>>>>>>> (a) None of the functions ever stops running.
>>>>>>>>>>>>>>>>>> (b) Each of the above functions stops running anyway.
>>>>>>>>>>>>>>>>> 
>>>>>>>>>>>>>>>>> You need to be clear that you are not making a claim about general
>>>>>>>>>>>>>>>>> undecidability but a claim about the SPECIFIC CASE of pathological self
>>>>>>>>>>>>>>>>> reference present in the classic Halting Problem definition .. the trolls
>>>>>>>>>>>>>>>>> here (especially Damon and Mikko) like to ignore that you are doing that.
>>>>>>>>>>>>>>>> 
>>>>>>>>>>>>>>>> He is not doing even that. What he is doing is totally outside of the
>>>>>>>>>>>>>>>> scope of the halting problem. He has already verified that DDD halts
>>>>>>>>>>>>>>>> and that HHH does not report that DDD halts. Nothing else is relevant
>>>>>>>>>>>>>>>> in context of the halting problem.
>>>>>>>>>>>>>>>> 
>>>>>>>>>>>>>>>> If his intent is to deceive he should avoid clarity at least as much
>>>>>>>>>>>>>>>> as he has recently done. His switch from "halting decider" to
>>>>>>>>>>>>>>>> "termination analyzer"
>>>>>>>>>>>>>>> 
>>>>>>>>>>>>>>> is a more accurate term for what I am referring to.
>>>>>>>>>>>>>> 
>>>>>>>>>>>>>> Not really as you are only talking about programs that do not take
>>>>>>>>>>>>>> any input. Termination analysis is about programs that do take input.
>>>>>>>>>>>>> 
>>>>>>>>>>>>> Inputs are typical yet not required.
>>>>>>>>>>>> 
>>>>>>>>>>>> Ability to analyze (at least some) programs that take inputs is
>>>>>>>>>>>> required.
>>>>>>>>>>> 
>>>>>>>>>>> No that is wrong.
>>>>>>>>>> 
>>>>>>>>>> Can you quote any author allowing a termination analyzer that is restricted
>>>>>>>>>> to programs that do not take any input?
>>>>>>>>> 
>>>>>>>>> The ability to correctly determine the halt status
>>>>>>>>> of at least one program that takes no inputs meets
>>>>>>>>> the requirement of being a termination analyzer for
>>>>>>>>> that one program.
>>>>>>>> 
>>>>>>>> It does not prove that all requirements are met, in particular the
>>>>>>>> requirement that the analyzer must be able to analyze programs that
>>>>>>>> do take input.
>>>>>>> 
>>>>>>> That is a bogus requirement.
>>>>>> 
>>>>>> No, it is not. It is essential to the meaning of the term.
>>>>>> A nut cracker is not a hammer although both can produce the same
>>>>>> effenct on nuts.
>>>>>> 
>>>>> 
>>>>> A termination analyzer determines the halt status
>>>>> of a program for every input that this program takes.
>>>>> 
>>>>> When it does this for a program that takes no inputs
>>>>> it is still doing this for every input that this
>>>>> program takes.
>>>> 
>>>> You mean a nutcracker is a hammer?
>>> 
>>> A termination analyzer correctly determines the halt
>>> status of an input program specification for every
>>> input that this program can take. A program specification
>>> taking  zero inputs is merely the simpler case of this
>>> same algorithm.
>> 
>> So you do. Perhapts it is a matter of taste but honest people
>> prefer to call a spade a "spade" and not an "earthmover" or a
>> "manually operated earthmover".
> 
> Every input that a program can take logically includes
> programs that take no inputs.

Yes. But the meaning of "termination analyzer" excludes analyzers
that don't analyze programs that do take inputs.

-- 
Mikko