1. Forum
  2. Usenet
  3. COMP.THEORY

  • Re: Hypothetical possibilities --- Sipser approved criteria

    From Alan Mackenzie@21:1/5 to olcott on Sat Jul 27 14:50:02 2024
    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.

    [ .... ]

    --
    Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius
    hits a target no one else can see." Arthur Schopenhauer

    --
    Alan Mackenzie (Nuremberg, Germany).

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Mikko@21:1/5 to olcott on Sun Jul 28 11:13:54 2024
    On 2024-07-27 14:41:54 +0000, olcott said:

    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.

    A more accurate paraphrase would be "Olcott is an idiot". Even that
    would not be really accurate.

    --
    Mikko

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Mikko@21:1/5 to olcott on Sun Jul 28 11:21:53 2024
    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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)