From 1c64305de4c3c23e321252c9f5af7f0d6332595b Mon Sep 17 00:00:00 2001 From: Thomas Walker Lynch Date: Mon, 27 Jul 2026 10:26:01 +0000 Subject: [PATCH] =?utf8?q?=CE=B4=20is=20a=20function,=20=CE=94=20is=20a=20?= =?utf8?q?set?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- document/book/TM-2026.html | 66 ++++++++++++++++++++------------------ 1 file changed, 34 insertions(+), 32 deletions(-) diff --git a/document/book/TM-2026.html b/document/book/TM-2026.html index a3a583f..6bc6046 100644 --- a/document/book/TM-2026.html +++ b/document/book/TM-2026.html @@ -1,3 +1,5 @@ + + @@ -522,7 +524,7 @@

This shows string reversal to be an O(n^2) complexity problem, which might appear to some to be a peculiar result, as the same problem can be solved in O(n) time with a C program. This justifies further analysis.

-

Reversing a string does not intrinsically require making decisions based on the values in the string that is being reversed; however, a Turing Machine must use the value under the head for the next state transitions. Also, the only memory a controller has is through adding control path branches, so to "carry the symbol right" requires a branch in the state controller to remember what the symbol is. Consequently, had the input alphabet been larger, this controller would have required proportionally more states, as noted on the diagram.

+

Reversing a string does not intrinsically require making decisions based on the values in the string that is being reversed; however, a Turing Machine must use the value under the head for the next state transitions. Also, the only memory a controller has is through adding control path branches, so to "carry the symbol right" requires a branch in the state controller per symbol to remember what the symbol is. Consequently, had the input alphabet been larger, this controller would have required proportionally more states, as noted on the diagram.

For a real machine, symbols are machine word encodings. For example, ASCII uses 7 data bits, so there are 128 symbols available. If the width of the word for encoding symbols is n bits, then the total number of states required for this string reverse machine is:

@@ -613,7 +615,7 @@ The computation theoretic TTCA Machine -

This chapter presents a modified computation theoretic Turing Machine with three structural additions. First, it separates control flow from data flow, ensuring that payload symbols do not needlessly expand the control state machine. Second, it unifies the control and data symbol sets into a single alphabet to natively support explicit communications protocols even in the presence of recursion and self-recursion. Finally, it implements a cascading next-state evaluation hierarchy, permitting the programmer to formally define and handle meta-symbols such as unspecified, and to more conveniently code communication protocols.

+

This chapter presents a modified computation theoretic Turing Machine with three structural additions. First, it separates control flow from data flow, ensuring that payload symbols do not needlessly expand the control state machine. Second, it unifies the control and data symbol sets into a single alphabet to natively support explicit communications protocols even in the presence of recursion and self-recursion. Finally, it implements a cascading next-state evaluation hierarchy, permitting the programmer to formally define and handle meta-symbols such as unspecified, while also making it more convenient to code communication protocols.

The unspecified symbol

@@ -644,15 +646,15 @@

The specific architectural modifications are as follows:

    -
  1. There is one unified alphabet σ to which both status symbols and data symbols belong.
    2. -
  2. It utilizes a Moore-style programmed state controller, so that actions can be managed separately from state transitions.
    3. -
  3. It separates control flow from data flow: +
  4. There is one unified alphabet Σ to which both status symbols and data symbols belong.
    5. +
  5. The machine utilizes a Moore-style programmed state controller, so that actions can be managed separately from state transitions.
    6. +
  6. The machine separates control flow from data flow:
      -
    1. Two registers exist within the machine: one for holding a symbol upon which control decisions are made, the s (status) register; and one for holding data upon which decisions are not based, the d (data) register. Here, s stands for 'status', as its value is a condition flag utilized by the programmed controller when determining the next state, while d stands for 'data'.
      2. -
    2. Read and write actions accept an operand designating the target or source register respectively, either s or d.
      3. +
    3. Two registers exist within the machine: one for holding a symbol upon which control decisions are made, the s (status) register; and one for holding data upon which decisions are not based, the d (data) register. Here, s stands for 'status', while d stands for 'data'.
      4. +
    4. Write and read actions are given an operand designating the target or source register respectively, either s or d.
    7. -
  7. It implements default state transitions that execute when no explicit transition is given in the main state transition table of triples (each triple being \langle S_i, σ, S_{i+1} \rangle): +
  8. The machine implements default state transitions that execute when no explicit transition is given in the main state transition table of triples (each triple being \langle S_i, σ, S_{i+1} \rangle):
    1. state-specific transition default pairs, which have the form \langle S_i, S_{i+1} \rangle
    2. status-specific transition default pairs, which have the form \langle σ, S_{i+1} \rangle
      3. @@ -663,15 +665,15 @@

      The new machine evaluates next-state transitions through these four layers, in order, progressing to the next layer only when no transition is found in the prior layer:

        -
      1. Conditional (δ_0): Selects the transition rule that matches the current state and the value of the status register.
        2. -
      2. State Default (δ_1): If no conditional next state rule is found, selects the default transition rule that matches the current state.
        3. -
      3. Status Default (δ_2): If no next state rule has been found, selects the default transition rule that matches the current machine status.
        4. -
      4. Global Default (δ_3): An unconditional transition of last resort if no prior layer provides a valid next state.
        5. +
      5. Conditional (Δ_0): Selects the transition rule that matches the current state and the value of the status register.
        6. +
      6. State Default (Δ_1): If no conditional next state rule is found, selects the default transition rule that matches the current state.
        7. +
      7. Status Default (Δ_2): If no next state rule has been found, selects the default transition rule that matches the current machine status.
        8. +
      8. Global Default (Δ_3): An unconditional transition of last resort if no prior layer provides a valid next state.
      -

      Programmers will typically use the Global Default arc, δ_3, to take the machine to an error state when they have mistakenly left the next state transition undefined. However, it is conceivable for some machines that if no other next state is defined, there is a single logical state that should be visited, and this condition is not an error. If no Global Default arc is specified, and no next state is found, the machine hangs.

      +

      Programmers will typically use the Global Default arc, Δ_3, to take the machine to an error state when they have mistakenly left the next state transition undefined. However, it is conceivable for some machines that if no other next state is defined, there is a single logical state that should be visited, and this condition is not an error. If no Global Default arc is specified, and no next state is found, the machine hangs.

      -

      This approach of cascading next-state decisions does more than merely make the machine more convenient to program; it also enables a programmer to support an unspecified symbol. For example, a programmer can incorporate a first-order unspecified symbol by first adding it to the alphabet σ, adding a Q_unspecified state to Q, and then adding a status default arc to δ_2 of \langle \mathtt{s{\cdot}unspecified}, \mathrm{Q\_unspecified} \rangle. Finally, the programmer adds Q_unspecified to the set of halting states. Then, if the machine attempts to make a decision upon the unspecified symbol, the machine will transition to the Q_unspecified state and halt. Such a machine can then be analyzed to see if it ever visits the Q_unspecified state.

      +

      This approach of cascading next-state decisions does more than merely make the machine more convenient to program; it also enables a programmer to support an unspecified symbol. For example, a programmer can incorporate a first-order unspecified symbol by first adding it to the alphabet Σ, adding a Q_unspecified state to Q, and then adding a status default arc to Δ_2 of \langle \mathtt{s{\cdot}unspecified}, \mathrm{Q\_unspecified} \rangle. Finally, the programmer adds Q_unspecified to the set of halting states. Then, if the machine attempts to make a decision upon the unspecified symbol, the machine will transition to the Q_unspecified state and halt. Such a machine can then be analyzed to see if it ever visits the Q_unspecified state, although the analyst must take care, because if he puts some thought into this, he will realize that no such universal analyzer can exist.

      The formal definition that follows will be partitioned according to the separation of concerns. The first section defines the fixed parts of the Turing Machine definition. The second section defines the memory elements (variables). The third section describes the programmable components, which vary between specific Turing Machines depending on their purposes.

      @@ -681,7 +683,7 @@

      The TTCA Machine fixed part

      - \mathrm{MF} = (\mathrm{QF}, \mathrm{σ F}, \mathrm{AF}) + \mathrm{MF} = (\mathrm{QF}, \mathrm{ΣF}, \mathrm{AF})

      In the following, the middle dot acts as a namespace operator, N{\cdot}x. By doing this we assure there will be no aliasing with the symbols provided by the programmer when he defines a programmed state controller.

      @@ -708,11 +710,11 @@ \end{aligned} -

      where σ must be in σ.

      +

      where σ must be in Σ.

      The set of predefined symbols:

      - \mathrm{σ F} = \{\mathrm{σ F}{\cdot}\mathtt{leftmost}\} + \mathrm{ΣF} = \{\mathrm{ΣF}{\cdot}\mathtt{leftmost}\}

      Machine variables

      @@ -734,7 +736,7 @@
      - \mathrm{MP} = (\mathrm{QP}, \mathrm{ΣP}, \lambda\mathrm{P}, δ_0, δ_1, δ_2, δ_3, \mathrm{HP}) + \mathrm{MP} = (\mathrm{QP}, \mathrm{ΣP}, \lambda\mathrm{P}, Δ_0, Δ_1, Δ_2, Δ_3, \mathrm{HP})
      @@ -757,25 +759,25 @@

      The conditional transition table. A set of state transition triples; each triple is of the form:

      - δ_0 = \{ \langle q_i, σ, q_{i+1} \rangle, \dots \} + Δ_0 = \{ \langle q_i, σ, q_{i+1} \rangle, \dots \}

      Here q_i and q_{i+1} are two states from the total set of Q. They need not be distinct. While the machine is running, state q_i is to be matched against the contents of the q register, the current state. Symbol σ is a member of the total set Σ and is to be matched against the contents of the s register, the machine status. When q_i matches the current state and σ matches the current status, then q_{i+1} becomes the next state.

      The state default transition table. A set of state transition pairs; each pair is of the form:

      - δ_1 = \{ \langle q_i, q_{i+1} \rangle, \dots \} + Δ_1 = \{ \langle q_i, q_{i+1} \rangle, \dots \}

      where q_i is matched to the current state, and upon a match q_{i+1} will be taken as the next state.

      The status default transition table. A set of state transition pairs; each pair is of the form:

      - δ_2 = \{ \langle σ, q_{i+1} \rangle, \dots \} + Δ_2 = \{ \langle σ, q_{i+1} \rangle, \dots \}

      where r{\cdot}σ matches the symbol in register r (either d or s), and upon a match q_{i+1} will be taken as the next state.

      The global default next state:

      - δ_3 = q_{i+1} + Δ_3 = q_{i+1}

      This is the transition of last resort. It is unconditional; the next state becomes q_{i+1}.

      @@ -788,7 +790,7 @@
      - M = (q, s, d, Q, Σ, \mathrm{AF}, \lambda\mathrm{P}, δ, \mathrm{HP}) + M = (q, s, d, Q, Σ, \mathrm{AF}, \lambda\mathrm{P}, Δ, \mathrm{HP})
      @@ -804,7 +806,7 @@

      The ordered sequence of next state transition rules:

      - δ = [δ_0 \mid δ_1 \mid δ_2 \mid δ_3] + Δ = [Δ_0 \mid Δ_1 \mid Δ_2 \mid Δ_3]

      Computation theoretic TTCA Machine executor

      @@ -829,12 +831,12 @@

    Phase 2: The state transition

    -

    Following the completion of the action, the executor evaluates the next state by cascading through the ordered sequence of transition rules δ = [δF_0 | δ_1 | δ_2 | δ_3]. The evaluation follows this hierarchy, stopping and branching at the first valid match:

    +

    Following the completion of the action, the executor evaluates the next state by cascading through the ordered sequence of transition rules Δ = [ΔF_0 | Δ_1 | Δ_2 | Δ_3]. The evaluation follows this hierarchy, stopping and branching at the first valid match:

      -
    1. Evaluate δF_0: Inspect the gate register g. If it holds the ΣF{·}\mathtt{unspecified} symbol, the next state becomes QF{·}\mathtt{unspecified\_decision}. This halts standard programmed execution.
      2. -
    2. Evaluate δ_1: Search the programmed conditional rules for a triple that matches the current state q and the exact symbol currently held in the gate register g. If a match is found, the next state updates to the specified q_1.
      3. -
    3. Evaluate δ_2: If no conditional rule matches, search the programmed default rules for a pair matching the current state q. If a match is found, the next state updates to the specified q_1.
      4. -
    4. Evaluate δ_3: If all prior evaluations fail to yield a match, unconditionally update the next state to the global fallback transition specified by δ_3.
      5. +
    5. Evaluate ΔF_0: Inspect the gate register g. If it holds the ΣF{·}\mathtt{unspecified} symbol, the next state becomes QF{·}\mathtt{unspecified\_decision}. This halts standard programmed execution.
      6. +
    6. Evaluate Δ_1: Search the programmed conditional rules for a triple that matches the current state q and the exact symbol currently held in the gate register g. If a match is found, the next state updates to the specified q_1.
      7. +
    7. Evaluate Δ_2: If no conditional rule matches, search the programmed default rules for a pair matching the current state q. If a match is found, the next state updates to the specified q_1.
      8. +
    8. Evaluate Δ_3: If all prior evaluations fail to yield a match, unconditionally update the next state to the global fallback transition specified by Δ_3.

    Halting stage

    @@ -3476,7 +3478,7 @@ Now suppose defining a Turing Machine that initially has the head on the leftmos fixed procedure for using these -

    In our original Turing Machine model, the controlling state machine commands were limited to, do-nothing, left, right, write, with reading as an implied command. To this list we add append. The append command may only be called when the head is on the rightmost tape cell. This is not limiting because the command may be called from a state that is at the end of an arc triggered by the right from rightmost error. When we have no empty-symbol, append accepts an alphabet symbol and performs a write into the new cell. This is not limiting because if need be, a person can always perform an extraneous write of an alphabet symbol.

    +

    In our original Turing Machine model, the controlling state machine commands were limited to, do-nothing, left, right, write, with reading as an implied command. To this list we add append. The append command may only be called when the head is on the rightmost tape cell. This is not limiting because the command may be called from a state that is at the end of an arc triggered by the right from rightmost error. When we have no empty-symbol, append is given an alphabet symbol and performs a write into the new cell. This is not limiting because if need be, a person can always perform an extraneous write of an alphabet symbol.

    With this extendable tape model all Turing Machine components remain finite during computation, though some are arbitrarily large. This variation is more suited for creating a mapping between a Turing Machine and a real program running on a real machine. Specifically, a computation requiring N cells maps exactly to a physical machine possessing at least N cells. The theoretical model and the physical implementation remain perfectly isomorphic provided the physical environment does not exhaust its memory bounds. Because a computational TTCA machine demands strictly finite tape extensions, a physical machine that completes the execution maintains exact structural correspondence. This isomorphism holds continuously as long as memory remains available, even accommodating dynamic hardware expansion such as memory hot-swapping. The theoretical correspondence fails solely upon a hard physical limit being reached during execution.

    @@ -3676,7 +3678,7 @@ Now suppose defining a Turing Machine that initially has the head on the leftmos

    The Turing Machine, and our variation of it, may be partitioned into two parts. One part of the part consists of the tape head and the tape. We call this the Tape Transport Unit, as that is the name used for the mechanism that does this work on real tape storage units. The other part of the part is the Controller.

    -

    The Tape Transport Unit accepts commands for reading, writing, and moving the head. (In real Tape Transport Units the head is in a fixed position and we move the tape, but the relative affect is the same.) Our modified model adds commands for extending the tape. During normal operation these commands only come from the controller.

    +

    The Tape Transport Unit is given commands for reading, writing, and moving the head. (In real Tape Transport Units the head is in a fixed position and we move the tape, but the relative affect is the same.) Our modified model adds commands for extending the tape. During normal operation these commands only come from the controller.

    We have two types of controllers. One type of controller is a state machine. Its design is an integral part of the Turing Machine. To step the Turing Machine means to step this state machine to its next state. The state machine definition exists before the Turing Machine takes its first step, and its definition remains intact for as long as said Turing Machine exists.

    @@ -3848,7 +3850,7 @@ Now suppose defining a Turing Machine that initially has the head on the leftmos

    The first f is in the parameter list of the function definition, so it is taken as a variable name. In contrast the f in the body is at the head of an evaluated list, so it is taken as a function name. Hence there is a disconnect, and we get error messages describing this disconnect.

    -

    The Lisp operator #' indicates that the symbol that follows is a function name to be taken literally, and not a variable name. This gets our function name into the data space for use as an argument. The Lisp function funcall accepts as a first argument the name of a function to be called, while the remaining arguments are passed through to said function as its arguments:

    +

    The Lisp operator #' indicates that the symbol that follows is a function name to be taken literally, and not a variable name. This gets our function name into the data space for use as an argument. The Lisp function funcall is given as a first argument the name of a function to be called, while the remaining arguments are passed through to said function as its arguments:

    (defun curry-three (f n) (funcall f n 3)) -- 2.20.1