Path: ...!weretis.net!feeder9.news.weretis.net!3.eu.feeder.erje.net!feeder.erje.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: Hypothetical possibilities --- Sipser approved criteria
Date: Sun, 28 Jul 2024 11:21:53 +0300
Organization: -
Lines: 45
Message-ID: <v84v31$3rsds$1@dont-email.me>
References: <v7gl30$3j9fi$1@dont-email.me> <v7led6$kacj$1@dont-email.me> <v7lsg5$luh0$5@dont-email.me> <v7nm9m$1433k$1@dont-email.me> <v7ofe7$17h8r$6@dont-email.me> <v7qfu0$1m6vf$1@dont-email.me> <v7r040$1onhe$3@dont-email.me> <v7vlbj$2ofet$1@dont-email.me> <v80a2u$2rabc$4@dont-email.me> <v825jo$39i9l$1@dont-email.me> <v830vj$3dftr$10@dont-email.me> <v831eq$3c7$2@news.muc.de> <v8320m$3e9sa$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sun, 28 Jul 2024 10:21:53 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="1e2c5978fba8d101c2f8131c12c4214d";
	logging-data="4059580"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX191bAHqI57O8PjggKoefTRN"
User-Agent: Unison/2.2
Cancel-Lock: sha1:tHVhBATQKr6XNwfwQMbNw91PNn4=
Bytes: 3264

On 2024-07-27 14:59:34 +0000, olcott said:

> On 7/27/2024 9:50 AM, Alan Mackenzie wrote:
>> olcott <polcott333@gmail.com> wrote:
>>> On 7/27/2024 1:54 AM, Mikko wrote:
>> 
>>>> If a simulator correctly simulates a finite number of instructions
>>>> where x86 program specifies an execution of an infinite number of
>>>> instructions then the simulation deviates from x86 semantics at the
>>>> point where the simulation stops but the x86 semantics specify
>>>> countinuation.
>> 
>>> I paraphrase this as the requirement for a termination analyzer
>>> to never terminate. That *is* a ridiculously stupid requirement.
>> 
>> I think you would do better to "paraphrase" it that a correct simulator
>> cannot always be a termination analyser.  The two are different things.
>> 
> 
> *When you say if backwards (like that) it makes less sense*
> A correct termination analyzer can always be based on a correct 
> simulator using this criteria:
> 
> <MIT Professor Sipser agreed to ONLY these verbatim words 10/13/2022>
>      If simulating halt decider H correctly simulates its input D
>      until H correctly determines that its simulated D would never
>      stop running unless aborted then
> 
>      H can abort its simulation of D and correctly report that D
>      specifies a non-halting sequence of configurations.
> </MIT Professor Sipser agreed to ONLY these verbatim words 10/13/2022>

The quoted criterion requires a partial simulation that discontinues the
simulation in a situation where the input specifies that the execution
must be continued.

It also requires that the analyzer must be able to determine whithout
simulation whether the unsimulated behaviour ever terminates. In some
cases this is determinable but no analyzer can determine it in all
cases. Your attempt does it right in some cases but gets wrong the
case that many consider the most interesting.

-- 
Mikko