From 1a52df9730e22452403004b3f7264c327a347e49 Mon Sep 17 00:00:00 2001 From: Thomas Walker Lynch Date: Mon, 27 Jul 2026 09:45:14 +0000 Subject: [PATCH] reorg of defintion --- document/book/TM-2026.html | 141 ++++++++++++++++++------------------- 1 file changed, 70 insertions(+), 71 deletions(-) diff --git a/document/book/TM-2026.html b/document/book/TM-2026.html index 77d8bc9..98759fc 100644 --- a/document/book/TM-2026.html +++ b/document/book/TM-2026.html @@ -337,9 +337,7 @@ then we can say without qualification that T is computation theoretic inconsequential. Though still implied are the sets of machines and tapes.

- The computation theoretic Turing Machine - -

The Hopcroft and Ullman Turing Machine

+ The conventional Turing Machine

This definition comes from Hopcroft and Ullman's book with minor terminology changes to make it flow into the text here John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation (Reading: Addison Wesley, 1979)..

@@ -386,6 +384,8 @@

So first the tape is X_1 X_2 \cdots X_{i-1} X_i X_{i+1} \cdots X_n, with the head over X_i, and in state q. Then after a step of the machine, the tape is X_1 X_2 \cdots X_{i-1} Y X_{i+1} \cdots X_n, with the head over X_{i-1}, and in state p. Thus X_i was overwritten with Y, and the head stepped left.

+

The reverse machine example

+

Here is the programmed controller for a Turing Machine that reverses a binary string. Although by definition each state transition matches exactly one value under the head, as a practical matter, disjunctive selection is allowed via a comma list. A conjunctive phrasing for a state transition proposition would require stringing intermediate states in series.

HU reverse machine @@ -506,6 +506,8 @@ done • 0 1 1 +

Analysis of the reverse machine

+

The total number of steps for reversing an n symbol string:

@@ -609,6 +611,10 @@

For the modified computational Turing machine presented later in this chapter, there will be a separate control alphabet of predefined symbols, as for the Hopcroft-Ullman interpretation. However, so as to support recursion, and because the current scheme does not achieve protocol guarantees, the predefined alphabet will be part of the alphabet Σ rather than distinct from it. Programmers then must explicitly design communication protocols that suit the problems they are working on, and those protocols become opaque for examination by a higher authority. Note that this does not preclude a programmer from using SP as an EOM marker, rather it removes the embedding of that protocol from the Turing Machine definition.

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

+

The unspecified symbol

In the first edition of this book, I introduced a "read only after write" rule while working towards an architectural Turing Machine because conventional computer architectures do not maintain a concept of empty memory. The approach described in this section integrates the "read only after write" into a computation theoretic machine by designing in the concept of being unspecified, which then displaces the concept of a cell being empty.

@@ -634,13 +640,11 @@

Recall the suggestion earlier in this section that "perhaps an algorithm could be studied for this very quality of not ever making decisions based on unspecified data." In this capacity, the unspecified symbol functions as a test probe. Such an analysis can be done with a two-layer architecture: a first-order machine under study and a second-order machine performing the analysis. The unspecified symbol resides within the alphabet of the second-order machine, which possesses the authority not only to move the symbol but also to base logic upon it. However, demoting the unspecified marker from a meta-symbol to a standard decision symbol leaves the second-order machine without a meta-symbol of its own. In a strictly layered architecture, analogous to Russell and Whitehead's hierarchy of types, a programmer could define unspecified-0, unspecified-1, and so forth, explicitly embedding the order as a unique identifier. However, if the system lacks this strict stratification, the layering strategy collapses. This occurs when a statement operates as an independent island of meaning, analogous to Gödel's unprovable truths, or when an analyzer is tasked with evaluating itself, as in Turing's halting proof. Therefore, whether an unspecified meta-symbol can be deployed successfully depends entirely upon the structural boundaries of the specific system under test.

-

The computation theoretic TTCA Machine

- -

This section 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.

+

The modifications

The specific architectural modifications are as follows:

    -
  1. There is one unified alphabet \Sigma to which both status symbols and data symbols belong.
    2. +
  2. There is one unified alphabet σ to which both status symbols and data symbols belong.
  3. It utilizes a Moore-style programmed state controller, so that actions can be managed separately from state transitions.
  4. It separates control flow from data flow:
      @@ -648,10 +652,10 @@
    1. Read and write actions accept an operand designating the target or source register respectively, either s or d.
    5. -
  5. 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, \sigma, S_{i+1} \rangle): +
  6. 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):
    1. state-specific transition default pairs, which have the form \langle S_i, S_{i+1} \rangle
      2. -
    2. status-specific transition default pairs, which have the form \langle \sigma, S_{i+1} \rangle
      3. +
    3. status-specific transition default pairs, which have the form \langle σ, S_{i+1} \rangle
    4. a global default transition, which has the form S_{i+1}
    7. @@ -659,27 +663,28 @@

    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 (\delta_0): Selects the transition rule that matches the current state and the value of the status register.
      2. -
    2. State Default (\delta_1): If no conditional next state rule is found, selects the default transition rule that matches the current state.
      3. -
    3. Status Default (\delta_2): If no next state rule has been found, selects the default transition rule that matches the current machine status.
      4. -
    4. Global Default (\delta_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, \delta_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 \Sigma, adding a Q_unspecified state to Q, and then adding a status default arc to \delta_2 of \langle \mathtt{unspecified}, \mathrm{Q\_unspecified} \rangle. Then, if the machine attempts to make a decision upon the unspecified symbol, the machine will go to the Q_unspecified state. 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.

    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.

    -

    There is a mechanical procedure for converting a Moore Machine into a Mealy Machine, and the reverse. Two such converted machines are equally expressive. Making the read operation an explicit action, instead of having it implied by a state transition, increases the number of states in a controller, and consequently the number of steps that must be taken. However, the new machine can do in two steps anything the former machine could do in one; consequently, this change affects the multiplier constant on the linear term of the step count formula but does not change the computation complexity class determined from such a step count. The layers of next-state functions can be collapsed into one layer, where the missing arguments are filled in with all possible unused values. This potentially increases the number of state transition arcs that must be specified, but the state transition logic and the number of states remain unchanged. Partitioning the machine definition by separation of concerns does not change the total specification. Hence, these modifications are computation theoretic inconsequential.

    +

    There is a mechanical procedure for converting a Moore Machine into a Mealy Machine, and the reverse. Two such converted machines are equally expressive. Making the read operation an explicit action, instead of having it implied by a state transition, increases the number of states in a controller, and consequently the number of steps that must be taken. However, the new machine can do in two steps anything the former machine could do in one; consequently, this change scales the step count formula by a constant factor, leaving the order of the highest term unchanged. The layers of next-state functions can be collapsed into one layer, where the missing arguments are filled in with all possible unused values. This potentially increases the number of state transition arcs that must be specified, but the state transition logic and the number of states remain unchanged. Partitioning the machine definition by separation of concerns does not change the total specification. Hence, these modifications are computation theoretic inconsequential.

    + -

    The TTCA Machine fixed part

    +

    The TTCA Machine fixed part

    - \mathrm{MF} = (\mathrm{QF}, \mathrm{\Sigma 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 defining the programmed state controller.

    +

    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.

    The set of predefined states:

    @@ -698,38 +703,38 @@ , & \mathtt{right} \\ , & \mathtt{read}(\mathtt{d} \mid \mathtt{s}) \\ , & \mathtt{status} \\ - , & \mathtt{write}(\mathtt{d} \mid \mathtt{s} \mid \mathtt{\sigma}, [\sigma]) \\ + , & \mathtt{write}(\mathtt{d} \mid \mathtt{s} \mid \mathtt{σ}, [σ]) \\ \} \end{aligned}
    -

    where \sigma must be in \Sigma.

    +

    where σ must be in σ.

    The set of predefined symbols:

    - \mathrm{\Sigma F} = \{\mathrm{\Sigma F}{\cdot}\mathtt{on\_leftmost}\} + \mathrm{σ F} = \{\mathrm{σ F}{\cdot}\mathtt{leftmost}\}
    -

    The TTCA Machine variables

    +

    Machine variables

    - \mathrm{MV} = (q, d, s) + \mathrm{MV} = (q, s, d)

    q: is the current state of the machine.

    -

    d: is the data register.

    +

    s: is the status register value, also called the machine status.

    -

    s: is the status register.

    +

    d: is the data register value.

    -

    The TTCA Machine programmable part

    +

    Programmable part

    - \mathrm{MP} = (\mathrm{QP}, \mathrm{\Sigma P}, \lambda\mathrm{P}, \delta_0, \delta_1, \delta_2, \delta_3, \mathrm{HP}) + \mathrm{MP} = (\mathrm{QP}, \mathrm{ΣP}, \lambda\mathrm{P}, δ_0, δ_1, δ_2, δ_3, \mathrm{HP})
    @@ -740,50 +745,50 @@

    A set of programmed data symbols:

    - \mathrm{\Sigma P} + \mathrm{ΣP}

    The programmed actions. A set of pairs of the form:

    - \lambda\mathrm{P} = \{ \langle q_0, a \rangle, \dots \} + \lambda\mathrm{P} = \{ \langle q_i, a \rangle, \dots \}
    -

    where q_0 is matched to the current state, and a is a member of \mathrm{AF}.

    +

    where q_i is matched to the current state, and a is a member of \mathrm{AF}. The subscript i is a device used to emphasize that q_i can be any member of the total set of states, Q, not merely the initial state, which some readers might have misunderstood had the symbology of q_0 been used. Also note, the spartan q is being reserved to denote the contents of the q register. +

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

    - \delta_0 = \{ \langle q_0, r{\cdot}\sigma, q_1 \rangle, \dots \} + δ_0 = \{ \langle q_i, σ, q_{i+1} \rangle, \dots \}
    -

    where q_0 is matched to the current state of the machine. r{\cdot}\sigma is a symbol in register r, where r is either d or s. q_1 is the next state. When q_0 matches the current state and the specified register holds \sigma, q_1 becomes the next state. Both q_0 and q_1 come from the total set Q. \sigma comes from the total set \Sigma.

    +

    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:

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

    where q_0 is matched to the current state, and upon a match q_1 will be taken as the next state.

    +

    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:

    - \delta_2 = \{ \langle r{\cdot}\sigma, q_1 \rangle, \dots \} + δ_2 = \{ \langle σ, q_{i+1} \rangle, \dots \}
    -

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

    +

    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:

    - \delta_3 = q_1 + δ_3 = q_{i+1}
    -

    This is the transition of last resort. It is unconditional; the next state becomes q_1.

    +

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

    A set of programmer-defined halting states:

    \mathrm{HP}
    - -

    The TTCA Machine in total

    +

    The TTCA Machine definition in total

    - M = (Q, \Sigma, \mathrm{AF}, \lambda\mathrm{P}, \delta, H) + M = (q, s, d, Q, Σ, \mathrm{AF}, \lambda\mathrm{P}, δ, \mathrm{HP})
    @@ -794,17 +799,12 @@

    The complete set of symbols, uniting the fixed control symbols and the programmed data symbols:

    - \Sigma = \mathrm{\Sigma F} \cup \mathrm{\Sigma P} + Σ = \mathrm{ΣF} \cup \mathrm{ΣP}

    The ordered sequence of next state transition rules:

    - \delta = [\delta_0 \mid \delta_1 \mid \delta_2 \mid \delta_3] -
    - -

    The complete set of halting states, uniting the fixed predefined states and the programmed states:

    -
    - H = \mathrm{HF} \cup \mathrm{HP} + δ = [δ_0 \mid δ_1 \mid δ_2 \mid δ_3]

    Computation theoretic TTCA Machine executor

    @@ -841,7 +841,6 @@

    If the machine reaches a point where there is no next state, or the head has walked off of the tape, the machine hangs. If, after the state transition phase completes, the current state is a member of H, the machine halts. Otherwise the cycle repeats.

    -

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

    @@ -895,7 +894,7 @@ Q·Check_Boundary: λ: status δ: - (on_leftmost: Q·Done) + (leftmost: Q·Done) Q·Fetch_0 Q·Read_Data: @@ -906,7 +905,7 @@ Q·Check_Last_Char: λ: status δ: - (on_leftmost: Q·Place_Last) + (leftmost: Q·Place_Last) Q·Place_SP # Phase 3: Mark the location and carry the opaque data rightward. @@ -1008,7 +1007,7 @@ while(g == EOM || g == SP){ status(); // Termination: Short-circuit for empty string - if(g == on_leftmost) return; + if(g == leftmost) return; left(); read_g(); } @@ -1017,7 +1016,7 @@ status(); // Center Break: Q·Check_Last_Char routes to the final chain - if(g == on_leftmost) break; + if(g == leftmost) break; // Main Carry Loop: Mark, carry, drop, and return to pivot write_σ(SP); @@ -1090,7 +1089,7 @@ Q·Check_Empty: λ: status(0) δ: - (on_leftmost: Q·Empty_Setup_1) + (leftmost: Q·Empty_Setup_1) Q·Setup_Write_1 Q·Empty_Setup_1: @@ -1117,7 +1116,7 @@ Q·Copy_Status: λ: status(0) δ: - (on_leftmost: Q·Copy_Last_Erase) + (leftmost: Q·Copy_Last_Erase) Q·Copy_Erase Q·Copy_Erase: @@ -1186,7 +1185,7 @@ // Phase 2: Setup pointers or short-circuit on empty string status(0); - if(g == on_leftmost){ + if(g == leftmost){ right(1); write_σ(1, EOR); return; @@ -1201,7 +1200,7 @@ status(0); // Break out to process the final character - if(g == on_leftmost) break; + if(g == leftmost) break; write_σ(0, SP); write_d(1); @@ -2037,9 +2036,9 @@

    The difference between adjacent function values in the above sequence is called the first finite difference. The forward first difference is defined as: - \Delta_i = f(t_{i+1}) - f(t_i). + δ_i = f(t_{i+1}) - f(t_i). While the backwards first difference is - \Delta_i = f(t_i) - f(t_{i-1}). + δ_i = f(t_i) - f(t_{i-1}). If 'forward' or 'backwards' is not specified, then the difference is taken to be 'forward'. Hence, extending a function is identical to adding the first difference. Thus a sequence of function values implies a sequence of first differences.

    @@ -2060,8 +2059,8 @@ Count (t) f(t) = t^2 - 1st Diff (\Delta^1) - 2nd Diff (\Delta^2) + 1st Diff (δ^1) + 2nd Diff (δ^2) @@ -2103,7 +2102,7 @@

    - Here is the sequence of tape states as the machine is repeatedly called to extend the function from its initial conditions at t = 0. During each step, the machine adds \Delta^1 to f, and \Delta^2 to \Delta^1, as there is no \Delta^3, it is taken to be zero, so \Delta^2 is merely copied down. + Here is the sequence of tape states as the machine is repeatedly called to extend the function from its initial conditions at t = 0. During each step, the machine adds δ^1 to f, and δ^2 to δ^1, as there is no δ^3, it is taken to be zero, so δ^2 is merely copied down.

    @@ -2183,7 +2182,7 @@

    Lemma: A polynomial function of degree \omega will have a D_0 vector of extent \omega

    - A polynomial of degree \omega is defined by a highest order term a_\omega t^\omega. The first forward difference operator, \Delta f(t) = f(t+1) - f(t), inherently cancels the t^\omega term. The binomial expansion of (t+1)^\omega yields t^\omega as its leading term, which subtracts out, leaving a new polynomial of exactly degree \omega - 1. + A polynomial of degree \omega is defined by a highest order term a_\omega t^\omega. The first forward difference operator, δ f(t) = f(t+1) - f(t), inherently cancels the t^\omega term. The binomial expansion of (t+1)^\omega yields t^\omega as its leading term, which subtracts out, leaving a new polynomial of exactly degree \omega - 1.

    @@ -2314,9 +2313,9 @@ Count (t) f(t) = 2^t - 1st Diff (\Delta^1) - 2nd Diff (\Delta^2) - 3rd Diff (\Delta^3) + 1st Diff (δ^1) + 2nd Diff (δ^2) + 3rd Diff (δ^3) @@ -2410,7 +2409,7 @@ Count (t) Quotient (f(t)/g(t)) - 1st Diff Ratio (\Delta^1 f(t) / \Delta^1 g(t)) + 1st Diff Ratio (δ^1 f(t) / δ^1 g(t)) @@ -2482,7 +2481,7 @@

    - I included the first difference along with the evaluation results in the table above. When building a first difference table an interesting thing happens at the singularity, the first difference and the function itself coincide, note calls 4 and 5. This makes sense because \Delta f(4) = f(5) - f(4), which becomes \Delta f(4) = 0 - f(4), and the same happens to g in the denominator, so the signs cancel. Note also \Delta f(5) = f(6) - f(5), which becomes \Delta f(5) = f(6) - 0. + I included the first difference along with the evaluation results in the table above. When building a first difference table an interesting thing happens at the singularity, the first difference and the function itself coincide, note calls 4 and 5. This makes sense because δ f(4) = f(5) - f(4), which becomes δ f(4) = 0 - f(4), and the same happens to g in the denominator, so the signs cancel. Note also δ f(5) = f(6) - f(5), which becomes δ f(5) = f(6) - 0.

    Ostensibly it looks like we have happened upon a discrete version of L'Hôpital's rule, that we merely use the first difference quotient instead of the function quotient at the singularity. But alas, the coincidence occurs at h(4) rather than at h(5). For the second coincidence, we find h(6) as the 5th first finite difference. In neither case did we learn anything about the value of h(5). @@ -2620,7 +2619,7 @@

    Wolfram Mathematica utilizes a true second order computation system by keeping expressions in their exact symbolic form for as long as possible. An expression like Sqrt[2] + Pi remains an AST of symbols. It then relies on an extensive library of algebraic rewrite rules to simplify the tree. However, unlike Boehm and Cartwright's method of pulling precision through back propagating extension calls, when a numeric result is required, Mathematica runs the computation forward using significance arithmetic. Should there be insufficient precision at the result, it employs an adaptive retry loop Fredrik Johansson, "The significance of arithmetic," 2008. Mathematica implements significance arithmetic by approximating numbers as a floating point value with an attached error estimate, allowing dynamic adaptation and iteration if precision falls below the required threshold. See also: Wolfram Language Documentation, "Arbitrary Precision Numbers" (https://reference.wolfram.com/language/tutorial/ArbitraryPrecisionNumbers.html)..

    -

    The approach I used differs from both of these approaches. Like them, the first step is to build the AST, but then the tree is evaluated in two phases. The first phase analyzes the tree, while createing error propagation expressions either per computation step or for atomic computation blocks. These take the form of symbolic expressions with error \epsilon in and error \delta out, over the domain of the input. Then instead of back propagation of precision requests at run time, there is a back propagation of precision requirements at analysis time. This approach was used on the AMD K5 processor transcendental microcode to guarantee that computations yielded specified accuracy. The method is also well suited for setting the bus widths for application specific processors, because the analysis step can occur once at design time. Thomas Walker Lynch, A. Ahmed, M. Schulte, T. Callaway, and R. Tisdale, "The K5 Transcendental Functions," Proceedings of the 12th IEEE Symposium on Computer Arithmetic, 1995. DOI: 10.1109/ARITH.1995.465368. Thomas Walker Lynch, "Numerical Analysis of Computer Approximations," September 2018. DOI: 10.13140/RG.2.2.10906.49601. License CC BY 4.0. https://www.researchgate.net/publication/329402329_Numerical_Analysis_of_Computer_Approximations. +

    The approach I used differs from both of these approaches. Like them, the first step is to build the AST, but then the tree is evaluated in two phases. The first phase analyzes the tree, while createing error propagation expressions either per computation step or for atomic computation blocks. These take the form of symbolic expressions with error \epsilon in and error δ out, over the domain of the input. Then instead of back propagation of precision requests at run time, there is a back propagation of precision requirements at analysis time. This approach was used on the AMD K5 processor transcendental microcode to guarantee that computations yielded specified accuracy. The method is also well suited for setting the bus widths for application specific processors, because the analysis step can occur once at design time. Thomas Walker Lynch, A. Ahmed, M. Schulte, T. Callaway, and R. Tisdale, "The K5 Transcendental Functions," Proceedings of the 12th IEEE Symposium on Computer Arithmetic, 1995. DOI: 10.1109/ARITH.1995.465368. Thomas Walker Lynch, "Numerical Analysis of Computer Approximations," September 2018. DOI: 10.13140/RG.2.2.10906.49601. License CC BY 4.0. https://www.researchgate.net/publication/329402329_Numerical_Analysis_of_Computer_Approximations.

    None of these computation systems, that of Boehm and Cartwright, Mathematica, nor my error analysis approach, makes use of the IEEE 754 standard floating point arithmetic. Rather they all require the use of variable precision. In the case of Boehm and Cartwright's this occurs through the serialization implied through lazy calls for more precision. In the case of Mathematica it is explicit in the significance arithmetic. In my error analysis approach, the means for variable precision was the High Radix Online Arithmetic Thomas W. Lynch, "High Radix On Line Arithmetic for Credible and Accurate Computing," Real Numbers and Computers, École des Mines de Saint Étienne, France, 1995, pp. 78 89. Thomas W. Lynch and Michael J. Schulte, "Software for High Radix On Line Arithmetic," Reliable Computing, vol. 2, no. 2, 1996, pp. 133 138. DOI: 10.1007/BF02425915.. @@ -4065,7 +4064,7 @@ Now suppose defining a Turing Machine that initially has the head on the leftmos

    - When a person applies the discrete forward difference operator, \Delta, to a falling factorial, it behaves identically to the continuous derivative: \Delta(t^{\underline{n}}) = n t^{\underline{n - 1}}. + When a person applies the discrete forward difference operator, δ, to a falling factorial, it behaves identically to the continuous derivative: δ(t^{\underline{n}}) = n t^{\underline{n - 1}}.

    Stirling Numbers of the Second Kind, S(n, k)

    -- 2.20.1