From 979cc9843100f4489afad68d2e4b08f56acb5315 Mon Sep 17 00:00:00 2001 From: Thomas Walker Lynch Date: Wed, 22 Jul 2026 10:12:50 +0000 Subject: [PATCH] staring on the TM architecture --- document/book/TM-2026.html | 174 +++++++++++++++++++++++++------------ 1 file changed, 120 insertions(+), 54 deletions(-) diff --git a/document/book/TM-2026.html b/document/book/TM-2026.html index 228b689..4da6c6f 100644 --- a/document/book/TM-2026.html +++ b/document/book/TM-2026.html @@ -28,9 +28,7 @@

Anyone familiar with my writing knows that I have experimented with gender forms in technical language for reasons of inclusion. For example, I used the plural-as-singular style in early writings and was applauded by some, though categorized as illiterate by others. Since then, I have evolved a writing style that emphasizes using roles as subjects: the mathematician, the author, the programmer. Such subjects are singular, so for grammatical agreement, I use the inclusive he. It is structurally much cleaner to use he as inclusive of all readers than it is to force "they" to take on a singular form. I strictly reserve "a person" for abstract generalizations where the subject is truly an unknown third party, including an AI.

-

In the prior edition of this book, the preface included a discussion on the meaning of the word "may" according to RFC 2119, the guidelines for specification writing. There is an important distinction between the 'may' of options or permission, and the 'may' of probability. However, distinguishing between the two was too much of an ask of readers, most of whom skip the preface anyway. So in this edition, I avoid the temptation to use 'may' and replace it with a direct statement of what I mean. "It is of high probability that..." or "There are options for...".

- -

Directly saying what is meant—who would have thought of it? The RFC 2119 authors have clearly struggled with this as well, as they now require the words they discuss to be strictly capitalized to prove they have a proscribed meaning.

+

In the prior edition of this book, the preface included a discussion on the meaning of the word "may" according to RFC 2119, the guidelines for specification writing. There is an important distinction between the 'may' of options or permission, and the 'may' of probability. However, distinguishing between the two was too much of an ask of readers, most of whom skip the preface anyway. So in this edition, I avoid the temptation to use 'may' and replace it with a direct statement of what I mean. "It is of high probability that..." or "There are options for...". Directly saying what is meant—who would have thought of it? The RFC 2119 authors have clearly struggled with this as well, as they now require the words they discuss to be strictly capitalized to prove they have a proscribed meaning.

The search that led to the Turing Machine @@ -376,6 +374,9 @@

State transitions are gated by the read value from the tape. Each state transition function includes actions to be taken; hence, their programmable controller is a Mealy style state machine. The step action is mandatory, though it can be in either direction. The write action must be specified, but the write could be the same symbol that is read, making it effectively an optional action.

+

This machine makes use of a single ended tape. If a computation specifies a two way infinite tape, it can be emulated by interleaving the addresses: assigning odd addressed cells to represent the right going half, and even addressed cells to represent the left going half. This emulation requires taking two steps instead of one to advance in a given logical direction. When analyzing the time complexity of an algorithm, this overhead doubles the constant on the linear term, leaving the asymptotic order of complexity entirely unchanged. The outcomes of decider programs are unaffected. Therefore, utilizing a single ended tape is a computation theory inconsequential variation of the two way tape machine. +

+

Hopcroft and Ullman explain a step of the machine by showing a representation of the tape with the state variable melded in to the left of the currently scanned symbol. Suppose δ(q, X_i) = (p, Y, L); i.e., the next move is leftward. Then,

@@ -540,7 +541,7 @@

These equations show that the state controller size explodes with word width. It would be impractical to implement for all but the smallest of word sizes. This is one of the reasons that computation theory books use modest-sized symbol alphabets in their examples, perhaps the first few letters of the Latin alphabet, or the letter 's' for unary arithmetic. Previous sections discussed challenges transitioning the Turing Machine to a real architecture due to the tape length, and how this could be mitigated. In contrast, there is no practical mediation for implementing a Turing Machine controller even for modest-sized real problems.

-

This raises a question: if the Turing machine is to instruct upon the limitations of real computation, what are the implications to its state controller being impractical? When a Turing Machine proof shows that a number is computable, it doesn't necessarily instruct upon how it could be computed. When a reader picks up a text on applied number theory, also called computer arithmetic, he is unlikely to find a chapter on Turing Machines.

+

This raises a question: if the Turing machine is to instruct upon the limitations of real computation, what are the implications stemming from its state controller being impractical? As one such implication, when a Turing Machine proof shows that a number is computable, it doesn't necessarily instruct upon how it could be computed. When a reader picks up a text on applied number theory, also called computer arithmetic, he is unlikely to find a chapter on Turing Machines.

Blank, empty, SP

@@ -842,10 +843,7 @@

The TTCA Machine programmed string reverse

-

Because the TTCA Machine separates the data path from the control path, it is possible to reverse a string without inspecting the payload. The programmed controller only needs to recognize the structural boundaries of the data protocol. When a payload symbol is encountered, the controller executes a read_d action, placing the value into a data register, which is not examined for decision-making purposes. When a value is used to base a decision upon, the controller executes a read_g, placing the value into a register connected to the arc comparators.

- -

Here is the programmed controller for the TTCA Machine string reverse. Because actions (λ) are bound to states rather than transitions, reading and stepping are distinct states, resulting in a threads of serialized execution.

- +

Because the TTCA Machine separates the data path from the control path, it is possible to reverse a string without inspecting the payload. The programmed controller only needs to recognize the structural boundaries of the data protocol. When a payload symbol is encountered, the controller executes a read_d action, placing the value into a data register, which is not examined for decision-making purposes. When a value is used to base a decision upon, the controller executes a read_g, placing the value into a register connected to the arc comparators. Because actions are bound to states rather than transitions, reading and stepping are distinct states. This combination of features results in a controller that has threads of serialized execution.

# TTCA Machine String Reverse @@ -987,7 +985,9 @@ TTCAM reverse machine -

With data payload examination removed from the controller, long strings of states with a few decision points emerge. There is a loop on the left, and a tail leading to done on the right. The number of states and arcs is a constant independent of how much data is to be reversed.

+

The number of states is constant at 24 independent of how much data is to be reversed. No arc refers to a payload value.

+ +

The form of this diagram shows a lead in, a long loop, and a tail leading to done. This is suggestive of code followed by a while loop that breaks out and then further code completes the program.

void TTCA·reverse_string() { @@ -1220,15 +1220,10 @@

The time complexity of the longest compute time input of length n dropping from O(n^2) to O(n) is computation theoretic consequential, so we should make a choice as to which machine to use as a reference. Given that real computers have multiple pointers into different memory contexts, the multi-head Turing Machine is the more suitable reference model.

Adding heads is not a general method for improving performance complexity. A quadratic performance improvement does not always occur and when it does it is not strong enough to change the asymptotic performance if there are higher-order terms in a step count polynomial. Furthermore, eliminating shuttling will never reduce a linear step count to a constant time step count; the simple reason is that n is unbounded, while adding k heads can only divide the work by a fixed constant k. Consequently, while the transformation is consequential in specific cases, it cannot change the broader time complexity class. -

- +

The Turing Machine architecture/organization -

-If a computation requires a two way infinite tape, the single ended tape machine can emulate it by interleaving the addresses: assigning odd addressed cells to represent the right going half, and even addressed cells to represent the left going half. This emulation requires taking two steps instead of one to advance in a given logical direction. When analyzing the time complexity of an algorithm, this overhead merely doubles the constant on the linear term, leaving the asymptotic order of complexity entirely unchanged. The outcomes of decider programs are unaffected. Therefore, utilizing a single ended tape is an inconsequential variation of the two way tape machine. -

-
Figure 1: A Turing Machine
Figure 1 A Turing Machine
@@ -1458,7 +1453,7 @@ If a computation requires a two way infinite tape, the single ended tape machine

- A leftmost cell is a set of two properties named 'right neighbor' and 'data'. A rightmost cell is a set of two properties named 'left neighbor' and 'data'. An interstitial cell is a set holding three properties: a 'left neighbor', a 'right neighbor', and 'data'. While an island cell owns a single compulsory property, that of 'data'. + A leftmost cell is a set of two properties named 'right neighbor' and 'data'. A rightmost cell is a set of two properties named 'left neighbor' and 'data'. An medial cell is a set holding three properties: a 'left neighbor', a 'right neighbor', and 'data'. While an island cell owns a single compulsory property, that of 'data'.

@@ -1468,7 +1463,7 @@ If a computation requires a two way infinite tape, the single ended tape machine

Tape

- A tape is a set containing exactly one leftmost cell and an infinite number of interstitial cells. For each cell in the set, called cell A, if cell A has a right neighbor that is cell B, then cell B's left neighbor is cell A. Similarly, if cell A has a left neighbor of cell B, then cell B's right neighbor is cell A. Furthermore, any cell in the set must be reachable by traversing right neighbors starting from the leftmost cell, in a finite number of steps. + A tape is a set containing exactly one leftmost cell and an infinite number of medial cells. For each cell in the set, called cell A, if cell A has a right neighbor that is cell B, then cell B's left neighbor is cell A. Similarly, if cell A has a left neighbor of cell B, then cell B's right neighbor is cell A. Furthermore, any cell in the set must be reachable by traversing right neighbors starting from the leftmost cell, in a finite number of steps.

@@ -1495,44 +1490,115 @@ If a computation requires a two way infinite tape, the single ended tape machine Mathematically, a Turing Machine tape can be expressed as a path graph. However, a tape model and a path graph model imply different ontological contexts. The neighbor property of a Turing Machine tape cell specifically informs a clock driven atomic step function where to place the machine head next. The machine only has defined meaning at the state points on the programmed controller. In contrast, a path graph exists in the wider context of graph theory. A path graph has edges and each edge can be focused on, said to be traversed over, and given general properties. These are things we explicitly excluded in the tape definition. If we were to move the tape from the context of the machine and into the more abstract mathematical context by modeling the tape with a path graph, then we would do so for the purpose of analyzing the tape, which is a higher order and more abstract activity. However, in the current exercise we are not reaching towards the more abstract; rather, we are reaching in the other direction, towards machine architecture.

-

Tape transport unit, TTU

+

Head unit, HU

-, from which tapes can be mounted and unmounted. Multiple TTUs can be plugged in. Each TTU contains: +

An HU contains a head and a local controller. The local controller supports these commands, but only when a tape is mounted under it:

-mount/unmount +
    +
  1. read → σ
    2. +
  2. write σ
    3. +
  3. status → γ
    4. +
-
    -
  1. a read/write head
    2. -
  2. a single symbol FIFO read data buffer, written by the TTU, read by the programmable controller
    3. -
  3. a single symbol FIFO status buffer, written by the TTU,, read by the programmable controller
    4. -
  4. a single symbol FIFO command buffer, written by the programmed controller, acted upon immediately by the TTU.
    5. -
- +

One or more head units are plugged into the TTU, which is described in the next section. Commands are only sent to the head unit when a tape is mounted on the TTU, and they are sent by the TTU. The machine at large does not have an interface to the HU. + The status command returns the name of the cell type of the cell the head is on. The head controller communicates with other components of the machine to ascertain the status, which is one of:

-

- The tape head consists of a reference to exactly one of the tape cells and a set of four functions: read, write, step-left, and step-right. In addition, the tape head can throw an error, left-of-leftmost, if the Turing Machine attempts to step left from the leftmost cell. When stepping, the cell reference in the head is updated based on the neighbor properties of the currently referenced cell. The cell referenced by the head is called the cell the head is on, or more simply, the head cell, or more generally as the indicated cell. -

+
    +
  1. leftmost → σ
    2. +
  2. rightmost
    3. +
  3. medial → γ

    +
  4. island → γ

    +
      + -

      - A person can also say that the head indexes the head cell. This utilizes the classical mechanical definition, where an index is a mark for aligning gears. This physical meaning contrasts with an index integer used for addressing an array. The architectural definition of the Turing Machine developed here relies strictly upon the topological properties of the tape, independent of the definition of Natural Numbers. Addresses, which do rely on Natural Numbers, are discussed further on in this volume. This represents a minor divergence from Alan Turing's original paper, as he took it as a given that numbers naturally paired with the squares. We explicitly establish that pairing only after deriving Natural Numbers using the Turing Machine itself. -

      +

      A status of rightmost or island would never be returned for a computer theoretic Turing Machine tape, but it can be for an area of a tape, and such an area can be virtual tape. We will use this model to reconcile the difference between the architectural finite tape, and that of the infinite theoretical tape. Area is discussed in the section dedicated to that topic.

      + +

      Tape transport unit, TTU

      +

      The TTU is where tapes are mounted and unmounted, and heads are plugged into. When multiple heads are plugged in, the controller passes control among them so it appears that heads never collide. The TTU controller has these components: +

      +
        +
      1. one or more read/write heads
        2. +
      2. a single symbol FIFO read data buss, written by the TTU, read by the executor
        3. +
      3. a single symbol FIFO status buffer, written by the TTU, read by the executor
        4. +
      4. a single symbol FIFO command buffer, written by the programmed controller, acted upon immediately by the TTU
        5. +
      -

      The customer programmed components

      +

      The TTU interfaces with the executor, which in turn contains the customer programmed control unit, the CPCU. The executor is single threaded, and issues commands to the TTU.

      -

      The customer programmed portion of the programmed control consists of:

        -
      1. default next state list
        2. -
      2. state dictionary
        3. -
      3. an initial state reference
        4. -
      4. a halt state reference
        5. -
      5. an error state reference
        6. +
      6. read head → σ → σ
        7. +
      7. write σ head
        8. +
      8. status head → γ
        9. +
      9. left
        10. +
      10. right
      -

      A programmer uses a Natural Number to reference a state. Hence the initial state reference and halt state reference are set to Natural Numbers. It is not required but it is conventional to use 0 as the initial state.

      +

      For the first three commands the head argument multiplexes the command to the specified head. If the TTU has one head, the head argument is optional. The last two commands cause the tape to be moved, such that relatively, the head moves left or right by one cell.

      + +

      The customer programmed control unit, CPCU

      + +

      The controller is programmed via patch panel. The panel would look something like this:

      + + + 
      +=================================================================
+               TTCA PROGRAMMABLE STATE CONTROLLER
+=================================================================
+
+[ CONTROL PANEL ] 
+(o) POWER  [/] Toggle     
+( ) RUN    [/] Toggle       ( ) RESET [Btn]    (*) STEP [Btn]
+
+-----------------------------------------------------------------
+[ GATE ]             [ STATE INDICATOR LIGHTS ]
+[ IND. ]             S0    S1    S2    S3    S4    S5
+                     ( )   ( )   (*)   ( )   ( )   ( )
+                      |     |     |     |     |     |
+                      V     V     V     V     V     V
+                   +-----------------------------------+
+( ) g0 (Empty)  g0 | ( )   ( )   ( )   ( )   ( )   ( ) |
+(*) g1 (Sym 0)  g1 | ( )   ( )   ( )   ( )   ( )   ( ) |
+( ) g2 (Sym 1)  g2 | ( )   ( )   (•)===╗ ( )   ( )   ( ) |
+( ) g3 (Mark *) g3 | ( )   ( )   ( )   ║ ( )   ( )   ( ) |
+( ) g4          g4 | ( )   ( )   ( )   ║ ( )   ( )   ( ) |
+                   +-------------------║---------------+
+                                       ║
+                     [ DESTINATION STATE ROWS ]
+                     S0    S1    S2    S3    S4    S5
+                D1 | ( )   ( )   ( )   (•)   ( )   ( ) |
+                D2 | ( )   ( )   ( )   ( )   ( )   ( ) |
+                D3 | ( )   ( )   ( )   ( )   ( )   ( ) |
+                   +-----------------------------------+
+
+                     [ DEFAULT TRANSITIONS ]
+                     S0    S1    S2    S3    S4    S5
+      STATE DFLT   | ( )   ( )   ( )   ( )   ( )   ( ) |
+
+      GLOBAL DFLT  |              ( )                  |
+=================================================================
+
      +       + +

      The top section has two toggle buttons. One turns the machine on, the other selects run or single step mode. Just to the left of the two toggles are indicator lights. To the right of the toggle buttons are two push buttons. One for reset, which sends the machine back to S0, the other for stepping the machine when it is in single step mode. +

      + +

      The second section is the next state panel. It is a rectangle of holes that fit the banana plugs ends of a patch chord. Each column is a current state. Each row is a gate symbol.

      + +

      Below the rectangular next state panel, is the next state panel. All three rows of the panel are the same, they nearly create room so multiple patch cords can be plugged in.

      + +

      Below the next state pantel are the default state transition panels. One for the default next state, and one for the global next state, as described by the TTCA theoretic machine.

      + +

      To program the controller, the programmer plugs in patch cords. Shown in the diagram is a patch cord going from S2,g2, to S3. This realizes a state transition arc for the controller. If the gating value has no patch cord plugged in, the machine instead uses the default transition. For a default transition a patch cord is plugged into the column for the current state, on the default transition table, and that is patched into the next state. Finally, if not patch cord is plugged in that would define the next state, the global default patch cord is followed to the next state.

      + +

      Not shown on this diagram is the row of toggle switches, one per state, that if flipped on, the state becomes a halting state. Also not show is the action selection panel. It is another rectangle, with rows for actions, and a top row for the state. Each state can then be assigned to an action. Note, this is the control panel for a single TTU machine.

      + +

      Stored Program Control

      + +

      Configuring and debugging a patch panel is a long and cumbersome task. The patch panel can instead be programmed with an interpreter, and then the program can be read from the tape. This then realizes the Universal Turing Machine. The program being interpreted then can call out TTCU commands directly, as functions in software. +

      -

      A next state specifier is a pair consisting of an identifer to be matched as a first of the pair, and a next symbol reference as a next component, where each identifier has the form:

      [<TTU_ID>:][<buffer>:]symbol @@ -1907,7 +1973,7 @@ mount/unmount

      - Consider an illustrative example. We start by defining a fundamental language for communicating with the head and tape transport unit. The statements we communicate to our tape transport unit will be explicit physical commands: (step), (step-left), (read), and (write symbol). In the first order, evaluating these commands physically actuates the tape. + Consider an illustrative example. We start by defining a fundamental language for communicating with the head and tape transport unit. The statements we communicate to our tape transport unit will be explicit physical commands: (step), (left), (read), and (write symbol). In the first order, evaluating these commands physically actuates the tape.

      @@ -1941,7 +2007,7 @@ mount/unmount

      - For the second order difference operation, we compose the ASTs to create a new program. Here we extract the body of the second operand's AST and substitute every (write s) followed by a (step) command with an inverted pair: a (step-left) command followed by writing the empty symbol (write □). + For the second order difference operation, we compose the ASTs to create a new program. Here we extract the body of the second operand's AST and substitute every (write s) followed by a (step) command with an inverted pair: a (left) command followed by writing the empty symbol (write □).

      @@ -1954,7 +2020,7 @@ mount/unmount (equal (first cmds) '(write s)) (equal (second cmds) '(step))) (append - '((step-left) (write □)) + '((left) (write □)) (invert-direction (cddr cmds)) )) ( @@ -1991,9 +2057,9 @@ mount/unmount ;; (write s) (step) ;; (write s) (step) ;; (write s) (step) - ;; (step-left) (write □) - ;; (step-left) (write □) - ;; (step-left) (write □) + ;; (left) (write □) + ;; (left) (write □) + ;; (left) (write □) ;; ) @@ -2002,7 +2068,7 @@ mount/unmount

      - Because of the purity of the Lisp syntax, we are able to present a remedial simplifier example here. A (step) followed by a (step-left) annihilate each other, resulting in zero net movement of the tape head. Similarly, on an initially empty tape, a (write s) followed immediately by overwriting with the empty symbol (write □) annihilate each other. + Because of the purity of the Lisp syntax, we are able to present a remedial simplifier example here. A (step) followed by a (left) annihilate each other, resulting in zero net movement of the tape head. Similarly, on an initially empty tape, a (write s) followed immediately by overwriting with the empty symbol (write □) annihilate each other.

      @@ -2017,7 +2083,7 @@ mount/unmount (and (cdr cmds) (equal (first cmds) '(step)) - (equal (second cmds) '(step-left))) + (equal (second cmds) '(left))) (remove-annihilations (cddr cmds))) ( (and @@ -3550,7 +3616,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, step-left, step-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 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.

      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.

      @@ -3559,8 +3625,8 @@ Now suppose defining a Turing Machine that initially has the head on the leftmos

      The Turing Machine state controller has a command symbol tied to each state. The Turing Machine procedure then has us take action based on this symbol. This is our current command set:

      - step-right, causes the head to move to the right neighbor cell. - step-left, causes the head to move to the left neighbor cell. + right, causes the head to move to the right neighbor cell. + left, causes the head to move to the left neighbor cell. read, returns the symbol under the head. The returned symbol is then used to chose the transition arc. write(x), causes the symbol x to be written to the cell that the head is currently on. The symbol x is any symbol from the alphabet. append(x) may only be called when on the rightmost cell. Extends the tape by one cell, and writes the symbol x into that cell, where x is any symbol from the alphabet. @@ -3605,7 +3671,7 @@ Now suppose defining a Turing Machine that initially has the head on the leftmos -a-s ; append to the left, step to the left -

      The left direction is specified with a minus sign, otherwise the direction is taken as right going. So the letter s is the step-right command, and -s is the step-left command. The command s3 steps right three times.

      +

      The left direction is specified with a minus sign, otherwise the direction is taken as right going. So the letter s is the right command, and -s is the left command. The command s3 steps right three times.

      The command a appends and writes a new cell to the right of the head. We use two special characters from the UTF character set to signify the rightmost and leftmost of the tape. This one looks like a little tape with its left cell inked in, ◧, so we use it to stand for leftmost. We use this one, ◨, to mean rightmost. Hence a◨ makes a new rightmost cell, and a◧ makes a new leftmost cell.

      -- 2.20.1