From 0dfd783de8f372acb279b9922f020173e537f646 Mon Sep 17 00:00:00 2001 From: Thomas Walker Lynch Date: Tue, 7 Jul 2026 04:09:18 +0000 Subject: [PATCH] . --- document/TM-2026.html | 223 +++++++++++++++++++++++++++++++++++++++++- 1 file changed, 222 insertions(+), 1 deletion(-) diff --git a/document/TM-2026.html b/document/TM-2026.html index be015be..6a8c331 100644 --- a/document/TM-2026.html +++ b/document/TM-2026.html @@ -19,6 +19,12 @@ + Preface + +

+ This is the second edition of "Tom's Turing Complete Computer Architecture" first volume. It now has its own title, its down introduction, and improved descriptions. +

+ The search for a formal foundation for mathematics led to the Turing Machine

@@ -892,6 +898,8 @@ Computational Analysis +

Definition

+

In mathematics, analysis is the rigorous study of limits, continuity, rates of change, and bounds. It encompasses several specialized branches. Real analysis studies the behavior of real numbers, sequences, and continuous functions. Complex analysis extends these principles to functions of complex variables. Functional analysis examines vector spaces where the elements themselves are functions. Numerical analysis focuses on the design of algorithms to yield approximate solutions for continuous mathematical problems. Harmonic analysis studies the representation of functions or signals as the superposition of basic waves, such as Fourier series. Across all these branches, analysis provides a formal framework for evaluating mathematical objects.

@@ -933,6 +941,219 @@ As an analyzer does not run the machine being studied, it is not required to be a machine that halts. Suppose we have a machine that produces an infinite sequence of digits to a tape without halting. A limit analyzer could examine that machine and, in some cases, determine if it has asymptotic behavior. For example, recognizing that appending a binary fractional sequence of 0.1111... indefinitely evaluates in the limit to 1.0. In this manner, the use of analyzers facilitates using computation theory for deriving higher order mathematics.

+ +

Second order Arithmetic

+ +

+ In their 1990 paper, "Exact Real Arithmetic: Formulating Real Numbers as Functions," Hans-Juergen Boehm and Robert Cartwright presented a system using Turing Machines to represent 'constructive real numbers', or exact real arithmetic. This directly implements a core concept from Alan Turing's 1936 paper of the "computable number." Hans-J. Boehm and Robert Cartwright, "Exact Real Arithmetic: Formulating Real Numbers as Functions," in Design and Implementation of Symbolic Computation Systems (Berlin: Springer, 1990), 43 52. Boehm translated this computation theory into a practical software architecture. Instead of storing a real number as a fixed width floating point approximation, Boehm's system represents a real number as a lazy evaluation function. +

+ +

+ Let us employ Boehm and Cartwright's constructive real numbers, though in second order arithmetic rather than a lazy evaluation system. Because we are doing second order arithmetic, our programs need not be the form of generators that yield a new value when called as for lazy arithmetic, but can be arbitrary programs that if run would produce results. As we are in the second order we will not run them, but rather manipulate them directly. +

+ +

+ Consider an illustrative example. We start by defining a fundamental language for communicating with the head and tape transport unit, so that we can send statements in this language from our Turing Machine controller. This will facilitate us in writing the controller using a Lisp rather than a state machine. The statements we communicate to our tape transport unit will be the the commands: (step), (step-left), (read), and (write symbol). We will not need the read command for this remedial example. +

+ +--- + +

+ Suppose further our goal is to subtract 3 from 5 in the second order. Consider a Turing Machine function 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. The program, then represented as a list of tape commands, is: +

+ + + (defun five () + (progn + (write s) (step) + (write s) (step) + (write s) (step) + (write s) (step) + (write s) (step) + )) + + +

Similarly, the function for the number 3:

+ + + (defun three () + (progn + (write s) (step) + (write s) (step) + (write s) (step) + )) + + +

+ For the second order difference operation, we compose the operands to create a new program. Here we take the second operand machine 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 ·). +

+ + + (defun invert-direction (cmds) + (cond ((null cmds) nil) + ((and (cdr cmds) + (equal (first cmds) '(write s)) + (equal (second cmds) '(step))) + (append '((step-left) (write ·)) + (invert-direction (cddr cmds)))) + (t (cons (first cmds) (invert-direction (cdr cmds)))))) + + (defun primitive-compose-subtract (machine-a machine-b) + (let ((body-a (butlast (funcall machine-a))) + (body-b (butlast (funcall machine-b)))) + (append body-a (invert-direction body-b)))) + + +

We give this program as operands our two natural number programs, and we get as a result a new program.

+ + + (defun primitive-five-minus-3 () + (progn + (write s) (step) + (write s) (step) + (write s) (step) + (write s) (step) + (write s) (step) + (step-left) (write ⊔) + (step-left) (write ⊔) + (step-left) (write ⊔) + )) + + +

+ I gave the resulting program a name so that we can reference it. I also called this 'primitive' because it does no simplification. Simplification customized for the program can be integrated. Here we will send the primitive composition to a program which scans the steps and removes redundant operations. +

+ +

+ 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, resulting in zero net change to the tape. The simplifier scans the program returned by the difference composer and removes these adjacent opposing commands. It calls itself recursively until the scan fails to find any further reductions, returning its operand. That fully optimized operand is the result: a program consisting purely of head and tape transport unit commands. +

+ + + (defun remove-annihilations (cmds) + (cond ((null cmds) nil) + ((and (cdr cmds) + (equal (first cmds) '(step)) + (equal (second cmds) '(step-left))) + (remove-annihilations (cddr cmds))) + ((and (cdr cmds) + (equal (first cmds) '(write s)) + (equal (second cmds) '(write ·))) + (remove-annihilations (cddr cmds))) + (t (cons (first cmds) (remove-annihilations (cdr cmds)))))) + + (defun simplify-machine (cmds) + (let ((reduced (remove-annihilations cmds))) + (if (equal reduced cmds) + cmds + (simplify-machine reduced)))) + + +

After giving the difference program to the simplifier, we get:

+ + + (defun simplified-five-minus-3 () + (progn + (write s) (step) + (write s) (step) + (write s) (step) + )) + + + + +

Second order Arithmetic

+ +

+ In their 1990 paper, "Exact Real Arithmetic: Formulating Real Numbers as Functions," Hans-Juergen Boehm and Robert Cartwright presented the idea of using Turing Machines to represent 'constructive real numbers', or exact real arithmetic. This directly implements a core concept from Alan Turing's 1936 paper of the "computable number." Hans-J. Boehm and Robert Cartwright, "Exact Real Arithmetic: Formulating Real Numbers as Functions," in Design and Implementation of Symbolic Computation Systems (Berlin: Springer, 1990), 43 52. Boehm translated this computation theory into a practical software architecture. Instead of storing a real number as a fixed width floating point approximation, Boehm's system represents a real number as a lazy evaluation function. +

+ +

+ Let us employ Boehm and Cartwright's constructive real numbers in second order arithmetic. Let us take a basic example of how this would work. Suppose we are to add 2 to 3 in the second order. Consider a Turing Machine that outputs the number 2, i.e., it prints to the tape, 'ss·'. Here I am using the middle dot as a terminator symbol, and unary notation. The Turing Machine program, here quoted in Lisp so as to be treated as a mathematical object rather than executed, would be: +

+ + + '(let () + (dotimes (i 2) + (write 's') + (step)) + (write '·')) + + +

Now the number 3:

+ + + '(let () + (dotimes (i 3) + (write 's') + (step)) + (write '·')) + + +

+ When run, the Arabic representation of each number gets written in unary code on the tape. This is a consequence of my having chosen a simple example for purposes of illustration. In general, Turing Machine programs can be complex algorithms. In a lazy evaluation system, each algorithm is expressed as a generator, so that it can be called upon to produce a digit. Here we are doing something different. We are not imposing any specific form on the programs, because we will not lazy evaluate them, as that would require descent into the first order to run them. Rather we will instead compose them. Here is our addition composer: +

+ + + (defun primitive-compose-add (machine-a machine-b) + (let ((body-a (butlast (cddr machine-a))) + (body-b (butlast (cddr machine-b)))) + `(let () + ,@body-a + ,@body-b + (write '·')))) + + +

I called this primitive, because it does no simplification. We will send the primitive composition to another program which expands out the steps, and removes redundant operations.

+ + + + (defun primitive-compose-add (machine-a machine-b) + (let ((body-a (butlast (cddr machine-a))) + (body-b (butlast (cddr machine-b)))) + `(let () + ,@body-a + ,@body-b + (write '·')))) + + +

+ I called this primitive, because it does no simplification. We will send the primitive composition to a program which expands out the steps, and removes redundant operations. Because of the purity of the Lisp syntax, we are able to present a remedial simplifier example here. We look at the operands and see if they fit the pattern of a natural number generator. If they do, we bypass the primitive concatenation entirely and synthesize a mathematically equivalent. We start with an extraction function that inspects the abstract syntax tree: +

+ + + (defun extract-natural-value (machine) + "Returns N if the machine is a simple natural number generator, otherwise nil." + (when (and (listp machine) + (eq (first machine) 'let) + (listp (third machine)) + (eq (first (third machine)) 'dotimes)) + (let ((loop-binding (second (third machine)))) + (when (and (listp loop-binding) + (numberp (second loop-binding))) + (second loop-binding))))) + + +

+ With the ability to safely extract the value from static natural number generators, we can define a smart composer. This composer analyzes both operands. If both yield static values, it performs the addition internally and outputs a single, fully reduced generator. If the analysis fails—perhaps because one of the operands is a complex algorithmic generator that requires lazy evaluation or full expansion—it falls back to the primitive composition. +

+ + + (defun compose-add (machine-a machine-b) + (let ((val-a (extract-natural-value machine-a)) + (val-b (extract-natural-value machine-b))) + (if (and val-a val-b) + `(let () + (dotimes (i ,(+ val-a val-b)) + (write 's') + (step)) + (write '·')) + (primitive-compose-add machine-a machine-b)))) + + + + + + Address

Unary Representation address

@@ -940,7 +1161,7 @@

We can define a Turing Machine that is identical to the recursive definition of Natural Numbers as given by Peano. Giuseppe Peano, Arithmetices principia, nova methodo exposita (Turin: Fratres Bocca, 1889).

-

If we were to run the Natural Numbers Machine and watch as it writes to the tape, we would watch as the Natural Numbers are printed one after another, '·s·ss·sss·ssss· ...'. Here we are using the middle dot as a terminator symbol. As the Natural Numbers Machine never halts, we cannot use the Natural Number Machine to initialize a tape, but we can analyze the machine. When the leftmost cell holds a terminator, we say it has the value 'zero'. We call '·s·' the number 'one'. Each set of 's' adjacent symbols surrounded by the terminators, and zero, is said to be a Natural Number. +

If we were to run the Natural Numbers Machine and watch as it writes to the tape, we would watch as the Natural Numbers are printed one after another, '·s·ss·sss·ssss· ...'. As the Natural Numbers Machine never halts, we cannot use the Natural Number Machine to initialize a tape, but we can analyze the machine. When the leftmost cell holds a terminator, we say it has the value 'zero'. We call '·s·' the number 'one'. Each set of 's' adjacent symbols surrounded by the terminators, and zero, is said to be a Natural Number.

To say that one Natural Number A is smaller than Natural Number B is to say that A would occur on the Natural Number Machine tape to the left of B, if the machine were to be run. Similarly, if B were said to be greater than A, that would mean B would occur further to the right. To increment a Natural Number is to find its right neighbor. To decrement a number is to find its left neighbor. -- 2.20.1