Sujet : Re: Hypothetical possibilities --- Sipser approved criteria
De : polcott333 (at) *nospam* gmail.com (olcott)
Groupes : comp.theoryDate : 27. Jul 2024, 15:59:34
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <v8320m$3e9sa$1@dont-email.me>
References : 1 2 3 4 5 6 7 8 9 10 11 12
User-Agent : Mozilla Thunderbird
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>
-- Copyright 2024 Olcott "Talent hits a target no one else can hit; Geniushits a target no one else can see." Arthur Schopenhauer