From bf351d14845b6b1f20cbbf79add743f3792fb17a Mon Sep 17 00:00:00 2001 From: Thomas Walker Lynch Date: Sat, 11 Jul 2026 15:50:54 +0000 Subject: [PATCH] Refining Turing Machine architecture description --- document/TM-2026.html | 67 ++++++++++++++++++++++++++++--------------- 1 file changed, 44 insertions(+), 23 deletions(-) diff --git a/document/TM-2026.html b/document/TM-2026.html index a79900d..8a3caed 100644 --- a/document/TM-2026.html +++ b/document/TM-2026.html @@ -533,7 +533,7 @@ - The Turing Machine as a computer architecture + The Turing Machine architecture

In this interpretation of the Turing Machine, the architecture utilizes a single ended tape, as done in Hopcroft and Ullman's book John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation (Reading: Addison Wesley, 1979).. 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. @@ -548,24 +548,45 @@

Figure 1 A Turing Machine
+

The Turing Machine consists of:

-

The Turing Machine consists of:

+

The customer programmable components

+ +

The immutable structural components

+ + + +

This is the fixed logic internal to the machine. +

  • a constant operation procedure where each step of the procedure can be referenced
  • a read writable operation procedure step reference counter
    • -
  • a read only clock to synchronize control and to cause counting until the halt state is reached.
    • -
  • a fixed hardware comparator to evaluate state and symbol equivalencies
  • a reset button that activates logic that initializes the machine
    • +
  • a read only clock to synchronize control and to cause counting until the halt state is reached.
    • + +

    Purchased separately. + +

    + +

    Each highlighted term is a short name for the associated item.

    @@ -951,7 +972,7 @@

    - Suppose our goal is to subtract 3 from 5 in the second order. Consider a Turing Machine representation named five that outputs the number 5, i.e., it prints to the tape, 'sssss', using unary notation. Let us assume that the tape is initially empty and that the empty symbol '⊔' terminates the string. To preserve the code for second order analysis, we define the program's Abstract Syntax Tree (AST) as a quoted progn block. This block can contain any native Lisp control structures, though for this generator it is a simple sequence: + Suppose our goal is to subtract 3 from 5 in the second order. Consider a Turing Machine representation named five that outputs the number 5, i.e., it prints to the tape, 'sssss', using unary notation. Let us assume that the tape is initially empty and that the empty symbol '□' terminates the string. To preserve the code for second order analysis, we define the program's Abstract Syntax Tree (AST) as a quoted progn block. This block can contain any native Lisp control structures, though for this generator it is a simple sequence:

    @@ -981,7 +1002,7 @@

    - 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 (step-left) command followed by writing the empty symbol (write □).

    @@ -994,7 +1015,7 @@ (equal (first cmds) '(write s)) (equal (second cmds) '(step))) (append - '((step-left) (write ⊔)) + '((step-left) (write □)) (invert-direction (cddr cmds)) )) ( @@ -1031,9 +1052,9 @@ ;; (write s) (step) ;; (write s) (step) ;; (write s) (step) - ;; (step-left) (write ⊔) - ;; (step-left) (write ⊔) - ;; (step-left) (write ⊔) + ;; (step-left) (write □) + ;; (step-left) (write □) + ;; (step-left) (write □) ;; ) @@ -1042,7 +1063,7 @@

    - 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 (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.

    @@ -1063,7 +1084,7 @@ (and (cdr cmds) (equal (first cmds) '(write s)) - (equal (second cmds) '(write ⊔))) + (equal (second cmds) '(write □))) (remove-annihilations (cddr cmds))) ( t @@ -1799,7 +1820,7 @@ increment: a = TTU.read() - if a == 0 or a == ⊔: + if a == 0 or a == □: TTU.write(1) halt TTU.write(0) -- 2.20.1