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
  • From Mikko@mikko.levanto@iki.fi to sci.logic,sci.math,comp.theory,sci.math.symbolic,alt.philosophy on Mon Jul 6 11:07:41 2026
    From Newsgroup: comp.theory

    On 04/07/2026 20:16, olcott wrote:
    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.

    Yes, there is. If HHH interpretes the call to HHH as a call
    to itself then it must regard itself as a part of the input.
    Otherwise it must interprete HHH as a call to some function
    other than itself, so it must regard itself as not a part of
    the input. EIther way, it must report correcltly about the
    behaviour as obsservable in an execution of the computation
    specified by the input.

    Of course this is irrelevant to the Turing machine halting problem.
    A Turing machine never calls another Turing machine.
    --
    Mikko
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From olcott@polcott333@gmail.com to sci.logic,comp.theory,sci.math,comp.ai.philosophy on Mon Jul 6 10:18:13 2026
    From Newsgroup: comp.theory

    On 7/6/2026 3:07 AM, Mikko wrote:
    On 04/07/2026 20:16, olcott wrote:
    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.

    Yes, there is. If HHH interpretes the call to HHH as a call

    You did not bother to pay attention to the line number 11.
    The HP stupidly assumes that a halt function must report
    on the behavior its caller. HHH has no access to its caller.

    to itself then it must regard itself as a part of the input.
    Otherwise it must interprete HHH as a call to some function
    other than itself, so it must regard itself as not a part of
    the input. EIther way, it must report correcltly about the
    behaviour as obsservable in an execution of the computation
    specified by the input.

    Of course this is irrelevant to the Turing machine halting problem.
    A Turing machine never calls another Turing machine.

    --
    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 Mikko@mikko.levanto@iki.fi to sci.logic,comp.theory,sci.math,comp.ai.philosophy on Wed Jul 8 10:45:02 2026
    From Newsgroup: comp.theory

    On 06/07/2026 18:18, olcott wrote:
    On 7/6/2026 3:07 AM, Mikko wrote:
    On 04/07/2026 20:16, olcott wrote:
    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.

    Yes, there is. If HHH interpretes the call to HHH as a call

    You did not bother to pay attention to the line number 11.
    The HP stupidly assumes that a halt function must report
    on the behavior its caller. HHH has no access to its caller.

    The HP does not assume anything. It requires.
    --
    Mikko
    --- Synchronet 3.22a-Linux NewsLink 1.2