• C description as a Turing Machine

    From wij@wyniijj5@gmail.com to comp.lang.c on Fri Sep 12 00:54:48 2025
    From Newsgroup: comp.lang.c

    I have a passage of text on the topic "C description as a Turing Machine".
    Note that by Church-Turing Thesis which is likely correct, C description is more expressive than any other formal languages used in math/logic (e.g. if  Peano Theorem were defined in procedural language, it will be better than it
    is now and have profound effect).
    'Polically', C can beat other language by its nature of being colser to TM. Particularly, C is also applicable in theoretical reasoning, as long as C's definition can be precise enough in an abstract TM (but surely not need to confine itself to 'only TM').
    +-----------------------------------+
    | C description as a Turing Machine |
    +-----------------------------------+
    Definition of the TM for treating a piece of C/Assembly description as a classic TM. (other high level programming languages should also work in the repect that they are some restricted form of TM language)
    From classic definition of TM, we need to re-define:
    Tape::= Registers + flags + read-writable working space + stack (all these may contain
    initial data)
    Transition function::= Readonly program (machine codes)
    Initial state::= User define (usually referring to a function call)
    Set of final state::= User define (usually the 'ret' instrunction of a 'TM'
    function.
    'Halt' in classic TM should mean "states that no transition is defined".
    But in modern computers, this definition is nearly unworkable.
    On CPU machines, halt may be defined the value that Program Counter(PC)
    matches specific values (may include the pointed instruction is executed),
    and implicitly including the conditon when invalid instruction is
    encountered. Once the condition is met, end of the 'TM' definition.

    .thread/process: Not part of a TM. There is uncertainty from like timing
    issues,... (except cooperative thread).
    .Signal(interrupt): Not part of a TM. TM has no capability accessing
    information not specifed, and timing issues.
    .longjmp(..): Fine.
    .exit(int): Depends. If the TM means the whole executable, exit(int) may be fine.
    ...
    .In general, all underlying function calls and data are part of the Transition
    function and the Tape.
    Example: A Halting Problem proof.

    extern int HHH(void (*)()); // Assume HHH is a TM (halt decider)
    void DD() {
    if(HHH(DD)) while(1);
    }
    int main() {
    HHH(DD); // begins a TM
    }
    This example of C description may be interpreted in some model to work but not while assuming HHH is
    a TM. Because DD must be considered as data in the tape,
    which implies along with the contained 'HHH(DD)' are all data which may involve
    encoding. Thus, DD (being non-real TM) never halts (including the HHH inside
    DD) but analyzed to halt or not.
    -------------------------
    Anything I missed in the description and idea?
    --- Synchronet 3.21a-Linux NewsLink 1.2