• Re: Halt Status of Halting Problem pathological input correctly determined

    From Mikko@mikko.levanto@iki.fi to comp.theory,sci.logic on Fri Nov 6 10:49:33 2026
    From Newsgroup: sci.logic

    On 02/11/2026 16:14, olcott wrote:
    On 11/2/2026 2:32 AM, Mikko wrote:
    On 29/10/2026 15:05, olcott wrote:
    On 10/29/2026 7:43 AM, Python wrote:
    Le 29/10/2026 |a 09:01, Mikko a |-crit :
    On 28/10/2026 14:31, olcott wrote:
    On 10/28/2026 4:37 AM, Mikko wrote:
    No imput to the halting problem is really pathological. For every >>>>>>> syntactically valid input there is a partial halting decider that >>>>>>> can answer it correctly.

    On 26/10/2026 01:52, olcott wrote:
    typedef int (*ptr)();
    int HHH(ptr P);

    01 int DD()
    02 {
    03-a-a int Halt_Status = HHH(DD);
    04-a-a if (Halt_Status)
    05-a-a-a-a HERE: goto HERE;
    06-a-a return Halt_Status;
    07 }
    08
    09 void main()
    10 {
    11-a HHH(DD);
    12 }

    <MIT Professor Sipser agreed to ONLY these verbatim words
    10/13/2022>
    -a-a-a-a If simulating halt decider H correctly simulates its
    -a-a-a-a input D until H correctly determines that its simulated D >>>>>>>> -a-a-a-a would never stop running unless aborted then

    -a-a-a-a H can abort its simulation of D and correctly report that >>>>>>>> -a-a-a-a D specifies a non-halting sequence of configurations. >>>>>>>> </MIT Professor Sipser agreed to ONLY these verbatim words
    10/13/2022>

    Note that the expression "its simulated D" is ambiguous: it may >>>>>>> either
    mean the original D that the simulation imitates or the imitation >>>>>>> of D
    in the simulation. Fortunately the ambiguity does not matter here as >>>>>>> if one runs forever unless aborted then so does the other.


    It is not ambiguous. It means the original finite string input.

    That is not obvious. You need to clarly specify it means that. You
    also
    must to specify what it means that a finite string would never stop
    unless aborted and what it means that a finite string is aborted, for >>>>> those expressions don't make sense.


    I think your distinction is exactly the important one here.

    Peter says that "its simulated D" means:

    -a-a-a the original finite string input

    but expressions such as:

    -a-a-a runs forever
    -a-a-a halts
    -a-a-a is aborted
    -a-a-a invokes HHH

    are properties of a COMPUTATION, not of the static finite string
    representing that computation.

    His own description immediately switches between the two:

    -a-a-a the static finite string of machine code of DD

    and then:

    -a-a-a simulated DD() invokes simulated HHH(DD)

    The static string invokes nothing. The computation represented by
    that string does.

    This is not merely terminological. It matters to the actual argument.

    I already gave Peter a concrete terminating example with no global
    state:

    -a-a-a typedef void (*fn)(unsigned);

    -a-a-a void F(unsigned);
    -a-a-a void G(unsigned);
    -a-a-a void Done(unsigned);

    -a-a-a void Done(unsigned n)
    -a-a-a {
    -a-a-a-a-a-a-a (void)n;
    -a-a-a }

    -a-a-a void G(unsigned n)
    -a-a-a {
    -a-a-a-a-a-a-a fn next[2] = { F, Done };
    -a-a-a-a-a-a-a fn p = next[n];
    -a-a-a-a-a-a-a p(n + 1);
    -a-a-a }

    -a-a-a void F(unsigned n)
    -a-a-a {
    -a-a-a-a-a-a-a G(n);
    -a-a-a }

    -a-a-a void P(void)
    -a-a-a {
    -a-a-a-a-a-a-a F(0);
    -a-a-a }

    Its execution is simply:

    -a-a-a P
    -a-a-a-a-a -> F(0)
    -a-a-a-a-a -> G(0)
    -a-a-a-a-a -> F(1)
    -a-a-a-a-a -> G(1)
    -a-a-a-a-a -> Done(2)
    -a-a-a-a-a -> return
    -a-a-a-a-a -> return
    -a-a-a-a-a -> ...
    -a-a-a-a-a -> halt

    Thus a finite static string can describe an execution in which
    apparently repeated calls occur while the complete computational
    state changes and the computation eventually halts.

    Peter reported that his HHH returned 0 ("does not halt") on this
    input. When I pointed out that P plainly halts, his response was
    that P was therefore outside HHH's domain.

    So yes: distinguishing the finite representation from the
    computation it represents is not pedantry. It is essential here.

    typedef int (*ptr)();
    int HHH(ptr P);

    01 int DD()
    02 {
    03-a-a int Halt_Status = HHH(DD);
    04-a-a if (Halt_Status)
    05-a-a-a-a HERE: goto HERE;
    06-a-a return Halt_Status;
    07 }
    08
    09 void main()
    10 {
    11-a HHH(DD);
    12 }

    Simulation Trace
    Line 11: main() invokes HHH(DD);

    Simulation invariant
    Line 03: simulated DD() invokes simulated HHH(DD) that simulates DD()
    DD simulated by HHH does not reach its own simulated final state.

    That you just switch the topic instead of telling what you were talking
    about is a good reasont to think that you don't know what you were and
    are talking about.



    I now have a four-way consensus on this
    Python, dbush, dart200, and Mike Terry.
    dbush was most helpful in achieving this
    consensus yesterday.

    DD is to be construed as a finite string of C source code of
    a C function. HHH is to be construed as a C interpreter that
    simulates C source code. HHH can simulate itself simulating
    DD if needed.

    If HHH is intended to take a C source as input it should be
    declared as

    int HHH (char *);
    --
    Mikko
    --- Synchronet 3.22a-Linux NewsLink 1.2