From 29d2a458b227e6f532c91ac33e2bb67e2537f65d Mon Sep 17 00:00:00 2001 From: Thomas Walker Lynch Date: Tue, 7 Jul 2026 05:10:36 +0000 Subject: [PATCH] . --- document/TM-2026.html | 267 +++++++++++++++++------------------------- 1 file changed, 110 insertions(+), 157 deletions(-) diff --git a/document/TM-2026.html b/document/TM-2026.html index 6a8c331..9f79375 100644 --- a/document/TM-2026.html +++ b/document/TM-2026.html @@ -949,208 +949,161 @@

- 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. + 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 in the form of generators that yield a new value when called, but can be arbitrary programs containing complex control logic. If run, they evaluate physical conditions and produce results. As we are in the second order, however, we will not run them, but rather analyze and manipulate their structural logic.

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

---- -

- 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: + 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:

- (defun five () - (progn - (write s) (step) - (write s) (step) - (write s) (step) - (write s) (step) - (write s) (step) - )) + (defparameter *five-ast* + '(progn + (write s) (step) + (write s) (step) + (write s) (step) + (write s) (step) + (write s) (step) + )) -

Similarly, the function for the number 3:

+

Similarly, the AST for the number 3:

- (defun three () - (progn - (write s) (step) - (write s) (step) - (write s) (step) - )) + (defparameter *three-ast* + '(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. + If we were to dynamically evaluate these ASTs in the first order, the Arabic representation of each number would be physically written in unary code on the tape.

- 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. + 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 ⊔).

- (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)))) + (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 (ast-a ast-b) + (let + ( + (body-a (rest ast-a)) + (body-b (rest ast-b)) + ) + `(progn + ,@body-a + ,@(invert-direction body-b) + ))) -

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

+

We pass our two natural number ASTs to this composer, and we get as a result a newly synthesized AST.

- (defun simplified-five-minus-3 () - (progn - (write s) (step) - (write s) (step) - (write s) (step) - )) + (defparameter *primitive-five-minus-3-ast* (primitive-compose-subtract *five-ast* *three-ast*)) + + ;; *primitive-five-minus-3-ast* evaluates to: + ;; '(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 ⊔) + ;; ) - - - -

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. + I called this 'primitive' because it is missing the simplification. This sort of simplification is also known as compiler code optimization. Optimizations can be operation specific, or general in nature. Here we will send the primitive composition's body to an analyzer which scans the steps and removes the redundant operations.

- 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: + 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.

- - '(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: + For a program containing branched control logic, the simplifier would require a deep recursive walk of the AST to ensure operations aren't annihilated across conditional boundaries. For our explicit natural number generators, a linear scan of the progn body suffices. It calls itself recursively until the scan fails to find any further reductions, returning its optimized AST.

- (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 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 (ast) + (let* + ( + (cmds (rest ast)) + (reduced (remove-annihilations cmds)) + ) + (if + (equal reduced cmds) + ast + (simplify-machine `(progn ,@reduced)) + ))) - - (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: -

+

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

- (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))))) + (defparameter + *simplified-five-minus-3-ast* + (simplify-machine *primitive-five-minus-3-ast*) + ) + + ;; *simplified-five-minus-3-ast* evaluates to: + ;; '(progn + ;; (write s) (step) + ;; (write s) (step)) -

- 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)))) - - - -- 2.20.1