Path: ...!feeds.phibee-telecom.net!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: Linz's proofs and other undecidable decision problems [LP as basis] [Mike Terry]
Date: Sun, 12 May 2024 18:14:58 +0300
Organization: -
Lines: 47
Message-ID: <v1qmdi$2podt$1@dont-email.me>
References: <877cj0g0bw.fsf@bsb.me.uk> <uromc0$5stj$1@dont-email.me> <uroob5$6c32$1@dont-email.me> <urpn7p$fetm$3@dont-email.me> <urq96s$m03b$9@dont-email.me> <urqmeg$p5i6$1@dont-email.me> <urqmv9$p6un$1@dont-email.me> <c2c69a25eecce5dc88cc3a979ee5cf9e4af2b67f.camel@gmail.com> <urqqo0$q1gd$1@dont-email.me> <94aaf99a4347e3fce0773fdd12001c3f03e3c1ea.camel@gmail.com> <urqrlk$q7ed$1@dont-email.me> <65a324cfb867c0219344ca9a767846930119784c.camel@gmail.com> <urqsr6$qgjj$1@dont-email.me> <urqviq$qrnj$2@dont-email.me> <a24a41a5fd0631d7dcca11af5bdc9819e3812cc7.camel@gmail.com> <urr0g7$r6eq$1@dont-email.me> <urregj$cbpo$2@i2pn2.org> <urrirc$12055$3@dont-email.me> <urrkup$cbpo$7@i2pn2.org> <urrrnf$13jnk$1@dont-email.me> <ROKdnSw4i6cUjn_4nZ2dnZfqn_udnZ2d@brightview.co.uk> <urt4qb$1bs5i$3@dont-email.me> <rLmcnQQ3-N_tvH_4nZ2dnZfqnPGdnZ2d@brightview.co.uk> <v1loa5$1g957$1@dont-email.me> <v1n8jr$1u6so$1@dont-email.me> <v1o526$245mu$1@dont-email.me> <v1qj2t$2ouob$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sun, 12 May 2024 17:14:58 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="5f81e78c20829fd69162fd8fa1b8dfc6";
	logging-data="2941373"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/Fw2UgmEITawZaLVD3WyZl"
User-Agent: Unison/2.2
Cancel-Lock: sha1:ELrpYAjlWLzdNNfQqEEGke8+pDo=
Bytes: 3677

On 2024-05-12 14:18:05 +0000, olcott said:

> On 5/12/2024 2:47 AM, Mikko wrote:
>> On 2024-05-11 16:06:29 +0000, olcott said:
>> 
>>> On 5/11/2024 3:00 AM, Mikko wrote:
>>>> On 2024-05-10 18:16:37 +0000, olcott said:
>>>> 
>>>>> On 3/1/2024 12:41 PM, Mike Terry wrote:
>>>> 
>>>>>> Obviously a simulator has access to the internal state (tape contents 
>>>>>> etc.) of the simulated machine.  No problem there.
>>>>>> 
>>>>>> What isn't allowed is the simulated machine altering its own behaviour 
>>>>>> by accessing data outside of its own state.  (I.e. accessing data from 
>>>>>> its parent simulators state.)
>>>>>> 
>>>>>> While an "active-simulator" [my own term] is at liberty to combine
>>>>>> straight simulation with add-on "enhancements" that extend the
>>>>>> functionality of the simulated machine, in doing so it would no
>>>>>> longer be a simulator in the sense you need it to be.  So you
>>>>>> mustn't do this!
>>>> 
>>>> In principle an incorrect simulation is permissible. However, to prove
>>>> that the result inferred from an incorrect simulation is correct may
>>>> be impossible.
>>>> 
>>> 
>>> Within the conventional terms-of-the-art of {termination analyzer}
>>> and {simulator} an incorrect simulation is forbidden.
>> 
>> The conventional meaning of "termination analyzer" does not prohibit
>> incorrect simulation.
> 
> If it does not correctly determine termination then it is not
> a termination analyzer.

That is not always required. IT is often considered sufficent that
the analyzer does not determine incorrectly. To not determine at
all is often considered acceptable.

An incorrect simulation as a part of the algorithm is acceptable
as long as the result about termination is correct.

-- 
Mikko