1. Forum
  2. Newsgroups
  3. comp.theory

  • The truth about the halting problem counter-example input

    From olcott@polcott333@gmail.com to sci.logic,comp.theory,comp.ai.philosophy,sci.math on Fri Jul 3 22:11:10 2026
    From Newsgroup: comp.theory

    On 7/3/2026 9:43 PM, dbush wrote:
    On 7/3/2026 10:37 PM, olcott wrote:
    On 7/3/2026 9:19 PM, dbush wrote:
    On 7/3/2026 10:05 PM, olcott wrote:
    On 7/3/2026 8:58 PM, dbush wrote:
    On 7/3/2026 9:52 PM, olcott wrote:
    On 7/3/2026 5:51 PM, André G. Isaak wrote:
    On 2026-07-03 16:37, olcott wrote:
    On 7/3/2026 1:47 PM, André G. Isaak wrote:
    On 2026-07-03 12:36, olcott wrote:
    On 7/3/2026 1:18 PM, dbush wrote:

    If an algorithm takes an input and produces an output, that >>>>>>>>>>> is by definition a mapping.
    That only proves that the definition is incoherent.
    The coherent way that it actually works is that
    inputs are transformed into outputs by applying
    finite string transformation rules to inputs to
    derive outputs.

    Apparently you don't understand the difference between a
    mapping and an algorithm. They are two different things.

    André


    A function that ignores its input and only returns 0
    is not any sort of halt function.

    He was defining 'mapping', not 'halt function'.

    André


    A actual halt function must compute
    The mathematical halting function:


    When you actually implement this concretely

    We find that it is not possible, as Linz and others have proved.


    Impossible requirements are incorrect requirements.


    Nope.  Requirements are requirements for a reason.  If they can't be satisfied, then that's just the way it is.


    The halting problem requires a decider that correctly reports the halt
    status of an input that does the opposite of whatever it reports. The
    meaning of these words prove that is logically impossible.

    I would like to have a single algorithm that can tell me whether any arbitrary algorithm with a given input will halt when executed directly,
    but unfortunately no such algorithm exists.

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

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

    HHH is not accountable to report on the
    behavior of its caller on line 11.

    HHH does correctly report on the behavior
    that its input specifies of its on line 12. https://github.com/plolcott/x86utm/blob/master/Halt7.c
    --
    Copyright 2026 Olcott

    My 28 year goal has been to make
    "true on the basis of meaning expressed in language"
    reliably computable for the entire body of knowledge.
    The complete structure of this system is now defined.

    The entire body of knowledge expressed in language is
    comprised of two types of relations between finite strings:
    (a) *Axioms* Expressions of language that are stipulated to be true.

    My system bridges the analytic/synthetic distinction by
    expressly encoding all empirical "atomic facts" in a formal
    language such as CycL of the Cyc project.

    (b) *Inference Rules* Expressions of language that are semantically
    entailed syntactically from (a) and/or (b).
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From dbush@dbush.mobile@gmail.com to sci.logic,comp.theory,comp.ai.philosophy,sci.math on Fri Jul 3 23:23:11 2026
    From Newsgroup: comp.theory

    On 7/3/2026 11:11 PM, olcott wrote:
    On 7/3/2026 9:43 PM, dbush wrote:
    On 7/3/2026 10:37 PM, olcott wrote:
    On 7/3/2026 9:19 PM, dbush wrote:
    On 7/3/2026 10:05 PM, olcott wrote:
    On 7/3/2026 8:58 PM, dbush wrote:
    On 7/3/2026 9:52 PM, olcott wrote:
    On 7/3/2026 5:51 PM, André G. Isaak wrote:
    On 2026-07-03 16:37, olcott wrote:
    On 7/3/2026 1:47 PM, André G. Isaak wrote:
    On 2026-07-03 12:36, olcott wrote:
    On 7/3/2026 1:18 PM, dbush wrote:

    If an algorithm takes an input and produces an output, that >>>>>>>>>>>> is by definition a mapping.
    That only proves that the definition is incoherent.
    The coherent way that it actually works is that
    inputs are transformed into outputs by applying
    finite string transformation rules to inputs to
    derive outputs.

    Apparently you don't understand the difference between a
    mapping and an algorithm. They are two different things.

    André


    A function that ignores its input and only returns 0
    is not any sort of halt function.

    He was defining 'mapping', not 'halt function'.

    André


    A actual halt function must compute
    The mathematical halting function:


    When you actually implement this concretely

    We find that it is not possible, as Linz and others have proved.


    Impossible requirements are incorrect requirements.


    Nope.  Requirements are requirements for a reason.  If they can't be
    satisfied, then that's just the way it is.


    The halting problem requires a decider that correctly reports the halt status of an input that does the opposite of whatever it reports.

    One such example is shown below where algorithm H1 does not correctly
    report the halt status of algorithm D1 which is built using the counter-example template.


    void D(ptr *I)
    {
    // algorithm D1; input: I
    ptr *X = D;
    ptr *Y = I;
    int result;
    {
    // algorithm H1; inputs: X,Y
    result = 0 + (X-X) + (Y-Y);
    }
    if (result == 1) {
    while (1);
    }
    }

    int H(ptr *X, ptr *Y)
    {
    int result;
    {
    // algorithm H1; inputs: X,Y
    result = 0 + (X-X) + (Y-Y);
    }
    return result;
    }


    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Mikko@mikko.levanto@iki.fi to sci.logic,comp.theory,comp.ai.philosophy,sci.math on Sat Jul 4 11:58:25 2026
    From Newsgroup: comp.theory

    On 04/07/2026 06:11, olcott wrote:
    On 7/3/2026 9:43 PM, dbush wrote:
    On 7/3/2026 10:37 PM, olcott wrote:
    On 7/3/2026 9:19 PM, dbush wrote:
    On 7/3/2026 10:05 PM, olcott wrote:
    On 7/3/2026 8:58 PM, dbush wrote:
    On 7/3/2026 9:52 PM, olcott wrote:
    On 7/3/2026 5:51 PM, André G. Isaak wrote:
    On 2026-07-03 16:37, olcott wrote:
    On 7/3/2026 1:47 PM, André G. Isaak wrote:
    On 2026-07-03 12:36, olcott wrote:
    On 7/3/2026 1:18 PM, dbush wrote:

    If an algorithm takes an input and produces an output, that >>>>>>>>>>>> is by definition a mapping.
    That only proves that the definition is incoherent.
    The coherent way that it actually works is that
    inputs are transformed into outputs by applying
    finite string transformation rules to inputs to
    derive outputs.

    Apparently you don't understand the difference between a
    mapping and an algorithm. They are two different things.

    André


    A function that ignores its input and only returns 0
    is not any sort of halt function.

    He was defining 'mapping', not 'halt function'.

    André


    A actual halt function must compute
    The mathematical halting function:


    When you actually implement this concretely

    We find that it is not possible, as Linz and others have proved.


    Impossible requirements are incorrect requirements.


    Nope.  Requirements are requirements for a reason.  If they can't be
    satisfied, then that's just the way it is.


    The halting problem requires a decider that correctly reports the halt status of an input that does the opposite of whatever it reports. The meaning of these words prove that is logically impossible.

    I would like to have a single algorithm that can tell me whether any
    arbitrary algorithm with a given input will halt when executed
    directly, but unfortunately no such algorithm exists.

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

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

    HHH is not accountable to report on the
    behavior of its caller on line 11.

    It is if HHH reagards itself as a part of the input. But HHH is not
    required to interprete the input that way. It could reject the input
    for the undefined symbol HHH.
    --
    Mikko
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From olcott@polcott333@gmail.com to sci.logic,sci.math,comp.theory,sci.math.symbolic,alt.philosophy on Sat Jul 4 12:16:09 2026
    From Newsgroup: comp.theory

    On 7/4/2026 3:58 AM, Mikko wrote:
    On 04/07/2026 06:11, olcott wrote:
    On 7/3/2026 9:43 PM, dbush wrote:
    On 7/3/2026 10:37 PM, olcott wrote:
    On 7/3/2026 9:19 PM, dbush wrote:
    On 7/3/2026 10:05 PM, olcott wrote:
    On 7/3/2026 8:58 PM, dbush wrote:
    On 7/3/2026 9:52 PM, olcott wrote:
    On 7/3/2026 5:51 PM, André G. Isaak wrote:
    On 2026-07-03 16:37, olcott wrote:
    On 7/3/2026 1:47 PM, André G. Isaak wrote:
    On 2026-07-03 12:36, olcott wrote:
    On 7/3/2026 1:18 PM, dbush wrote:

    If an algorithm takes an input and produces an output, that >>>>>>>>>>>>> is by definition a mapping.
    That only proves that the definition is incoherent.
    The coherent way that it actually works is that
    inputs are transformed into outputs by applying
    finite string transformation rules to inputs to
    derive outputs.

    Apparently you don't understand the difference between a >>>>>>>>>>> mapping and an algorithm. They are two different things. >>>>>>>>>>>
    André


    A function that ignores its input and only returns 0
    is not any sort of halt function.

    He was defining 'mapping', not 'halt function'.

    André


    A actual halt function must compute
    The mathematical halting function:


    When you actually implement this concretely

    We find that it is not possible, as Linz and others have proved.


    Impossible requirements are incorrect requirements.


    Nope.  Requirements are requirements for a reason.  If they can't be
    satisfied, then that's just the way it is.


    The halting problem requires a decider that correctly reports the halt
    status of an input that does the opposite of whatever it reports. The
    meaning of these words prove that is logically impossible.

    I would like to have a single algorithm that can tell me whether any
    arbitrary algorithm with a given input will halt when executed
    directly, but unfortunately no such algorithm exists.

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

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

    HHH is not accountable to report on the
    behavior of its caller on line 11.

    It is if HHH reagards itself as a part of the input.

    There is no regarding to it
    HHH is not accountable to report on the
    behavior of its caller on line 11.

    But HHH is not
    required to interprete the input that way. It could reject the input
    for the undefined symbol HHH.


    The only correct way for HHH to process its input
    is as a sequence of inference steps according to the
    operational semantics of C.
    --
    Copyright 2026 Olcott

    My 28 year goal has been to make
    "true on the basis of meaning expressed in language"
    reliably computable for the entire body of knowledge.
    The complete structure of this system is now defined.

    The entire body of knowledge expressed in language is
    comprised of two types of relations between finite strings:
    (a) *Axioms* Expressions of language that are stipulated to be true.

    My system bridges the analytic/synthetic distinction by
    expressly encoding all empirical "atomic facts" in a formal
    language such as CycL of the Cyc project.

    (b) *Inference Rules* Expressions of language that are semantically
    entailed syntactically from (a) and/or (b).
    --- Synchronet 3.22a-Linux NewsLink 1.2