• Re: Michael Sipser of MIT validates the notion of a simulating halt dec

    From olcott@21:1/5 to Keith Thompson on Mon May 12 12:14:03 2025
    XPost: comp.theory

    On 10/12/2022 6:49 PM, Keith Thompson wrote:
    olcott <polcott2@gmail.com> writes:
    On 10/12/2022 5:37 PM, Richard Damon wrote:
    On 10/12/22 11:08 AM, olcott wrote:
    Professor Michael Sipser of MIT said that this verbatim paragraph
    looks correct:

    <quoted email to professor Sipser>
    Here is what I would like to say:

    Professor Michael Sipser of MIT said that this verbatim paragraph
    looks correct:

    If H does correctly determine that its correct simulation
    of D would never stop running unless aborted, would it be
    correct for H to abort this simulation and report that D
    specifies a non-halting sequence of configurations?

    This validates the idea of a simulating halt decider referenced in
    this paper.

    Rebutting the Sipser Halting Problem Proof
    https://www.researchgate.net/publication/364302709_Rebutting_the_Sipser_Halting_Problem_Proof

    Professor Sipser has not had the time to carefully review this paper
    presented to him.
    </quoted email to professor Sipser>

    <quoted reply from professor Sipser>
    Looks ok. Thanks for checking.
    </quoted reply from professor Sipser>

    IF I drop by and ask him face to face, will he confirm this?

    Yes.

    Would Professor Sipser agree that you have refuted his halting problem
    proof?

    If I understand this correctly, it does not support the idea that a
    general "simulating halt decider" can actually exist.

    In the above, let D be a program that may or may not halt, and let H be
    an observer who attempts to determine whether or not D halts.
    Concretely, let D be this C program or equivalent:

    int main(void) { while (1) { } }

    and I'll be H. I can observe D. I can simulate it until I get bored,
    which won't take long (one iteration, two iterations, three iterations, zzzzzzzzz). I can, while simulating it, conclude that it will never
    halt, abort the simulation, and report that it never halts. It wouldn't
    be difficult to automate the process in a way that works for this simple case.


    My scope is to prove that the "impossible"
    input to all the halting problem proofs <is>
    decidable. Refuting the halting problem itself
    has never been in scope.

    int DD()
    {
    int Halt_Status = HHH(DD);
    if (Halt_Status)
    HERE: goto HERE;
    return Halt_Status;
    }

    HHH(DD) does correctly determine that its input DD
    would never stop running unless aborted.

    --
    Copyright 2024 Olcott

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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Mikko@21:1/5 to olcott on Tue May 13 10:46:11 2025
    On 2025-05-12 17:14:03 +0000, olcott said:

    On 10/12/2022 6:49 PM, Keith Thompson wrote:
    olcott <polcott2@gmail.com> writes:
    On 10/12/2022 5:37 PM, Richard Damon wrote:
    On 10/12/22 11:08 AM, olcott wrote:
    Professor Michael Sipser of MIT said that this verbatim paragraph
    looks correct:

    <quoted email to professor Sipser>
    Here is what I would like to say:

    Professor Michael Sipser of MIT said that this verbatim paragraph
    looks correct:

    If H does correctly determine that its correct simulation
    of D would never stop running unless aborted, would it be
    correct for H to abort this simulation and report that D
    specifies a non-halting sequence of configurations?

    This validates the idea of a simulating halt decider referenced in
    this paper.

    Rebutting the Sipser Halting Problem Proof
    https://www.researchgate.net/publication/364302709_Rebutting_the_Sipser_Halting_Problem_Proof


    Professor Sipser has not had the time to carefully review this paper
    presented to him.
    </quoted email to professor Sipser>

    <quoted reply from professor Sipser>
    Looks ok. Thanks for checking.
    </quoted reply from professor Sipser>

    IF I drop by and ask him face to face, will he confirm this?

    Yes.

    Would Professor Sipser agree that you have refuted his halting problem
    proof?

    If I understand this correctly, it does not support the idea that a
    general "simulating halt decider" can actually exist.

    In the above, let D be a program that may or may not halt, and let H be
    an observer who attempts to determine whether or not D halts.
    Concretely, let D be this C program or equivalent:

    int main(void) { while (1) { } }

    and I'll be H. I can observe D. I can simulate it until I get bored,
    which won't take long (one iteration, two iterations, three iterations,
    zzzzzzzzz). I can, while simulating it, conclude that it will never
    halt, abort the simulation, and report that it never halts. It wouldn't
    be difficult to automate the process in a way that works for this simple
    case.


    My scope is to prove that the "impossible"
    input to all the halting problem proofs <is>
    decidable.

    As it is provably impossible it is not possible. The nearest you can hope
    is to construct an oracle that can do what a Turing machine cannot do. It
    would not be easy, just not yet proven imposssible.

    --
    Mikko

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