1. Forum
  2. Fidonet
  3. COMP.LANG.C++

  • Re: Church-Turing and computable functions --- keeps simulating

    From olcott@3:633/10 to All on Tue Oct 27 14:01:18 2026
    On 10/23/2026 3:54 AM, Python wrote:
    *keeps repeating unless aborted*
    Line 03: simulated DD() invokes simulated HHH(DD) that simulates DD()

    *Simulation invariant*
    DD correctly simulated by HHH cannot possibly reach its
    simulated final state.

    Your own answer to A or B:

    On 10/9/2026 6:53 AM, Python wrote:
    You have established that correct application of the C operational
    semantics within HHH produces the recursively simulated sequence:

    ÿÿÿ HHH simulates DD
    ÿÿÿÿÿÿÿ -> DD calls HHH(DD)
    ÿÿÿÿÿÿÿÿÿÿÿ -> HHH simulates DD
    ÿÿÿÿÿÿÿÿÿÿÿÿÿÿÿ -> ...

    Agreed.

    Peter, I understand perfectly well what I agreed to.

    I agreed that IF HHH keeps recursively simulating the HHH call
    encountered at DD line 03, then we obtain:

    ÿÿ HHH -> DD -> HHH -> DD -> ...

    and that recursive simulation does not naturally return.

    There are other statements that are semantically entailed by that.
    "does not naturally return" only seems to have one meaning and that
    meaning excludes "does naturally return".

    A halt decider is only evaluating "does naturally return" versus
    "does not naturally return".

    01 int DD()
    02 {
    03 int Halt_Status = HHH(DD);
    04 if (Halt_Status)
    05 HERE: goto HERE;
    06 return Halt_Status;
    07 }



    --
    Copyright 2026 Olcott

    Axiom 1 --- Paraphrase of Emil Post definition of computation
    All computations are equivalent to the application of finite
    string transformation rules to finite string inputs to derive
    any and all outputs.

    Axiom 2
    Deciders must apply finite string transformation inference
    steps to their finite string inputs that are relevant to the
    decision criteria and make their decision on this basis.

    *Succinct refutation of the Halting Theorem* https://github.com/plolcott/x86utm/blob/master/README.md


    The essence of computation is applying finite
    string transformations to finite string inputs
    to derive outputs. // paraphrase of Emil Post

    My 28 year goal has been to make
    "true on the basis of meaning expressed in language"
    reliably computable for the entire body of general 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* Ex