From 2149c97cd1a6c8d68088badc5ce84301d338a4cf Mon Sep 17 00:00:00 2001 From: Thomas Walker Lynch Date: Wed, 29 Jul 2026 12:52:36 +0000 Subject: [PATCH] . --- document/book/TM-2026.html | 2090 ++++++++++++++++++------------------ 1 file changed, 1057 insertions(+), 1033 deletions(-) diff --git a/document/book/TM-2026.html b/document/book/TM-2026.html index e6686d3..cae3326 100644 --- a/document/book/TM-2026.html +++ b/document/book/TM-2026.html @@ -378,7 +378,7 @@

Here the input alphabet is said to be a subset of a larger alphabet. This allows some symbols to be set aside and only used by the machine. The symbols which are exclusive to the larger set are control symbols. control symbols symbols are distinguished by their use in describing the machine status rather than serving explicitly as input data. Hopcroft and Ullman include the empty symbol, □, as a control symbol. However, they have simultaneously listed it as a separate component.

-

State transitions are gated by the value read from the tape. Each state transition is bound to an actions to be taken; hence, this Turing Machine definition describes a Mealy style state machine. The step action can be in either direction, but taking a step is mandatory. The write action must be specified, but the written symbol can be the same symbol that is read, making it effectively an optional action.

+

State transitions are gated by the value read from the tape. Each state transition is bound to an action to be taken by the machine; hence, this Turing Machine definition describes a Mealy style state machine. Structurally, this action specifies two distinct instructions. First, it is mandatory that exactly one of the two step instructions, left or right, be issued. Second, a write(σ) instruction must also be specified, though the written symbol can be the same symbol that is read, making the write operation effectively optional.

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, and to wrap motion at the dividing cell, and is otherwise undetectable. The transformation has a small constant effect at the dividing cell, and otherwise multiplies the step count formula by two, which do not affect big O results. Hence, the single ended tape machine is a computation theoretic inconsequential variation of the two way tape machine.

@@ -656,11 +656,11 @@

The specific architectural modifications are as follows:

  1. There is one unified alphabet Σ to which both status symbols and data symbols belong.
    2. -
  2. The machine utilizes a Moore-style programmed state controller, so that actions can be managed separately from state transitions.
    3. +
  3. The machine utilizes a Moore-style programmed state controller, with zero or one instruction specified per state, so that instructions are independent and managed separately from state transitions.
  4. The machine separates control flow from data flow:
    1. Two registers exist within the machine: one for holding a symbol upon which control decisions are made, the s (status) register; and one for holding data upon which decisions are not based, the d (data) register.
      2. -
    2. Write and read actions are given an operand designating the target or source register respectively, either s or d.
      3. +
    3. Write and read instructions are given an operand designating the target or source register respectively, either s or d.
  5. The machine implements default state transitions that execute when no explicit transition is given in the main state transition table of triples (each triple being \langle q_i, σ, q_{i+1} \rangle): @@ -690,7 +690,7 @@

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

    +

    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 instruction, 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

    @@ -708,7 +708,7 @@

    The state controller always starts in the QF·initial state. This is a symbol representing the state; it is not a register that holds a state. The 'F' values are all fixed.

    -

    The programmer cannot add actions to the machine definition, so there are no aliasing issues here:

    +

    The programmer cannot add instructions to the machine definition, so there are no symbol aliasing issues here:

    \begin{aligned} @@ -763,7 +763,7 @@ \mathit{ΣP}
    -

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

    +

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

    \mathit{ΛP} = \{ \langle q_i, a \rangle, \dots \}
    @@ -819,13 +819,13 @@ Σ = \mathit{ΣF} \cup \mathit{ΣP} -

    All members of the set of available actions are fixed:

    +

    All members of the set of available instructions are fixed:

    A = \mathit{AF}
    -

    The table of state-action pairs is strictly programmed.

    +

    The table of state-instruction pairs is strictly programmed.

    Λ = \mathit{ΛP}
    @@ -858,16 +858,15 @@

    Programmed control stage

    -

    Phase 1: The action

    -

    During the action phase, the executor looks up the operation mapped to the current state.

    +

    Phase 1: Instruction issue and execution

      -
    1. Locate the current state q within the actions table Λ.
      2. -
    2. Perform the associated action λ.
      3. +
    3. Given the current state q, lookup the instruction λ, within the instruction table Λ.
      4. +
    4. Perform the instruction λ.
    -

    If the action is left and the machine walks off the tape, the machine hangs.

    +

    If the instruction is left and the machine walks off the tape, the machine hangs.

    Phase 2: The state transition

    -

    Following the completion of the action, the executor evaluates the next state by cascading through the ordered sequence of transition rules Δ = [Δ_0 \mid Δ_1 \mid Δ_2 \mid Δ_3]. The evaluation follows this hierarchy, stopping and branching at the first valid match. Upon not finding a next state transition, the machine hangs.

    +

    Following the completion of the instruction, the programmed controller evaluates the next state by cascading through the ordered sequence of transition rules Δ = [Δ_0 \mid Δ_1 \mid Δ_2 \mid Δ_3]. The evaluation follows this hierarchy, stopping and branching at the first valid match. Upon not finding a next state transition, the machine hangs.

    Halting stage

    If, after the state transition phase completes, the current state is a member of H, the machine halts. Otherwise, the execution continues from the programmed control stage.

    @@ -875,7 +874,7 @@

    The TTCA Machine 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 the 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(s), placing the value into the status register. 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.

    +

    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) instruction, placing the value into the 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(s), placing the value into the status register. Because instructions 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 @@ -1369,7 +1368,7 @@ 
    -                                [ Action ]
+                               [ Instruction ]
                     +-----------------------------------+
                     | q0    q1    q2    q3    q4    q5  |
                 Src | ( )   ( )   ( )   ( )   ( )   ( ) |
@@ -1398,7 +1397,7 @@
                     +-----------------------------------+
    -

    The top panel has two toggle switches. One turns the machine on, and the other selects run or single-step mode. Immediately to the right of the two toggles are indicator lights. To the right of the indicator lights are two push buttons. One is for reset, which sends the machine back to state q_0, and the other is for stepping the machine when it is in single-step mode. This panel also has an error indicator light which will illuminate if no next state is specified for a state transition, and thus the machine is hung.

    +

    The top panel has two toggle switches. One turns the machine on, and the other selects run or single-step mode. Immediately to the right of the two toggles are indicator lights. To the right of the indicator lights are two push buttons. One is for reset, which sends the machine back to state q_0, and the other is for stepping the machine when it is in single-step mode. This panel also has an error indicator light which will illuminate if no next state is specified for a state transition, and thus the machine is hung, or if a head walks off the end of a tape.

    The second section is the state transition panel. At the top of this panel are the state indicator lights and a row of halting toggles; if flipped closed, the corresponding state becomes a halting state. Below this is the transition condition matrix, consisting of holes that fit the banana plug ends of a patch cord. Each column corresponds to a current state, and each row corresponds to a status symbol.

    @@ -1408,7 +1407,7 @@

    To program the controller, the programmer connects the patch cords. For example, routing a patch cord from the (q_2, s_2) intersection to the q_3 destination hole physically realizes a conditional state transition arc for the controller for the tripple \langle q_2, s_2, q_3 \rangle. If the active status value has no patch cord plugged in at the specific state intersection, the machine evaluates the status default column. If that hole is also empty, the machine utilizes the state default transition hole for the current state. Finally, if no patch cord is plugged in across any of the prior layers, the global default patch cord located at the def intersection is followed.

    -

    Below the transition panel are the action selection and symbol selection panels. To enforce the rule that each state executes exactly one action, each state column on the action panel features a single source hole at the top. The programmer routes a patch cord from this source hole down to the desired action row. If the selected action requires a symbol argument, such as write('σ'), a similar routing is performed on the bottom symbol selection panel. Note that this describes the control panel for a single-head, single-TTU machine. Additional patch options would be required to add a TTU device specifier and a head specifier within each TTU.

    +

    Below the transition panel are the instruction selection and symbol selection panels. To enforce the rule that each state executes exactly one instruction, each state column on the instruction panel features a single source hole at the top. The programmer routes a patch cord from this source hole down to the desired instruction row. If the selected instruction requires a symbol argument, such as write('σ' ,σ), a similar routing is performed on the bottom symbol selection panel. Note that this describes the control panel for a single-head, single-TTU machine. Additional patch options would be required to add a TTU device specifier and a head specifier within each TTU.

    The machine block diagram

    @@ -1450,7 +1449,7 @@
    1. One-hot q register
    2. Next State Table
      3. -
    3. Action Table
      4. +
    4. Instruction Table
  6. Data bus
    7. @@ -1461,15 +1460,15 @@

    As described in the computation theoretic section that is being used as the architectural template, the executor guides the machine through the initialization, programmed control, and halting stages of execution. The Executor contains the power, reset, and clock logic. It has two modes of execution: the run mode in which the clock runs free, and the single-step mode, in which clock pulses are sent with the push of a button. It also holds the halt state switch bank, and is ready to stop the clock when a halt state is reached. When in the programmed control stage, most of the active control comes from the CPCU.

    -

    The CPCU contains the current state register q, the Next State Table, and the Action Table.

    +

    The CPCU contains the current state register q, the Next State Table, and the Instruction Table.

    -

    The output of the Action Table provides primary control of the running machine. Its output determines which of the TTUs will be active and which head in the TTU is to be used. The machine has an internal data bus. The output of the Action Table also determines which TTU register will drive that bus, and which register will receive data from the bus.

    +

    The output of the Instruction Table provides primary control of the running machine. Its output determines which of the TTUs will be active and which head in the TTU is to be used. The machine has an internal data bus. The output of the Instruction Table also determines which TTU register will drive that bus, and which register will receive data from the bus.

    The register file contains two registers, s and d. Both can receive values from the internal data bus or drive values onto that bus. The d register is not connected to any other units, so it can not participate in the next-state decision process. It can however, be an argument in a subsequent write instruction, causing its value to go back out on the data bus, then to an HU, and then be put back on the tape. The s register is connected directly to the Status Decode, and that in turn is connected directly to the next state logic. The s register can also drive the data bus.

    The symbols of the alphabet are enumerated such that each symbol corresponds to a specific row index on the control panel. The value of the s register is decoded, resulting in a one-hot encoding of the status symbol. This one-hot encoding then goes to the Next State Table in the CPCU and illuminates one of the rows. The q register enumerates the columns. If a patch cord is plugged into that intersection point and leads to the destination state row below, then the state selected becomes the next state for the machine.

    -

    The current state register q utilizes a one-hot encoding, allocating a discrete bit per state. A control line from each bit routes to the Halt Switch Bank within the executor, where the outputs are wire-ORed together to generate the master halt signal. Consequently, a halt condition asserts if and only if the currently active state bit corresponds to an enabled toggle in the switch bank. The output of the q register also selects a row in the Action Table, and this is key to controlling the machine.

    +

    The current state register q utilizes a one-hot encoding, allocating a discrete bit per state. A control line from each bit routes to the Halt Switch Bank within the executor, where the outputs are wire-ORed together to generate the master halt signal. Consequently, a halt condition asserts if and only if the currently active state bit corresponds to an enabled toggle in the switch bank. The output of the q register also selects a row in the Instruction Table, and this is key to controlling the machine.

    Upon reset, the current state register initializes to a one-hot configuration with the bit for state q_0 asserted, while all other machine registers clear to zero. Uncontrolled power-up could trap the machine in an illegal configuration where it would ignore subsequent reset instructions or even induce physical hardware damage. To prevent initialization hazards, the power switch incorporates a capacitor timer that maintains an active reset signal until supply voltages fully stabilize. When in run mode, the machine will begin running after reset is released. In single step mode, it will then wait for a push of the single step button.

    @@ -1481,1631 +1480,1656 @@

    The current state register, q, samples and holds on the rising edge of the clock. This then provides a stable state signal to the control panel next state matrix columns for an entire cycle. The status register, s, is the phase inverse; when enabled it samples on the falling edge of the clock and holds for an entire cycle.

    -

    On the rising edge of the clock, the new current state signal ripples through the Action Table. As the q register is stored as a one-hot value, this happens very quickly. Rather than placing instructions in the Action Table, the decoded values to be used as control signals are programmed directly into the table. Among the decoded outputs of the action instruction is a control signal that enables the status register to sample when the clock falls.

    +

    On the rising edge of the clock, the new current state signal ripples through the Instruction Table. As the q register is stored as a one-hot value, this happens very quickly. Rather than placing instructions in the Instruction Table, the decoded values to be used as control signals are programmed directly into the table. Among the decoded outputs is a control signal that enables the status register to sample when the clock falls.

    -

    A control signal from the decoded instruction coming from the Action Table then enables the selected TTU and provides it with its decoded instruction. Part of the decode will be the HU select line, and a signal to tell the HU status register to drive the machine's internal data bus.

    +

    A control signal from the decoded instruction coming from the Instruction Table then enables the selected TTU and provides it with its decoded instruction. Part of the decode will be the HU select line, and a signal to tell the HU status register to drive the machine's internal data bus.

    Thus the status register in the selected TTU and HU will be driving the data bus, and the machine s register is ready to sample the bus. Then the clock falls, the s register updates, and holds its value until the next time when it is enabled to update and the clock falls.

    The updated value in the s register then drives the Next State Table rows. The column lines stabilized earlier in the cycle, immediately after the state updated. If a patch cord is plugged in at the intersection of the row and the column, then a signal will travel through that cord to the next state row that is located below the state and status matrix. Then when the clock rises again, this signal, which is held steady by the driving status register, will be sampled and become the next state.

    -

    Then the clock rises, and the cycle repeats, though perhaps while selecting a different row from the action table, and thus performing a different instruction.

    +

    Then the clock rises, and the cycle repeats, though perhaps while selecting a different row from the instruction table, and thus performing a different instruction.

    + +

    In physical machine design, rather than triggering logic on both edges of a single clock and managing strict duty cycle constraints, designers often deploy two clocks separated by a 180-degree phase shift. This configuration, known as two-phase clocking, allows all registers to sample uniformly on a rising edge (or all on a falling edge) while permitting designers to adjust the phase separation to optimize timing margins. This approach can be used to accommodate any number of phase separated clocks. Alternatively, a single-edge-triggered clock can drive the entire control loop. In this design, the current state propagates through the instruction table, selects the driving status register in the TTU, passes through the status decoder, and resolves at the next-state matrix. Because the s and d registers are wired as appendages to this primary loop and also sample on the rising edge, the system must enforce strict hold-time requirements. This guarantees the registers capture the established state rather than the transient values newly propagating across the bus. Clocking designs that successfully maintain these operational margins across the extremes of manufacturing tolerances and thermal ranges are said to be clean.

    -

    In physical machine design, rather than triggering logic on both edges of a single clock and managing strict duty cycle constraints, designers often deploy two clocks separated by a 180-degree phase shift. This configuration, known as two-phase clocking, allows all registers to sample uniformly on a rising edge (or all on a falling edge) while permitting designers to adjust the phase separation to optimize timing margins. This approach can be used to accommodate any number of phase separated clocks. Alternatively, a single-edge-triggered clock can drive the entire control loop. In this design, the current state propagates through the action table, selects the driving status register in the TTU, passes through the status decoder, and resolves at the next-state matrix. Because the s and d registers are wired as appendages to this primary loop and also sample on the rising edge, the system must enforce strict hold-time requirements. This guarantees the registers capture the established state rather than the transient values newly propagating across the bus. Clocking designs that successfully maintain these operational margins across the extremes of manufacturing tolerances and thermal ranges are said to be clean.

    - The TTCA stored program + Address -

    Symbol in mathematics

    + +

    Unary Representation address

    - A symbol is a distinct mathematical object capable of being instantiated. Within a given context, any instance of a specific symbol evaluates as equal to any other instance of that identical symbol, and evaluates as not equal to any instance of a different symbol. + A person 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 a person were to run the Natural Number Machine and observe as it writes to the tape, that person would watch as the Natural Numbers are printed one after another: '·s·ss·sss·ssss· ...'. Here '·' represents zero, and 's·' represents one, etc. Because the Natural Number Machine never halts, the machine cannot be used to initialize a tape, but an analyzer can evaluate the machine to make conclusions about what it would write if it were run.

    - Put more formally, given a set of instantiable objects and a collection of instances made from them, for these objects to be symbols, two conditions must be met. First, it must be possible to define an instance comparison operation, denoted =, that acts as an equivalence relation to partition the collection into discrete equivalence classes. There must be a one to one correspondence between the resulting equivalence classes and the original instantiable objects from which the member instances were derived. + In contrast, a function extension version of the Natural Number sequence generator can be run. The function extension machine would be given as input a prior function extension result, or an initial empty tape. It would then modify the tape to contain the next Natural Number, as per the sequence that the Natural Number machine would write, if it could be run. This is accomplished through two subroutine calls: find_empty and increment. The find_empty machine checks the symbol under the head. Upon finding it is not the empty symbol, the machine steps right and checks the next cell, repeating until it finds the empty symbol, whereupon it halts. The increment machine then writes an 's' onto the tape and halts. Recurrent calls to the Natural Number extender then produce a sequence of result tapes: [], [s], [ss], …. Similarly, a programmer can write a machine called decrement, though the programmer must note that decrementing can return the left-of-leftmost symbol.

    - It follows from this definition that the distinct equivalence classes can be used as a proxy for the instantiable objects themselves. That is, a person can name either the instantiable object or the equivalence class, and then through this correspondence, find the other. + To say that 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 run. Conversely, if B were said to be greater than A, that would mean B occurs further to the right. It is a simple matter for a programmer to write a decider machine for this. The decider is given two input tapes for the two numbers to compare, and it keeps a head on each. It then steps forward until neither head has an 's' under it. If empty symbols are found simultaneously on both tapes, then the two numbers are equal; otherwise, the number with an empty symbol under the head is the lesser number.

    -

    Symbol in computing

    +

    + As such, a person can assign a Natural Number to each cell of a given tape by using a mechanical procedure. Given a machine, say P, and an address machine, say A_P, each time P is stepped right, a call is made to run increment on A_P. Similarly, each time P is stepped left, a call is made to run decrement on A_P. In this manner the tape on A_P will always hold the address that machine P's head is on. +

    - In the context of real machines, the symbol itself can be defined as a factory that produces symbol instances. A new symbol instance of the given symbol is then made, say, by calling the factory's make function. All of the symbol instances made by the factory constitute the members of the corresponding equivalence class. + The Natural Number found on A_P is then called the address for the cell that machine P's head is on. As each increment and decrement of the address is a constant time operation, keeping the address of the cell the head is on is computationally inconsequential.

    - A symbol instance newly minted by the factory is said to come direct from the factory. A symbol instance direct from the factory is also called an original. + An address space is a set of addresses for contiguous cells. The tape's address space is the set of addresses for all the cells on the tape. Typically the address of 0 is given to the leftmost among the contiguous cells.

    -

    Required properties of symbol factories

    + +

    Binary Arabic representation address

    - Any two symbol instances returned directly from two distinct factories will always evaluate to False during an equality comparison. In other words, two distinct originals will always be not equal. + Would it be computationally consequential if binary Arabic representation were used instead of unary for addresses? For unary representation each increment was constant time, but with Arabic addresses, increments have a carry. Would the carry cause stepping to the right, combined with calling the address machine, to become slower and slower as the machine steps further and further?

    - Given an original, all copies stemming from it will be equal to each other and to the original. By stemming from, this definition includes all direct copies and copies of copies. + For this discussion, the Arabic representation address is variable precision, so it will grow as the count becomes larger. The empty symbol will serve as the terminator.

    - Given any two originals, say A and B, it is established that A is not equal to B, as discussed above. Note also that A is not equal to any copy stemming from B, and B is not equal to any copy stemming from A. + For Arabic_increment, the machine reads the cell under the head; upon finding a 0 or the terminator, it writes a 1 and halts. Upon finding a 1, it writes a 0, steps right, and repeats the procedure.

    + + increment: + a = TTU.read() + if a == 0 or a == □: + TTU.write(1) + halt + TTU.write(0) + TTU.step() + goto increment + + +

    Here TTU is the tape transport unit. It has the number to be incremented mounted on it. This number is either zero, which would mean the leftmost cell is empty, or it is of the same form as a result from a Natural Number extension machine. A TTU.read places a copy of the symbol instance found in the cell under the head into the read buffer automatically when the machine enters a new state on the programmed controller, so it is not counted as a step. In contrast, the other actions are associated with the state of the programmed controller, so when the machine arrives at a write, step, or halt node, it means that the programmed state controller has taken a step. Sequential instructions mean unconditional next state choices, whereas an if signals a conditional next state choice. The if condition is a logical proposition based on the read symbol.

    + +

    The loop form here is worth taking note of, as it will come up again. The controller executes a first action, that of a read, followed by a middle break test, and then the recursive form actions.

    +

    - Though symbol instances are integer like in that copy and equality comparison operations can be used with them, symbol instances are disallowed from being used with other integer operators. Symbols cannot be compared for greater than or less than; they cannot be incremented, added, nor subtracted, etc. + Each row shows an input tape, and actions taken to write the result tape. For any given row, the result tape is the same as the input tape on the next row down. The table lists 7 increments, which is sufficient to reach the maximum count that can be held by a 3 bit counter.

    -

    Instance implementation

    + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
    inputactioncost (steps)
    0write 1, halt (result is maximum 1 bit count)2
    1 write 0, step, write 1, halt4
    01write 1, halt (result is maximum 2 bit count)2
    11write 0, step, write 0, step, write 1, halt6
    001write 1, halt2
    101write 0, step right, write 1, halt4
    011write 1, halt (result is maximum 3 bit count)2
    111

    - Within a process, a reference to the factory can be used as a symbol instance, which will cause the factory to become trivial. Making a new instance will merely require copying the factory reference, and there will be nothing in memory that the base factory reference is pointing to. + The number of programmable controller state transition steps required to reach a maximum 1 bit, 2 bit, and 3 bit count are: [2, 8, 22]. Note these are cumulative. The three bit maximum count cost includes that of the two bit maximum count cost, etc. Each maximum count is exponentially larger, so a better measure is the average cost per step: [2/1, 8/3, 22/7] = [2, 2.667, 3.143]

    - In general, memory addresses are built in symbol instances, hence within the context of a single process run, a program can make use of these symbols. However, this diminishes the size of the address space and leaves the memory at those addresses unused. A common hedge is then to use references into a dictionary, where the data looked up in the dictionary is the name of the symbol. + For an n bit counter, the sequence of costs follows a pattern. Half of the increments evaluate one bit (costing 2 steps), a quarter evaluate two bits (costing 4 steps), an eighth evaluate three bits (costing 6 steps), and so forth, over the 2^n - 1 increments required to reach the maximum n bit count:

    + \sum_{k=1}^{n} 2k · 2^{n-k} = 2^{n+2} - 2n - 4 +

    - Such symbol names are non structural strings, so they do not need to follow the rules of symbols. For example, a program written where references to strings were used as symbol instances, could give multiple, or all, strings the same name, and the program would function. Conventionally, the names are made to be distinct so as to avoid confusion. The hazard here is that a programmer will then conflate the string name with the symbol instance, and perform symbol operations with it. + To find the average cost per increment to reach each maximum, an analyst divides by the total number of increments, which is 2^n - 1:

    + \text{Average Cost} = \frac{2^{n+2} - 2n - 4}{2^n - 1} = \frac{4(2^n-1)+4-2n-4}{2^n-1} +

    - An alternative implementation is to have the factory return an integer value. Each factory has a base integer that is distinct from that of other factories. Calling make then returns the base integer. + This simplifies algebraically to:

    + \text{Average Cost} = 4 - \frac{2n}{2^n - 1} +

    - As another alternative, each factory can be given a base string, and then make returns a copy of the base string. Here we refer literally to the string as the symbol instance. There is no separate name, and the string data, not the reference to the string, becomes the symbol instance. This is however merely an architectural constraint, under the hood an implementation could use string references as long as it always appears to the programmer that the string value is being used. + As the address space grows, the bit width n increases. The polynomial term 2n is outpaced by the exponential denominator 2^n - 1, causing the fractional terms to converge to zero. The average work done by the machine head converges to exactly four tape actions per increment. Constant time, same as for unary. This is a surprising counter intuitive result.

    - At the time of this writing many machines use 64 bit words. This is equivalent to 8 ASCII characters, while the average size of an identifier is about 5 characters. Hence the approach of using a string as a symbol might not be as inefficient as it seems to be at first. Using strings has advantages. Symbol instances can carry semantic clues for the programmer. There is no hazard of conflating the string instance with the name, as they are the same. Also, a string instance will have integrity across contexts, such as between invocations or when passed between processes (note the section below on crossing context boundaries). A drawback is in cases there is no language support, the strings are typically ad hoc so the guarantee of distinctness becomes merely a contract with the programmer. + Consequently, maintaining an Arabic address on a secondary Address Machine remains a constant time operation in the amortized sense, making it computationally inconsequential to the complexity class of the base machine. However, if a problem were to increment and decrement repeatedly around a binary power count, the behavior would be the limiting logarithmic time due to the length of the counter. An unlucky situation like this is called aliasing.

    -

    Distinctness across contexts

    -

    - If a symbol persists across contexts (such as across scopes or processes), it must remain distinct from all other symbols in its new context. + The model used here to define an address is analogous to keeping a pointer into memory. Each step then increments or decrements the pointer. Conventional processors do the converse of the Turing Machine model presented here. For a processor, the address is the base object, while the head location is what is implied by the address. On processors, pointers will be one word in width. In small geometries where computation element delay dominates, two operand adders tend towards logarithmic complexity evaluation times against bit width, and the constants are small. Because of this, it is practical to perform word width addition operations atomically in one machine cycle. In fact, for some machines, the adder time likely sets the clock period. Such an adder will be used for address arithmetic; consequently, a programmer cannot arrange a program to expose aliasing in the address increment time to the real world. It remains a theoretical observation.

    - One way to meet this requirement is to find a scope encompassing both contexts and to place the symbol factory there. Another solution is to give each context a distinct root symbol and to use an array of symbols in place of the imported symbol. Yet another approach is to associate an imported symbol with a new symbol in the given new context using a correspondence map. + An address is sent on a trip through the memory hierarchy to locate the corresponding memory cell, ultimately landing on a memory decoder over a physically implemented memory. Address decoders resemble carry chains, and they also have logarithmic physical evaluation times as word width grows. Hence, a fixed width word holding an address gets decoded in approximately constant time measured in clock ticks. However, the trip through the memory hierarchy is not negligible.

    - When utilizing memory addresses as symbols in a virtual memory environment, the convention is to disallow addresses in one process from being used in another. If that isolation is insufficient, it is often adequate to use indexes instead of addresses, taking the address to the base of the data structure. Though the absolute address of the data structure might differ across contexts, the relative offset remains constant. Another approach is to reserve memory address blocks and to guarantee imported pages have the exact same addresses as before, though they might be imported sequentially to reuse the memory block. In architecture, this is generally known as the pointer swizzling problem. + Direct address decoding operates independently of reference locality. This fundamentally differs from a Turing Machine head, which incurs a linear computation cost strictly proportional to the distance traveled. However, direct decoding is only the base of the memory hierarchy.

    -

    Symbol copy consequentiality

    -

    - Copying symbol instances is an integral part of the operation of the Turing machine. Typically the programmed control steps are used as a cost metric for running a program. Such steps integrate operations of copying symbols to and from the tape. Thus from a pure step count perspective the cost of the symbol copy is inconsequential, not due to any behavior of a symbol copy, but rather due the symbol copy being subsumed within the definition of the step.

    -

    - However, this is feels unsatisfactory. Here we are tying to build a bridge from computation theory to architecture, and thus we want a step to be a constant time occurrence at least in the average, or at least approximately. To model the symbol copy time, a symbol could be copied a tranche of bits per step, thus giving the copy a step count. Then, if symbols were to grow in tranche count as a program ran longer, then symbol copy of ever longer symbols would be computationally consequential. + It is possible that decoding occurs separately in a row and column manner, and changes in the lower bits of the address walk a buffered row that was found in a prior access. This makes access to neighbor cell addresses within a row a low expense operation. However, this depends on memory implementation. One layer up, it is common for memory to be made of interleaved banks, so neighbor access that remains in the leaf collection is generally faster than that which requires fetching a new leaf set.

    - Fortunately, the Turing Machine is defined with a finite alphabet and a couple of additional symbols. As these are part of the machine definition, and thus do not change at run time, there is no growth in size, and the time to copy them is inconsequential. + There will, however, be a more dominant effect. For programs with islands of locality of reference, instructions or data will be discovered in a cache. Caches bring in two types of locality: that of access within a cache line, which makes neighbor walks that stay in the line fast, and cache line prefetch and replacement policies, which assume for any given fetch address that a subsequent fetch will be nearby in memory. These effects lead to similar memory behavior as a head on tape, where a single step to a neighbor is faster than taking many steps to find memory further away, but there is not a one to one correspondence.

    - On a real machine, the factory would be used to make the data alphabet and a couple of additional symbols. As these are set up before the machine runs, and thus before we count steps, these actions are computationally inconsequential. + Memory accesses into the processor local memory file are even faster. If locality of reference, even in an abstract sense, remains tight, then memory cells can be accessed in a minimal amount of time.

    -

    Alphabet

    +

    + For programs with large memory footprints and sparse memory access patterns, the dominant factor becomes the virtual memory subsystem. Here locality again comes into play as the translation lookaside buffer provides stateful location context, and the neighbor relationship between pages is sometimes taken into account for performance reasons. However, once a program starts performing at virtual memory page fetch times instead of cache access, or even local system memory access times, the program is said to be page thrashing, and it becomes very slow. It is also possible for small programs to have memory access patterns that alias against the memory subsystem's heuristics and lead to page thrashing. For a typical system, a programmer can write a small program to demonstrate this. +

    - An alphabet is another name for 'a set of symbols'. Because it is simply a set, an infinite number of distinct alphabets can exist, and a set of symbols could be finite or infinite.

    + In summary then, using Arabic representation for addressing is not statistically computationally consequential. On the other hand, the idea of using a decoded address in place of a tape head raises computational model issues. So much so that it would not be an exaggeration to say that the very goal of modern computer architecture is to ensure that, within an execution context, address decode does not become computationally consequential. Architects employ a memory hierarchy to do this, and that memory hierarchy rewards locality of reference, but access times are not linear in time relative to distance from prior access. Instead they are clumped into a constant time access abstract concept of locality groups where the time to access each group grows exponentially with the distance from the processor. +

    -

    For a Turing machine there are a fixed number of alphabets that are all finite. The set of data symbols, control symbols, and controller state name symbols, are all finite and set in advance. +

    + Let us put this into perspective. Suppose in ancient Roman times that a clock tick for a computer was scaled to be one day long, so that the action involves sending letters rather than variable values. Under this scale, a single nanosecond of real world execution time equates to three days. Suppose a program initiated a read request for a location in memory on the Ides of March, the date when Caesar was assassinated on -0043-03-15. Surely that was a big day for posting letters. The following table provides the historical date that the variable value would finally be loaded into the processor, depending on the memory tier being accessed:

    -

    Symbol implementation examples

    + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
    Memory TierReal World LatencyScaled DelayScaled Arrival EraHistorical Context
    L1 Cache Hit1 ns3 days-0043-03-18Three days after the assassination.
    DRAM (Main memory)100 ns300 days-0042-01-09Nearly a year later, during the Liberators' civil war.
    NVMe SSD Page Swap15 µs45,000 days0080123 years later, exactly as the Colosseum is completed in Rome.
    SATA SSD Page Swap100 µs300,000 days0778821 years later, during the reign of Charlemagne and the Frankish Empire.
    Magnetic HDD Page Swap10 ms30,000,000 days82092Tens of thousands of years in the future, long after current human civilizations are dust.

    - The enum of C is used to make alphabets of named symbols. Each entry in the enum is a static symbol factory, and instances are distinct integers. + In computer architecture, there is a rule that the slower the access time, the larger the amount of data that should be transferred. The idea is then that of access time per bit, instead of access time per fetch. A common example given is that of a station wagon of hard drives driven across the country. Andrew S. Tanenbaum famously coined this concept in his 1981 textbook Computer Networks, stating: "Never underestimate the bandwidth of a station wagon full of tapes hurtling down the highway." This physical data transfer method is universally referred to as a sneakernet. Ten terabits, at three days, equates to 26 nanoseconds per bit. Not bad, if a user can wait three days to continue the program, but aliasing between data sets would make a program very slow. The Turing Machine model does not capture the effects of clumped data accesses.

    - - /* The enum definition acts as the factory. */ - typedef enum { - SYMBOL_EMPTY = 0, - SYMBOL_ZERO = 1, - SYMBOL_ONE = 2, - SYMBOL_A = 3, - SYMBOL_B = 4 - } TapeAlphabet; - - /* Instantiating copies of the symbols: */ - TapeAlphabet cell_1 = SYMBOL_A; - TapeAlphabet cell_2 = SYMBOL_A; - /* Equality comparison over instances */ - if(cell_1 == cell_2){ - /* Evaluates to True */ - } - + + Area and partitioning

    - The enum is a static alphabet made by the compiler, where symbol instances are integers. In the following example, the alphabet is made dynamically, where each symbol instance is a string pointer. + We call a subset of contiguous cells from a tape an area. An area with a single cell is called a singleton, one with two cells is called a pair. An area has a leftmost cell and a rightmost cell. For a singleton area, those will be the same cell.

    - - #include <string.h> - #include <stdlib.h> - #include <stdio.h> +

    The left neighbor cell to the leftmost cell of a given area is considered to be the left neighbor cell to the area. Similarly, the right neighbor cell to the rightmost cell of a given area is considered to be the right neighbor cell to the area. If the given area is located at the left end of the tape, then it has no left neighbor cell. If the given area is open on the right, then it has no right neighbor cell. +

    - // maximum legal index into the symbol list - #define LIST_EXTENT 3 +

    A tape partition is a set of areas that completely span a tape. For any partition of a single ended Turing Machine tape, at least one of the areas will necessarily be infinite. +

    - typedef const char *Instance; - typedef struct{ - Instance *head; - Instance *tail; - Instance *extent; - } List; +

    Head partition

    - static List SYM_LIST = {NULL ,NULL ,NULL}; +
      +
    1. The left side: The finite set containing all of the cells to the left of the head cell.
      2. +
    2. Head: the head cell.
      3. +
    3. The right side: the infinite set containing all the cells to the right of the head.
      4. +
    - Instance make_list(const char *name){ - size_t size = LIST_EXTENT + 1; - SYM_LIST.head = (Instance *)malloc( size * sizeof(Instance) ); - SYM_LIST.tail = SYM_LIST.head; - SYM_LIST.extent = SYM_LIST.head + LIST_EXTENT; - *SYM_LIST.head = strdup(name); - return *SYM_LIST.head; - } +

    If the head is on the leftmost cell, there is no left side area.

    - Instance make_symbol(const char *name){ - if(!SYM_LIST.head) return make_list(name); +

    Leftmost/remaining partition

    - Instance *pt = SYM_LIST.head; - while(1){ - if( strcmp(*pt ,name) == 0 ) return *pt; +
      +
    1. Leftmost: the leftmost cell.
      2. +
    2. Remaining: the infinite set including the right neighbor of the leftmost cell, and all cells further to the right.
      3. +
    - if(pt == SYM_LIST.extent){ - fprintf(stderr ,"symbol list overflow for %s\n" ,name); - return NULL; - } +

    Active area partition

    - if(pt == SYM_LIST.tail){ - *++SYM_LIST.tail = strdup(name); - return *SYM_LIST.tail; - } +

    + A nonempty tape, one with at least one cell holding an alphabet symbol, can be partitioned into the following areas: +

    - pt++; - } - } +
      +
    1. The left empty tail: if the leftmost cell of the tape is an alphabet cell, there is no left empty tail. Otherwise, it consists of the leftmost cell and the empty cells, if any, to the right of the leftmost cell, up to, but not including, the first alphabet cell.
      2. - int main(){ - Instance a = make_symbol("a"); - Instance b = make_symbol("b"); - Instance c = make_symbol("c"); - Instance d = make_symbol("d"); - Instance e = make_symbol("e"); // overflows table +
    2. Active area: a finite area for computational problems, containing the cells extending from the leftmost alphabet cell up to and including the rightmost alphabet cell. It is possible that the leftmost alphabet cell and the rightmost alphabet cell will be the same cell.
      3. - Instance *pt = SYM_LIST.head; - Instance *pt_tail = SYM_LIST.tail; - while(1){ - puts(*pt); - if(pt == pt_tail) break; - pt++; - } +
    3. The right empty tail: the infinite set extending from the right neighbor of the rightmost cell of the active area, extending rightward.
      4. +
    - if(e == NULL) printf("e is NULL\n"); - } -     +

    + A noncomputational tape is one that cannot be initialized by a Turing Machine, but can still be surmised to exist, perhaps in analysis due to its properties. The empty tape is an example. The tape holding the Natural Numbers is another example. For noncomputational tapes that have the property that the active area is open on the right, there is no right empty tail. +

    -

    Property

    +

    Area implied partition

    - A property is a pair, where the components are called the name and the value. A name is an instance of a symbol and it must uniquely identify the property within its context. The value is a variable that can be written then read back. + The existence of a finite given area implies a three area partition: the left side, the given area, and the right side. If the given area is located at the left end of the tape, there is no left side area. If the given area is open on the right, there is no right side area.

    -

    Dictionary and reference

    +

    The impossibility of recognizing an empty tape

    -

    A dictionary is a property context object. It is a set of properties, where a property may be selected from the set given its name, which is a symbol instance. The corresponding property value is then the referenced object.

    +

    + Recognition is a process where a Turing Machine decides if a pattern is present on a tape solely by reading symbols found on the tape. No meta information, such as a message communicating something about the area being examined or the nature of the program that wrote the symbols, can be taken into account. +

    -

    A reference is a dictionary key which uniquely identifies a property in the dictionary. A dictionary is also known as a symbol table. In hardware design, the symbols are often unsigned integers, AKA Natural Numbers, and a symbol table is implemented using an array that is indexed into using the key.

    +

    + The active area partition of a tape only works for tapes that have at least one alphabet cell. As soon as a machine does its first write of an alphabet symbol, it is known the tape has at least one alphabet symbol. However, what if a tape of unknown status, whether completely empty or containing an alphabet cell, is mounted on a tape machine, and it is desired that the machine recognize if the tape is empty or has an alphabet cell? This is the equivalent problem of looking for the leftmost cell of an active area. +

    -

    Any programming object that holds other objects is a container, whereas a dictionary is a specific type of key access container.

    +

    + Recognizing that a tape is empty is generally impossible. Suppose it were attempted, and a machine started scanning the tape rightward from the leftmost cell; for every cell that is discovered to be empty, the machine would have to scan further rightward to check for an alphabet cell. If the tape is truly empty, the recognizer would never stop scanning, so no decision would ever be rendered. +

    -

    A Turing Machine tape cell

    +

    The impossibility of recognizing the rightmost cell of the active area

    - A cell is the square from Alan Turing's 1936 paper Alan M. Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem," Proceedings of the London Mathematical Society s2 42, no. 1 (1936): 230 265.. Mathematically, a cell is a referencable distinct identifiable set, with one to three property members depending on the type of cell. + In general, a Turing Machine cannot step across a tape reading cells to recognize the rightmost cell of the active area, or equivalently, the leftmost cell of the right empty tail. Suppose a recognizer attempted this by starting in the active area and stepping right, and the machine discovered an empty cell. The machine would be unable to distinguish between the case of said empty cell being embedded within the active area (meaning more alphabet cells lie further to the right), or the case where said cell is genuinely the leftmost cell of the right tail. To resolve the ambiguity, the machine would be obligated to continue stepping right. Yet, there would never come a time where finding another empty cell would avoid leading back to the exact same case ambiguity, so the machine would forever step right without returning a decision.

    - 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'. + It follows that if knowledge of the end of the active area is needed, this information must be encoded as a message. For example, a special symbol can be reserved in the alphabet specifically to serve as the end of active area marker. Each time a machine steps beyond the current end of active area marker and does a write, it writes the marker in the right neighbor cell, and goes back and erases the old mark. This method is related to communications theory and the science of signaling. Here, the active area marker is an out-of-band control signal.

    - The value of a neighbor property is a non-null single reference to a cell. The value of a data property is strictly an instance of an alphabet symbol, or alternatively, an instance of the empty symbol. + If a tape is written by an initializing tape machine, unmounted, and then mounted on a second analyzing tape machine, the analyzing tape machine is starting with a populated tape. Similarly, a mathematician can, by decree, define an initial tape that holds predefined alphabet symbols. In such a scenario, the initializing machine and the analyzing machine must use a shared communication protocol for signaling the end of the active area. They cannot operate independently or the analyzing machine would not be able to find the end of the active area. This shared protocol then represents information held by a mediator, said mediator could be used at a higher level to write the control for the two machines, or it could be consulted when the two machines are run. Hence, the mediator is either an author, or a service provider, or possibly both.

    -

    Tape

    -

    - 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. + By definition, a computation must finish in a finite number of steps. It follows that the active area when a Turing Machine halts a computation will always be finite. Consequently, if a Turing Machine initially starts working with a tape that was computed by another Turing Machine, the length of the input will be finite. Still, that input will be in the active area, so the receiving Turing Machine will need to read control data left on the tape under a common communication protocol to be able to find the bounds of the input area.

    - To say that a tape is infinite, and to simultaneously require that any cell can be reached in a finite number of steps, means that after reaching said cell, there will always be further cells to the right. Consequently, though any cell can be reached in finite hops starting at the leftmost cell, a finite traversal of the tape can not visit all of the cells. This seeming contradiction is at the very heart of the definition of the countable infinity in mathematics. + When an input tape is provided as a general mathematical object, either decreed by definition or perhaps abstracted from 'what a Turing Machine computation would produce in the limit of step count', then the input can be either finite or infinite.

    +

    In band and out-of-band control

    +

    - In conventional computation theory, once a tape is defined, the cell neighbor properties values are fixed. Cells don't move, new cells cannot be added, and cells existing on the tape cannot be removed. This fits the definition of a space, so we can say that a Turing Machine tape has a constant, fixed, linear topology. This permanence of cells matches the reality of hardware memories. On the other hand, it does not track well with general memory containers such as linked lists where destructive operations are often permitted. + Because of the impossibility of recognizing certain tape features, when a tape is written by one Turing Machine, then used by another, there must be some sort of system for messaging control. There are two approaches for mixing data and control together: one is in band signaling, while the other is out-of-band signaling.

    - Nor can a cell data property be removed; however, unlike for cell neighbor property values, the cell data property value can be changed while the Turing Machine is running. In fact some people would say this is the whole point of running a Turing Machine. + In band control occurs when control signals or structural metadata are mixed directly into the same channel and alphabet as the data payload. In band signaling leads to ambiguities between what is control and what is data. As we saw, there are cases where a recognizer, i.e., merely examining the data, is completely incapable of resolving even the simplest of control questions. A conventional approach for resolving these ambiguities makes use of escape sequence schemes that grow in length as the levels of communication grow. This has always been an afterthought, a sort of hack.

    - An empty tape is filled with empty symbols. However, as we noted above, a Turing Machine cannot visit all the cells on a tape, so a Turing Machine cannot erase a tape in advance for another Turing Machine to use. Say a Turing Machine tried to erase a tape by writing the empty symbol, then stepping right, then repeating. At some point it must halt. When it halts some number of cells will have been written with the empty symbols, but there will be further cells to the right of the cell the machine halted at, which have not yet been erased. So for example, if a machine wrote 10 cells with the empty symbol, then it might be the case that the prior user of the tape had written data to 11 of the cells. Without historical knowledge the eraser machine can not know where to stop. So here we see another meaning of infinity, it speaks to the situation of not having historical knowledge. And thus, we are left to decree into existence an empty tape, or as the mathematicians say, empty tapes are available by definition. + In contrast, out-of-band control communicates structural information through a strictly separate channel or by utilizing symbols definitively excluded from the programmer visible data alphabet. The rightmost tape marker is an out-of-band mechanism because it utilizes an expanded hardware tape alphabet strictly reserved for machine management, guaranteeing it can never be conflated with the user's data. Modern architectures often lack the luxury of inventing new symbols to serve as control rather than data. Another out-of-band signaling technique is to structure the data into channels; such structure is called formatting. We find formatting on hard drives, in frame based and packet based communication channels, and in data structures.

    -

    - Mathematically, a Turing Machine tape is a specialized path graph. The neighbor properties are the edges. In this special form, properties are attached to the edges. A Turing Machine has a clock based state controller. Taking a step is an atomic operation. The machine is either in state q_i or in state q_{i+1}, there is no mathematical meaning given to the concept of during a step, which is why no properties are added to the edges of the tape path graph. This is not to say that some analysis of a Turing Machine program won't take pairs of nodes from the path graph and give them meaning, thus effectively giving properties to the arcs. However, this would not be part of the machine definition, such a program must go through the additional effort of making node pairs, because the machine itself does not provide the program with a feature for attaching properties directly to the neighbor property itself.

    +

    Virtual cells

    -

    An example of a non-Turing tape like model is the Emacs vertical line cursor model, where a cursor is said to be between characters. An ASCII file offers no such feature as 'in between' characters. Like a Turing Machine tape, a medial character in an ASCII file has a left neighbor and a right neighbor character. Any attempt to represent an in between cursor within the file itself would require inserting more characters into the file under the same model of every medial character having a left and a right character. Consequently, though emacs presents a model where cursor is located in between two characters, this model is only due to the interpretation of the functions' actual effects presented to users in the documentation. For example, instead of saying a cursor is located upon a character, and that inserting a character inserts the character to the right of the given character, the manual gives the description that the new character is inserted at the cursor location, where said cursor is in between the given character and its right neighbor. Thus the documentation presents the user with one model, which by necessity of using standard library calls to work with files, is built upon another model.

    +

    A given finite area that is not sitting on the end of the tape will have a left neighbor area and right neighbor area that are not in the area. If the given area is sitting on the end of the tape there will be no left neighbor area. If the area is open on the right, there will be no right neighbor area.

    - - Computational Analysis +

    Now imagine we define a Turing Machine such that when it steps right, it steps to the right neighbor area, and when it steps left, if there is a left area, it steps to that, otherwise it returns a left-of-leftmost symbol. The read instruction reads all of the cells in the area, and similarly the write instruction writes them all. Then for this machine the areas are virtual tape cells. +

    -

    Definition

    +

    An example of this from conventional computing is where memory is accessed in units of bytes, but a program works with units of words.

    -

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

    Virtual tape

    + +

    As established, the Turing Machine head transport returns a distinct left-of-leftmost symbol when stepping left off the end of the tape. The programmed controller, the statement machine, then uses an arc defined specifically for this symbol. It is a distinct symbol that cannot be written to the tape.

    -

    - In computation theory, computational analysis is defined as the static evaluation of a formal system or machine definition to deduce its absolute boundaries and properties. This process remains entirely distinct from dynamically executing the machine to yield a computed result. +

    Various portions of this text have mentioned calling a Turing Machine as a subroutine. This is described as unmounting the tape from the calling machine, mounting it on the subroutine machine, running the subroutine machine until it halts, then unmounting the tape from the subroutine machine, and mounting it back on the calling machine. However, this would be a manual process. To automate the process, we use a Universal Turing Machine. It has the definition for the calling machine and the subroutine machine on its tape. We can add an additional tape to the machine to hold the stack. Then a subroutine call happens much as it does in conventional software.

    +

    A gasket machine is actually a set of subroutines with one corresponding to each of the tape transport instructions. +

    +

    - This analytical perspective has been present from the very beginning of the field. Alan Turing's formulation of the halting problem relies explicitly on one machine examining another. To properly evaluate the limits of this analytical capacity, the examining machine must necessarily be given definitions of programs that loop infinitely. Consequently, the foundational proofs of computer science formally establish non computational programs as legitimate objects of analytical study. + There is a small problem, in that the left-of-leftmost symbol was stipulated as being separate from the alphabet, and only alphabet symbols and the empty symbol can be written to the tape. There are a couple of possible solutions. One solution is to add a symbol to the alphabet that is also taken to mean 'left of leftmost', say gasket-left-of-leftmost. Then machines that make use of gaskets can recognize this new symbol for its meaning. Another alternative, that will be used for the remainder of our discussion, is to define a separate control alphabet of symbols that are distinct from data alphabet symbols, but can also be written and read from the tape. We will add to this alphabet, empty, left-of-leftmost, and a new control symbol used by gaskets,right-of-rightmost.

    +

    Now suppose defining a Turing Machine that initially has the head on the leftmost cell of a specific area. When step left is called, the tape transport immediately returns the left of leftmost symbol, independent of whether the area is actually at the physical left end of the tape or not. +

    +

    - We call a program that examines another program so as to deduce properties of its results an analyzer. The program or machine definition being subjected to this evaluation is called the studied program or studied machine. +Now suppose defining a Turing Machine that initially has the head on the leftmost cell of a specific area. When step left is called, the tape transport immediately returns the left of leftmost symbol, independent of whether the area is actually at the physical left end of the tape or not.

    -

    - Turing Machines that halt in a finite number of steps for any finite input within a stipulated domain are said to be computational over that domain. +

    Suppose further that this area is finite. If the machine attempts to step right from the rightmost cell of this finite area, the tape transport returns, in analogy, right-from-rightmost symbol. Such a machine defines a virtual tape over an area.

    +

    Partitions on a finite virtual tape

    +

    - By definition, first order analysis is the running of programs, and it has its place. - Generally, when we want to know what output a computational machine will produce, the fastest route to this knowledge is to run the program. Most programs written to solve problems are most effectively run to solve those problems rather than analyzed to deduce what they will produce. + When a Turing Machine operates on a finite virtual tape, the structural logic of the partitions established earlier must be updated to reflect the absolute rightward boundary.

    -

    - Now suppose we quantify the inputs to a computational machine over a domain and want to know a property of the machine. Perhaps, say, that it always produces an even number. If the quantification is over a large set, then it might be faster to study the machine than it would be to run the machine on every input in the domain while checking its output. +

      +
    1. For the Head partition and Area implied partition, the right side is no longer infinite. It is a finite set containing all cells extending from the right neighbor of the head (or area) up to the absolute rightmost cell of the virtual tape. If the head (or area) includes the rightmost cell of the virtual tape, the right side set does not exist.
      2. +
    2. For the Leftmost/remaining partition, the remaining area is now a finite set terminating at the rightmost cell of the virtual tape.
      3. +
    3. For the Active area partition, the right empty tail is similarly a finite set extending to the rightmost boundary of the virtual tape. If the rightmost alphabet cell occupies the rightmost cell of the virtual tape, the right empty tail does not exist.
      4. +
    + + + Metrics + +

    Address defined area

    + +

    We defined a tape as having a single feature, that of a leftmost cell, along with a linear neighbor topology. When a tape is mounted it gains a second feature, that of the cell the head is on. The leftmost cell was fixed in place, while any other single cell on the tape can be featured as the cell the head is on. When we introduced areas, we picked up two new features, that of the leftmost cell of the area, and the rightmost cell of the area. Again, those features could coincide with the former features. We noted that the features partitioned a tape thus defining more areas, and more features.

    - Further suppose that the quantification is over an infinite input space. Then the only option for answering a question about the properties of results from such a machine is to analyze it. This is second order analysis, also called simply analysis. + When cells were defined we noted that they were sets, and that these sets had identity and could be referred to. We needed that to be the case so as to build the tape topology using neighbor properties. Had the tape been singly linked, perhaps we could have used the cells to represent themselves in the properties, but when we doubly linked it, a given cell had to appear in two places, as the right neighbor of its left neighbor, and the left neighbor of its right neighbor, so we stipulated the sets as being identifiable. Initially we did not say how they would be identified. This is common in mathematics, but we soon cleared this up by formalizing the concept of a symbol.

    - Famously, we know that universally an analyzer cannot determine if a machine is computational. This knowledge was derived by reasoning about the properties of a hypothetically existing analyzer machine. This is a third order analysis activity. + When discussing symbols we noted they could be natural numbers, and even went so far as to point out that addresses were symbols, though we had not yet defined them. They are familiar to anyone involved in computing, so again, it did not present a serious problem. Here we have now formalized them.

    - 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. + So we now have two means for identifying a feature. One means is to state its address, and the other is to put a tape machine head on it.

    +

    As we noted in the section discussing area, an area has two distinguishing features, being that it has a leftmost cell, and a rightmost cell. That definition is topological. If we start with the leftmost cell of a tape, we are either already on the leftmost cell of a defined area, or we can step right to find it. At the point of finding it we know this leftmost cell is part of the area, then we are either already on the rightmost cell, or we can continue to step right on cells in the area until we find the rightmost cell in the area. The right neighbor of the rightmost cell in the area, and all cells to that right of that, are excluded from the area. +

    -

    Second order Arithmetic

    +

    With addresses we can now define an area with two addresses, two natural numbers, the address of the leftmost cell, and that of the rightmost cell. All natural numbers greater than or equal to the address of the leftmost cell, or less than or equal to the address of the rightmost cell, are addresses of cells that are in the area. This feels more satisfactory for most of us, as now we are talking about arithmetic rather than graph topology. Though should the topology of the tape be generalized, this could become limiting. It reminds me of Frege's admonition that perhaps math should be built on top of geometry. +

    -

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

    Distance and extent

    + +

    The distance between two cells is the absolute difference in their addresses. When we talk about the distance between the leftmost cell of an area and the rightmost cell of an area, we call this number the area's extent.

    + +

    In an analogous manner to defining an address space for a tape, we can define an address space for an area. Accordingly, the leftmost cell of the area is assigned address zero, and the address increments cell by cell going to the right. A finite area will have a finite address space, with the address of the rightmost cell being the largest address in the address space. +

    + +

    It is interesting that the extent of an area will be the same, whether it is calculated from the address space of the tape, or the address space of the area. In fact, the extent will always be identical to the largest address in the address space. We will use the Greek symbol omega, \omega, to symbolize an extent. We can give it a subscript with the name of an area if the correspondence is not already clear. The choice of \omega makes sense here because \omega is an inclusive bound, i.e. it is the rightmost letter included in the Greek alphabet. Thus it is the extent of the Greek alphabet. +

    + +

    Length

    + +

    If cells in an area are transacted, the cost of the area is the cost of a cell multiplied by the count of cells. Vincent Atanasoff probably found himself needing to know such a count when ordering capacitors. The count of cells in an area is also known as the area's length. We will use the Greek symbol Ï¡, pronounced as sampi, to refer to the length. The length of an area, the count of its cells, will always be one greater than its extent, Ï¡ = \omega + 1. This symbol makes sense here, as the Greek number system fell short of letters, so the symbol Ï¡ was tacked on to the end of the alphabet, but did not belong to the alphabet. +

    + +

    The count of cells in an area, the length of an area, and the cardinality of the address space for an area are all the same number, Ï¡. The extent of an area, \omega, is an address in an area's address space, whereas the cardinality of an area, Ï¡, falls outside it. This has implications. Because extent is an address, extent and addresses can always use the same number representation. In contrast, there is no such guarantee for cardinality, Ï¡. Take for example an area that contains 256 cells. The addresses run from zero to 255, and all can be represented with an 8 bit binary number. However, the number 256 requires 9 bits, and thus would not fit in an 8 bit address register. This one of the reasons that code will have fewer end case problems when expressing the size of objects with extents, rather than with lengths. +

    + +

    Is the cardinality of an open on the right area a Natural Number?

    + +

    So we find an interesting situation with the cardinality of an address space for an area that is open on the right. It goes like this.

    + +

    How cardinality is computed

    + +
      +
    1. We set Turing Machine P with its head on the leftmost cell of an area. We mount the initial tape, '·', on the A machine.
      2. +
    2. We step P and simultaneously run the A machine. Stepping stops when P reaches the rightmost cell of the area. At this point, the tape on the A machine holds the address space extent.
      3. +
    3. The A machine is run an additional time. The output on the tape is defined to be the cardinality of the address space, aka the cardinality.
      4. +
    + +

    Lemma 1, the A machine produces Natural Numbers

    + +

    This follows from its definition; it is literally the increment from the Natural Numbers Machine.

    + +

    Lemma 2, cardinality is a natural number

    + +

    Cardinality is produced by repeatedly calling the A machine, and the A machine produces Natural Numbers.

    + +

    Lemma 3, cardinality is not in the address space

    + +

    At the end of the second step in the procedure for producing the cardinality, the tape of the A machine held the extent of the address space. Then in step 3, A was called again, thus leaving a number one larger than the extent on its tape. The extent is the largest number in the address space, hence cardinality is larger than all numbers in the address space. Thus cardinality is not in the address space.

    + +

    Lemma 4, the address space of an open on the right area is identical to the Natural Numbers.

    + +

    Composing the A machine with an unterminated loop call, where each result is written to a tape with a terminator between entries, results in the same machine as the Natural Numbers Machine.

    + +

    The apparent contradiction.

    + +

    By Lemma 2, cardinality is a Natural Number. By Lemma 3 cardinality is not in the address space. By Lemma 4 the address space is identical to the Natural Numbers.

    + +

    Resolution

    + +

    The resolution lies in the computational reality of Step 2. For an area that is open on the right, the stepping of machine P never halts. Because Step 2 never terminates, Step 3 is never executed. The A machine never runs that final, additional time. Therefore, the cardinality of an open area is never actually produced by the machine. In the language of Computational Naturalism, Lemma 2 is false for an infinite area; the cardinality of an open on the right area is excluded from being a Natural Number because a Natural Number Machine cannot reach it in the first order.

    + +

    So then can we add a property to cardinality, such that a second order analysis could use this property to continue downstream analysis? In short we could say that cardinality has no first order value, but it has a second order one. This is analogous to inventing a new type of number, analogous to a complex number with a second component. I.e., there is no 'real' solution, but there is an 'imaginary' one. Or analogous to error algebra, where a number value is replaced with a rule on how to handle downstream operations when it is given as an input. +

    + +

    Such a value would be a new Turing Machine, one that composes a call to the never halting Natural Number machine followed by an increment operation. It cannot be run, but it perfectly explains the situation to an analyst. Perhaps we name this machine \aleph_0.

    +

    What if extent was used instead of cardinality?

    +

    - 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. + Had extent been used instead of cardinality, we would lack the final increment step in the three step computing procedure. However, step 2 still cannot complete. Rather than a value, the result of the second order analysis would be a machine that produces ever larger Natural Numbers. We can call this machine \aleph_{-1}.

    - 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 instructions: (step), (left), (read), and (write symbol). In the first order, evaluating these instructions physically actuates the tape. + Now here is an interesting result:

    + + \aleph_{0} - \aleph_{-1} = 1 + +

    - 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: + Neither machine can be run. However we can compose the two machines, then simplify the composition. When we do so, the ever larger Natural Number machines annihilate each other, and the increment machine remains. The increment machine can be run, so we end up with an output value.

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

    Similarly, the AST for the number 3:

    +

    Size

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

    Consider the case of a partitioned tape. Then consider that we write a gasket, such that we have a higher level Turing Machine that considers each of the areas of the partition as a cell. So then, initially the Turing machine starts with its head on the leftmost area, stepping right steps to the right neighbor area etc. In this manner we abstract the concept of a cell to areas. A length then becomes a count of areas; however the size remains a count of the cells. Something similar is done in the C language, where the length of an array is a count of the elements in the array, but the size of the array is a count of bytes. A byte being an addressable unit in physical memory, and thus the underlying cell that everything is built up from.

    + + + The Universal Turing Machine + +

    The Computer Theoretic model chapter provided symbolic definitions for the Turing machine and the TTCA variation. Those definitions were written as strings of characters, which the reader scanned, and presumably understood. Furthermore we explained in detail how an executor could make use of those definitions so as perform input string transformations. I proposed in the text that the executor could be a person, say a student, and in the text also described how a machine could execute the transformations automatically.

    + +

    In his original paper Alan Turing put these things together and explained that a Universal Turing Machine could read the definition of a Turing Machine from tape, and thus be a Turing Machine executor. Hence, say, a Turing Machine reads the symbolic definition of a Turing Machine from one tape, and then automatically performs the described input string transformations on another tape. Said Universal Turing Machine would then be chameleon like, performing the function of any other Turing Machine so described on the first tape.

    + +

    The only information that the first tape of a Universal Machine need contain is the variable part, \mathit{MP}, which we called the program, as the remainder of the definition is common to all machines and can thus be built into the controller. \mathit{MP} describes a state controller, it lists the states, the symbols of the alphabet, the instruction to be issued from each state, the symbol gated next state transitions, and the halting state. The universal machine control program would then have to interpret that information and send the universal machine through the same steps that a human executor would take while running the described machine.

    + +

    However, the controller can be simplified if the program encoding is changed from the raw definition. Notice that the only information that leaves the state controller while it runs are the instructions issued per state, with that list terminating when the controller reaches the halt state.

    + +

    Imagine then, mounting a tape on a given machine, running the machine, and recording the instructions that leave the controller up until it halts. Then taking that list of instructions, and the same input tape, and mounting them on a Playback Machine. The Playback Machine then takes the instructions from the list on the first tape and issues them out of its own controller one by one. The playback controller is quite simple. Though of course, this approach has the drawback of having to run the given machine first so as to observe it, thus making the playback run moot.

    + +

    Consider then, adding a jump table instruction. To create the program first examine the state diagram for the controller. Take all the sequential state runs, even those of length 1, from the controller, and list their instructions in the same sequence order. Wherever a state has next state transition arcs based on the value of the status register, insert jump table instruction, so that it jumps to the appropriate instruction sequence.

    + +

    Take for example the TTCA machine two headed string reverse example, this procedure produces the following instruction sequence:

    + + + + + + + + Software + +

    Symbol in mathematics

    - 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. + A symbol is a distinct mathematical object capable of being instantiated. Within a given context, any instance of a specific symbol evaluates as equal to any other instance of that identical symbol, and evaluates as not equal to any instance of a different symbol.

    - 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) instruction with an inverted pair: a (left) instruction followed by writing the empty symbol (write □). + Put more formally, given a set of instantiable objects and a collection of instances made from them, for these objects to be symbols, two conditions must be met. First, it must be possible to define an instance comparison operation, denoted =, that acts as an equivalence relation to partition the collection into discrete equivalence classes. There must be a one to one correspondence between the resulting equivalence classes and the original instantiable objects from which the member instances were derived.

    - - (defun invert-direction (cmds) - (cond - ((null cmds) nil) - ( - (and - (cdr cmds) - (equal (first cmds) '(write s)) - (equal (second cmds) '(step))) - (append - '((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) - ))) - - -

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

    - - - (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) - ;; (left) (write □) - ;; (left) (write □) - ;; (left) (write □) - ;; ) - -

    - 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. + It follows from this definition that the distinct equivalence classes can be used as a proxy for the instantiable objects themselves. That is, a person can name either the instantiable object or the equivalence class, and then through this correspondence, find the 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. -

    +

    Symbol in computing

    - 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. + In the context of real machines, the symbol itself can be defined as a factory that produces symbol instances. A new symbol instance of the given symbol is then made, say, by calling the factory's make function. All of the symbol instances made by the factory constitute the members of the corresponding equivalence class.

    - - (defun remove-annihilations (cmds) - (cond - ((null cmds) nil) - ( - (and - (cdr cmds) - (equal (first cmds) '(step)) - (equal (second cmds) '(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)) - ))) - - - -

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

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

    This technique of composing Turing Machine programs in the presence of simplification is closely related to that of symbol computation and expression simplification that we find in math tools such as Mathematica. We can imagine our Turing Machines as functions with names, and then symbolic computation leaves them unevaluated as here. Then the Mathematica Simplify is the compiler optimization simplifier as above. A difference in these two systems is that of the functions being reduced to Turing Machine head and tape transport unit instructions.

    - -

    The multiplicative inverse of the additive identity

    -

    - Generally it is more efficient to perform arithmetic in the first order. Also, it is easier to write Turing Machine control programs if we take Natural Number arithmetic as already available, say, from a subroutine library. On processors fixed word length arithmetic is built into the hardware. Where second order computation becomes useful is in places where a result cannot be computed in the first order. + A symbol instance newly minted by the factory is said to come direct from the factory. A symbol instance direct from the factory is also called an original.

    -

    - The IEEE 754 floating point standard includes error algebra tags. These are explored in depth by Popova, Evgenija D. "On a Formally Correct Implementation of IEEE Computer Arithmetic." Journal of Universal Computer Science 1, no. 7 (1995): 560 569. This is a form of second order arithmetic, because each of the error tags is standing in for a machine that did not complete. When a computation fails to result in a first order object, this becomes a gateway for replacing the result with a second order object. -

    +

    Required properties of symbol factories

    - Let us take the multiplicative inverse of the additive identity as an example, AKA division by zero. In the second order, when we divide, say 6/0, the machine will not reduce. It will return a second order value: + Any two symbol instances returned directly from two distinct factories will always evaluate to False during an equality comparison. In other words, two distinct originals will always be not equal.

    - - (divide 6 0) - - -

    Now consider the compiler optimization like simplification of this expression:

    - - - (divide (divide 6 0) (divide 3 0)) - - -

    The result will be:

    - - - (multiply 2 (divide 0 0)) - -

    - There is no special help here. Hence, (divide 0 0) remains as an error flag. + Given an original, all copies stemming from it will be equal to each other and to the original. By stemming from, this definition includes all direct copies and copies of copies.

    - The divide machine cannot be run to produce a value, as any value from the field assigned to it would lead to contradictions. Stated more precisely, for x · y = q operations, when given an x and a q value, there is only one possible y value, and it can be recovered with q/x. However, when x is zero, and only when it is zero, q is solely determined by x independent of y, so y is ignored; it could be any value. There is no way to recover it from q/x. + Given any two originals, say A and B, it is established that A is not equal to B, as discussed above. Note also that A is not equal to any copy stemming from B, and B is not equal to any copy stemming from A.

    -

    Evaluating and Extending

    -

    - When a machine is 1) programmed to perform a function f, 2) has its tape initialized with a constant input value, say t (which can be a vector of values), and 3) is then run, writing the result f(t) and halting; we say that the run evaluates the function at t. + Though symbol instances are integer like in that copy and equality comparison operations can be used with them, symbol instances are disallowed from being used with other integer operators. Symbols cannot be compared for greater than or less than; they cannot be incremented, added, nor subtracted, etc.

    -

    - When an evaluator erases the input and leaves only the result in its place, we say it is a substitution evaluator. It is an inconsequential modification to add multiple tapes each with their own tape head to a Turing Machine, so it is possible that an evaluator will have a dedicated tape for the input, a dedicated tape for the output, and have zero or more additional tapes for scratch work. In which case, instead of substitution, one tape is mounted as an input, the machine is run until it halts, and then separately the result tape can be unmounted to potentially be used in a downstream computation. -

    +

    Instance implementation

    - In a variation of analytical evaluation, we can instead mount an initial value for a function, and call a machine to repeatedly extend the function. To state this more precisely, when a machine tape is given the initial value of f(t_i) on its input tape, and then when run until it halts having written the result f(t_{i+1}) to the tape, we say that running the machine extends the function. Typically extension machines are designed so they can be used recurrently to extend the function indefinitely, thus producing a sequence of function values, f(t_0), f(t_1), f(t_2), \ldots. + Within a process, a reference to the factory can be used as a symbol instance, which will cause the factory to become trivial. Making a new instance will merely require copying the factory reference, and there will be nothing in memory that the base factory reference is pointing to.

    - The difference between adjacent function values in the above sequence is called the first finite difference. The forward first difference is defined as: - δ_i = f(t_{i+1}) - f(t_i). - While the backwards first difference is - δ_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. + In general, memory addresses are built in symbol instances, hence within the context of a single process run, a program can make use of these symbols. However, this diminishes the size of the address space and leaves the memory at those addresses unused. A common hedge is then to use references into a dictionary, where the data looked up in the dictionary is the name of the symbol.

    - A second difference can be defined as the difference between two adjacent first differences. A second difference can be added to a prior first difference to create the next first difference, which could then be added to a prior function value to extend the function to its next value. This pattern can be extended to any number of levels. + Such symbol names are non structural strings, so they do not need to follow the rules of symbols. For example, a program written where references to strings were used as symbol instances, could give multiple, or all, strings the same name, and the program would function. Conventionally, the names are made to be distinct so as to avoid confusion. The hazard here is that a programmer will then conflate the string name with the symbol instance, and perform symbol operations with it.

    - The mechanical application of finite differences was famously leveraged by Charles Babbage in the design of his Difference Engine. By examining the discrete changes between consecutive outputs of a polynomial function, a person can observe that the higher order differences eventually reduce to a constant. This structure allows the computation of subsequent sequential values using only addition, bypassing the need for complex multiplication machinery. + An alternative implementation is to have the factory return an integer value. Each factory has a base integer that is distinct from that of other factories. Calling make then returns the base integer.

    - Let us construct a forward difference pyramid for the polynomial f(t) = t^2. + As another alternative, each factory can be given a base string, and then make returns a copy of the base string. Here we refer literally to the string as the symbol instance. There is no separate name, and the string data, not the reference to the string, becomes the symbol instance. This is however merely an architectural constraint, under the hood an implementation could use string references as long as it always appears to the programmer that the string value is being used.

    - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
    Count (t)f(t) = t^21st Diff (δ^1)2nd Diff (δ^2)
    0012
    1132
    2452
    397
    416
    -

    - In order to design for indefinite extension, the Turing Machine tape must retain the function value alongside with its forward differences. Because the second difference is constant higher order differences are all zero. Hence the tape requires a three component vector to hold the differences. + At the time of this writing many machines use 64 bit words. This is equivalent to 8 ASCII characters, while the average size of an identifier is about 5 characters. Hence the approach of using a string as a symbol might not be as inefficient as it seems to be at first. Using strings has advantages. Symbol instances can carry semantic clues for the programmer. There is no hazard of conflating the string instance with the name, as they are the same. Also, a string instance will have integrity across contexts, such as between invocations or when passed between processes (note the section below on crossing context boundaries). A drawback is in cases there is no language support, the strings are typically ad hoc so the guarantee of distinctness becomes merely a contract with the programmer.

    +

    Distinctness across contexts

    +

    - 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. + If a symbol persists across contexts (such as across scopes or processes), it must remain distinct from all other symbols in its new context.

    - - Initial Tape (t=0): [0, 1, 2] - Call 1 (t=1): [1, 3, 2] - Call 2 (t=2): [4, 5, 2] - Call 3 (t=3): [9, 7, 2] - Call 4 (t=4): [16, 9, 2] - -

    - For Call 1, the input tape is the Initial Tape. In Call 1 the machine will take the function value on the input tape, 0, and add the first difference, 1, writing the result 1, to the result tape. The machine will then continue on and take the first difference on the input tape, 1, and add the second difference on the input tape, 2, writing the result first difference to the result tape, 3. Then finishing up, the machine will not find a third difference on the input tape, so it will copy the second difference found on the input tape as the second difference for the result tape. + One way to meet this requirement is to find a scope encompassing both contexts and to place the symbol factory there. Another solution is to give each context a distinct root symbol and to use an array of symbols in place of the imported symbol. Yet another approach is to associate an imported symbol with a new symbol in the given new context using a correspondence map.

    - For Call 2, the input tape is the result tape from Call 1. Execution then proceeds identically to Call 1. This pattern repeats for all successive calls. A person can see the values of t^2 as the first number on each result tape. Any polynomial can be computed in this manner, and the only ALU required is an adder that is also capable of subtraction. + When utilizing memory addresses as symbols in a virtual memory environment, the convention is to disallow addresses in one process from being used in another. If that isolation is insufficient, it is often adequate to use indexes instead of addresses, taking the address to the base of the data structure. Though the absolute address of the data structure might differ across contexts, the relative offset remains constant. Another approach is to reserve memory address blocks and to guarantee imported pages have the exact same addresses as before, though they might be imported sequentially to reuse the memory block. In architecture, this is generally known as the pointer swizzling problem.

    -

    Lemma: Only row 0 is needed

    +

    Symbol copy consequentiality

    - The extension function can be called any number of times when the initial tape is identical to row 0 of the table of finite differences. No other row is needed from the table of finite differences. + Copying symbol instances is an integral part of the operation of the Turing machine. Typically the programmed control steps are used as a cost metric for running a program. Such steps integrate operations of copying symbols to and from the tape. Thus from a pure step count perspective the cost of the symbol copy is inconsequential, not due to any behavior of a symbol copy, but rather due the symbol copy being subsumed within the definition of the step.

    +

    + However, this is feels unsatisfactory. Here we are tying to build a bridge from computation theory to architecture, and thus we want a step to be a constant time occurrence at least in the average, or at least approximately. To model the symbol copy time, a symbol could be copied a tranche of bits per step, thus giving the copy a step count. Then, if symbols were to grow in tranche count as a program ran longer, then symbol copy of ever longer symbols would be computationally consequential.

    - This follows from the mechanical procedure given above for computing the next row of the table from any given row. + Fortunately, the Turing Machine is defined with a finite alphabet and a couple of additional symbols. As these are part of the machine definition, and thus do not change at run time, there is no growth in size, and the time to copy them is inconsequential.

    -

    Lemma: Evaluating call \omega requires an initial tape populated with components 0 through \omega of row 0

    -

    - Let the extent refer to the maximum index for accessing a component of a vector; the extent is often denoted as \omega. Performing extensions to calculate the function value at call \omega makes use of the initial tape up to index \omega, or as many nonzero values as are available up to that extent. + On a real machine, the factory would be used to make the data alphabet and a couple of additional symbols. As these are set up before the machine runs, and thus before we count steps, these actions are computationally inconsequential.

    -

    - To make this precise, let us define the difference vector at call k as D_k. The components of this vector are D_{k, 0}, D_{k, 1}, \ldots up to the maximum available difference. The first component, D_{k, 0}, is the function value itself. The component D_{k, 1} is the first difference, and so on. -

    +

    Alphabet

    - Thus, this lemma claims that to compute D_{\omega, 0}, the highest component index accessed from the initial tape vector D_{0, i} will be i = \omega. -

    + An alphabet is another name for 'a set of symbols'. Because it is simply a set, an infinite number of distinct alphabets can exist, and a set of symbols could be finite or infinite.

    -

    - Note that to compute the D_{k, 0} result by the mechanical procedure given above requires adding the input tape first difference to the prior difference. That is, D_{k, 0} = D_{k-1, 0} + D_{k-1, 1}. Hence we see immediately the lemma holds for the first call where k = \omega = 1. +

    For a Turing machine there are a fixed number of alphabets that are all finite. The set of data symbols, control symbols, and controller state name symbols, are all finite and set in advance.

    -

    - For an arbitrary k value we discovered that the highest index required of the D_{k-1, i} vector is i=1. - The value D_{k-1, 1} is computed from our mechanical procedure as - D_{k-1, 1} = D_{k-2, 1} + D_{k-2, 2}. Given we already know that to compute the value merely requires the prior value and first difference, we find that the largest index needed from vector D_{k-2, i} is 2. -

    +

    Symbol implementation examples

    - There is a strict linear progression here. The computation of any component D_{k, i} inherently requires D_{k-1, i} and D_{k-1, i+1}. Therefore, each step backwards in time k expands the required index i by exactly one. By induction, computing the base value D_{\omega, 0} at call \omega requires tracing back \omega steps to the initial tape at k=0, which forces the maximum accessed index to be 0 + \omega = \omega. Thus, the highest required component from the initial tape is D_{0, \omega}. + The enum of C is used to make alphabets of named symbols. Each entry in the enum is a static symbol factory, and instances are distinct integers.

    -

    - The exact algebraic composition of this mechanical expansion is formalized by Newton's calculus of finite differences Isaac Newton formalized this interpolation method in 1675, later published in his Methodus Differentialis (1711). For a comprehensive foundational treatment, see George Boole, A Treatise on the Calculus of Finite Differences (Cambridge: Macmillan and Co., 1860), Chapter II.. Instead of executing the machine incrementally, a person can calculate the function value at call \omega directly as a linear combination of the initial tape components using Newton's forward difference formula: -

    + + /* The enum definition acts as the factory. */ + typedef enum { + SYMBOL_EMPTY = 0, + SYMBOL_ZERO = 1, + SYMBOL_ONE = 2, + SYMBOL_A = 3, + SYMBOL_B = 4 + } TapeAlphabet; + + /* Instantiating copies of the symbols: */ + TapeAlphabet cell_1 = SYMBOL_A; + TapeAlphabet cell_2 = SYMBOL_A; + + /* Equality comparison over instances */ + if(cell_1 == cell_2){ + /* Evaluates to True */ + } +

    - D_{\omega, 0} = \sum_{j=0}^{\omega} \binom{\omega}{j} D_{0, j} + The enum is a static alphabet made by the compiler, where symbol instances are integers. In the following example, the alphabet is made dynamically, where each symbol instance is a string pointer. +

    + + + #include <string.h> + #include <stdlib.h> + #include <stdio.h> + + // maximum legal index into the symbol list + #define LIST_EXTENT 3 + + typedef const char *Instance; + typedef struct{ + Instance *head; + Instance *tail; + Instance *extent; + } List; + + static List SYM_LIST = {NULL ,NULL ,NULL}; + + Instance make_list(const char *name){ + size_t size = LIST_EXTENT + 1; + SYM_LIST.head = (Instance *)malloc( size * sizeof(Instance) ); + SYM_LIST.tail = SYM_LIST.head; + SYM_LIST.extent = SYM_LIST.head + LIST_EXTENT; + *SYM_LIST.head = strdup(name); + return *SYM_LIST.head; + } + + Instance make_symbol(const char *name){ + if(!SYM_LIST.head) return make_list(name); + + Instance *pt = SYM_LIST.head; + while(1){ + if( strcmp(*pt ,name) == 0 ) return *pt; + + if(pt == SYM_LIST.extent){ + fprintf(stderr ,"symbol list overflow for %s\n" ,name); + return NULL; + } + + if(pt == SYM_LIST.tail){ + *++SYM_LIST.tail = strdup(name); + return *SYM_LIST.tail; + } + + pt++; + } + } + + int main(){ + Instance a = make_symbol("a"); + Instance b = make_symbol("b"); + Instance c = make_symbol("c"); + Instance d = make_symbol("d"); + Instance e = make_symbol("e"); // overflows table + + Instance *pt = SYM_LIST.head; + Instance *pt_tail = SYM_LIST.tail; + while(1){ + puts(*pt); + if(pt == pt_tail) break; + pt++; + } + + if(e == NULL) printf("e is NULL\n"); + } + + +

    Property

    + +

    + A property is a pair, where the components are called the name and the value. A name is an instance of a symbol and it must uniquely identify the property within its context. The value is a variable that can be written then read back.

    +

    Dictionary and reference

    + +

    A dictionary is a property context object. It is a set of properties, where a property may be selected from the set given its name, which is a symbol instance. The corresponding property value is then the referenced object.

    + +

    A reference is a dictionary key which uniquely identifies a property in the dictionary. A dictionary is also known as a symbol table. In hardware design, the symbols are often unsigned integers, AKA Natural Numbers, and a symbol table is implemented using an array that is indexed into using the key.

    + +

    Any programming object that holds other objects is a container, whereas a dictionary is a specific type of key access container.

    + +

    A Turing Machine tape cell

    +

    - Because the binomial coefficient \binom{\omega}{j} evaluates to exactly zero for any integer j > \omega, the summation naturally truncates at index \omega. This algebraic property perfectly mirrors the physical boundary established by the machine execution trace. Furthermore, the relationship is symmetric. A person can compute the specific components of the initial tape, D_{0, n}, directly from the sequence of evaluated function calls, D_{k, 0}, using the alternating binomial sum: + A cell is the square from Alan Turing's 1936 paper Alan M. Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem," Proceedings of the London Mathematical Society s2 42, no. 1 (1936): 230 265.. Mathematically, a cell is a referencable distinct identifiable set, with one to three property members depending on the type of cell.

    - D_{0, n} = \sum_{k=0}^{n} (-1)^{n-k} \binom{n}{k} D_{k, 0} + 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'.

    - As a consequence of this lemma, we know that for any finite number of calls, i.e. finite \omega, that a finite prefix of D_0 is used. + The value of a neighbor property is a non-null single reference to a cell. The value of a data property is strictly an instance of an alphabet symbol, or alternatively, an instance of the empty symbol.

    -

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

    +

    Tape

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

    - Taking successive finite differences reduces the degree of the polynomial by exactly one at each step. Consequently, the \omegath difference evaluates to a constant, and the next difference evaluates to exactly zero. + To say that a tape is infinite, and to simultaneously require that any cell can be reached in a finite number of steps, means that after reaching said cell, there will always be further cells to the right. Consequently, though any cell can be reached in finite hops starting at the leftmost cell, a finite traversal of the tape can not visit all of the cells. This seeming contradiction is at the very heart of the definition of the countable infinity in mathematics.

    -

    Lemma: A D_0 vector of finite extent \omega generates a polynomial function of degree \omega

    -

    - If an initial difference vector D_0 has an extent of \omega, the sequence of function values generated by the machine corresponds to a polynomial of exactly degree \omega. A person can demonstrate this by algebraically recovering the polynomial constants, a_i, directly from the initial tape components, D_{0, i}. + In conventional computation theory, once a tape is defined, the cell neighbor properties values are fixed. Cells don't move, new cells cannot be added, and cells existing on the tape cannot be removed. This fits the definition of a space, so we can say that a Turing Machine tape has a constant, fixed, linear topology. This permanence of cells matches the reality of hardware memories. On the other hand, it does not track well with general memory containers such as linked lists where destructive operations are often permitted.

    - Consider an extent of \omega = 0, forming a polynomial of degree 0, f(t) = a_0. Evaluating at t = 0 yields f(0) = a_0. Because the machine's initial value is D_{0,0}, a person establishes a_0 = D_{0,0}. + Nor can a cell data property be removed; however, unlike for cell neighbor property values, the cell data property value can be changed while the Turing Machine is running. In fact some people would say this is the whole point of running a Turing Machine.

    - When a person extends the extent to \omega = 1, the next term is added to form f(t) = a_0 + a_1 t. The first forward difference at t = 0 is D_{0,1} = f(1) - f(0) = (a_0 + a_1) - a_0 = a_1. Therefore, a_1 = D_{0,1}. Note that the addition of the linear term did not change the evaluation at t = 0; the a_0 constant remains firmly anchored to D_{0,0}. + An empty tape is filled with empty symbols. However, as we noted above, a Turing Machine cannot visit all the cells on a tape, so a Turing Machine cannot erase a tape in advance for another Turing Machine to use. Say a Turing Machine tried to erase a tape by writing the empty symbol, then stepping right, then repeating. At some point it must halt. When it halts some number of cells will have been written with the empty symbols, but there will be further cells to the right of the cell the machine halted at, which have not yet been erased. So for example, if a machine wrote 10 cells with the empty symbol, then it might be the case that the prior user of the tape had written data to 11 of the cells. Without historical knowledge the eraser machine can not know where to stop. So here we see another meaning of infinity, it speaks to the situation of not having historical knowledge. And thus, we are left to decree into existence an empty tape, or as the mathematicians say, empty tapes are available by definition.

    - Extending to \omega = 2, the polynomial becomes f(t) = a_0 + a_1 t + a_2 t^2. The second difference at t = 0 is calculated as D_{0,2} = f(2) - 2f(1) + f(0). Substituting the polynomial yields D_{0,2} = (a_0 + 2a_1 + 4a_2) - 2(a_0 + a_1 + a_2) + a_0 = 2a_2. Thus, a person recovers a_2 = D_{0,2} / 2. The lower coefficient then adjusts to a_1 = D_{0,1} - a_2. + Mathematically, a Turing Machine tape is a specialized path graph. The neighbor properties are the edges. In this special form, properties are attached to the edges. A Turing Machine has a clock based state controller. Taking a step is an atomic operation. The machine is either in state q_i or in state q_{i+1}, there is no mathematical meaning given to the concept of during a step, which is why no properties are added to the edges of the tape path graph. This is not to say that some analysis of a Turing Machine program won't take pairs of nodes from the path graph and give them meaning, thus effectively giving properties to the arcs. However, this would not be part of the machine definition, such a program must go through the additional effort of making node pairs, because the machine itself does not provide the program with a feature for attaching properties directly to the neighbor property itself.

    + +

    An example of a non-Turing tape like model is the Emacs vertical line cursor model, where a cursor is said to be between characters. An ASCII file offers no such feature as 'in between' characters. Like a Turing Machine tape, a medial character in an ASCII file has a left neighbor and a right neighbor character. Any attempt to represent an in between cursor within the file itself would require inserting more characters into the file under the same model of every medial character having a left and a right character. Consequently, though emacs presents a model where cursor is located in between two characters, this model is only due to the interpretation of the functions' actual effects presented to users in the documentation. For example, instead of saying a cursor is located upon a character, and that inserting a character inserts the character to the right of the given character, the manual gives the description that the new character is inserted at the cursor location, where said cursor is in between the given character and its right neighbor. Thus the documentation presents the user with one model, which by necessity of using standard library calls to work with files, is built upon another model.

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

    - Continuing to \omega = 3, the polynomial is f(t) = a_0 + a_1 t + a_2 t^2 + a_3 t^3. Evaluating the third difference D_{0,3} isolates the highest order term, yielding D_{0,3} = 6a_3. This allows immediate recovery of the highest constant: a_3 = D_{0,3} / 6. + In computation theory, computational analysis is defined as the static evaluation of a formal system or machine definition to deduce its absolute boundaries and properties. This process remains entirely distinct from dynamically executing the machine to yield a computed result.

    - Once a_3 is known, the shifting nature of the lower order constants becomes apparent through back substitution. The second difference equation expands to D_{0,2} = 2a_2 + 6a_3. Substituting the known a_3 allows recovery of a_2 = (D_{0,2} - 6a_3) / 2. Similarly, the first difference equation expands to D_{0,1} = a_1 + a_2 + a_3, which resolves to a_1 = D_{0,1} - a_2 - a_3. Through all of this shifting, a_0 = D_{0,0} remains entirely unperturbed. + This analytical perspective has been present from the very beginning of the field. Alan Turing's formulation of the halting problem relies explicitly on one machine examining another. To properly evaluate the limits of this analytical capacity, the examining machine must necessarily be given definitions of programs that loop infinitely. Consequently, the foundational proofs of computer science formally establish non computational programs as legitimate objects of analytical study.

    - To observe the structural integrity of this progression, a person can array these relationships into a system of equations mapping the initial tape to the polynomial constants: + We call a program that examines another program so as to deduce properties of its results an analyzer. The program or machine definition being subjected to this evaluation is called the studied program or studied machine.

    - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
    DifferenceEquation
    D_{0,0}= a_0
    D_{0,1}= a_1 + a_2 + a_3 + \ldots + a_\omega
    D_{0,2}= 2a_2 + 6a_3 + \ldots
    D_{0,3}= 6a_3 + \ldots
    \ldots\ldots
    D_{0,\omega}= \omega! a_\omega
    +

    + Turing Machines that halt in a finite number of steps for any finite input within a stipulated domain are said to be computational over that domain. +

    - A pattern emerges. Because each successive forward difference operator annihilates the lowest power of t, the resulting algebraic system is upper triangular. For any extent \omega, the \omegath difference equation reduces to D_{0,\omega} = \omega! a_\omega. This structural guarantee permits a person to reliably recover a_\omega = D_{0,\omega} / \omega!. Because an initial tape of extent \omega dictates that D_{0,\omega} is nonzero, a_\omega is guaranteed to be nonzero. All subsequent lower order constants are then systematically resolved through cascading back substitution. + By definition, first order analysis is the running of programs, and it has its place. + Generally, when we want to know what output a computational machine will produce, the fastest route to this knowledge is to run the program. Most programs written to solve problems are most effectively run to solve those problems rather than analyzed to deduce what they will produce.

    - To observe the formal mechanics of this progression, a person can alternatively array these relationships into a matrix equation mapping the polynomial constants, a_i, to the initial tape differences, D_{0,n}. The coefficients of this transformation are defined by the Stirling numbers of the second kind, denoted S(i,n): + Now suppose we quantify the inputs to a computational machine over a domain and want to know a property of the machine. Perhaps, say, that it always produces an even number. If the quantification is over a large set, then it might be faster to study the machine than it would be to run the machine on every input in the domain while checking its output.

    - - \begin{bmatrix} D_{0,0} \\ D_{0,1} \\ D_{0,2} \\ \vdots \\ D_{0,\omega} \end{bmatrix} = - \begin{bmatrix} - 0! S(0,0) & 0! S(1,0) & 0! S(2,0) & ⋯ & 0! S(\omega,0) \\ - 0 & 1! S(1,1) & 1! S(2,1) & ⋯ & 1! S(\omega,1) \\ - 0 & 0 & 2! S(2,2) & ⋯ & 2! S(\omega,2) \\ - \vdots & \vdots & \vdots & \ddots & \vdots \\ - 0 & 0 & 0 & ⋯ & \omega! S(\omega,\omega) - \end{bmatrix} - \begin{bmatrix} a_0 \\ a_1 \\ a_2 \\ \vdots \\ a_\omega \end{bmatrix} - -

    - For any extent \omega, the final row of this strictly upper triangular matrix again simplifies to D_{0,\omega} = \omega! a_\omega. + Further suppose that the quantification is over an infinite input space. Then the only option for answering a question about the properties of results from such a machine is to analyze it. This is second order analysis, also called simply analysis.

    - The main diagonal contains strictly non zero factorials, ensuring the matrix is invertible. By inverting this matrix, a person replaces the cascading back substitution with a direct, closed form equation to recover any constant a_i. The inversion utilizes the signed Stirling numbers of the first kind, denoted s(n,i) (see the Appendix on Stirling numbers). + Famously, we know that universally an analyzer cannot determine if a machine is computational. This knowledge was derived by reasoning about the properties of a hypothetically existing analyzer machine. This is a third order analysis activity.

    - a_i = \sum_{n=i}^{\omega} \frac{s(n,i)}{n!} D_{0,n} + 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

    +

    - Thus, extending this procedure \omega times definitively recovers the constants for exactly a polynomial of degree \omega. + 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.

    - This mechanical recovery of standard polynomial constants is completely analogous to Newton's interpolation formula Ibid.. Instead of resolving the standard constants a_i through an upper triangular matrix, a person can construct the polynomial directly by treating the initial tape components as the exact coefficients for a basis of binomial terms: + 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.

    - f(t) = \sum_{n=0}^{\omega} D_{0, n} \binom{t}{n} + 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 instructions: (step), (left), (read), and (write symbol). In the first order, evaluating these instructions physically actuates the tape.

    - Because the nth binomial coefficient expands into a polynomial of exactly degree n, and the summation is bounded by the finite extent \omega where D_{0, \omega} is definitively nonzero, the constructed function f(t) is structurally guaranteed to be a polynomial of degree \omega. + 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:

    -

    Difference table for an exponential function

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

    Similarly, the AST for the number 3:

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

    - Here is the table of finite differences for the function 2^t. + 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.

    - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
    Count (t)f(t) = 2^t1st Diff (δ^1)2nd Diff (δ^2)3rd Diff (δ^3)
    01111
    12222
    2444
    388
    416
    -

    - The first difference of 2^t is also 2^t, so row 0 of the table will have an infinite number of values. Fortunately, due to the lemma stating that evaluating call \omega requires an initial tape populated with components 0 through \omega of row 0, exactly those components are needed for the recurrence to proceed. Furthermore, when new values are needed, they are easily computed. A programmer need not store the entire infinite first row of the difference table on a static tape. -

    - -

    - Instead of attempting to write an infinite sequence to a physical tape, a person can encapsulate the generation logic within a dedicated Turing Machine. In the tradition of constructive arithmetic associated with Boehm, this generator machine acts as a virtual tape. When the primary extension machine requires the next difference component, it queries the generator machine, which computes and yields the value on demand. This lazy evaluation strategy elegantly handles functions with infinite difference sequences without exhausting finite memory. + 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) instruction with an inverted pair: a (left) instruction followed by writing the empty symbol (write □).

    -

    Composition of recurrence functions

    - -

    If we desire to compose recurrence functions, in the first order or the second order, the call counts must first be synchronized.

    + + (defun invert-direction (cmds) + (cond + ((null cmds) nil) + ( + (and + (cdr cmds) + (equal (first cmds) '(write s)) + (equal (second cmds) '(step))) + (append + '((left) (write □)) + (invert-direction (cddr cmds)) + )) + ( + t + (cons + (first cmds) + (invert-direction (cdr cmds)) + )))) -

    Say for example, we have a machine called fizz that adds 3 to the input on the tape, and another machine called buzz that adds 5 to the input on the tape, and we wanted to compose the two machines. We would have to define what a call to the resultant machine means to the machines in composition.

    + (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) + ))) +     -

    If one call to the resultant machine makes the equivalent of one call to the fizz, and one to buzz, the the resultant machine can be simplified to add 8 to its input tape each time it is called. In contrast if one call to the resultant machine makes the equivalent of 5 calls to fizz, and 3 calls to buzz, then the resultant machine reduces to adding 30 to the input tape per call. The two machines are very different.

    +

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

    -

    Performing operations with recurrence functions requires integrating a call algebra in addition to integrating the machines. Often this is handled by considering the machines being composed to be subroutines, and the outer controller than explicitly calls them. The call algebra can then be dynamic depending on the input. Calls can be skipped due to being inside conditionals, or performed an arbitrary number of times in loops. Though simple control structures that are static are more math like, and are more likely to be more affected by optimizations (simplifications).

    + + (defparameter + *primitive-five-minus-3-ast* + (primitive-compose-subtract *five-ast* *three-ast*) + ) -

    A pole and zero cancellation

    + ;; *primitive-five-minus-3-ast* evaluates to: + ;; '(progn + ;; (write s) (step) + ;; (write s) (step) + ;; (write s) (step) + ;; (write s) (step) + ;; (write s) (step) + ;; (left) (write □) + ;; (left) (write □) + ;; (left) (write □) + ;; ) +

    - Here we circle back to the division by zero problem, though this time while extending functions. Let us begin with the two functions, f(t) = 2^t - 32 and g(u) = u - 15. Both have D_0 vectors, though the one for the exponential function is defined by a machine rather than by a value on a tape. + 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.

    - We cannot do function based arithmetic on these until we synchronize them. Suppose that for each call of the f machine, there will be three calls to the g machine. So we can make a new machine that is called once, each time f is called, g(t) = 3t - 15. + 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.

    - Now suppose we want to express the quotient of these two functions. + 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.

    - - h(t) = \frac{f(t)}{g(t)} = \frac{2^t - 32}{3t - 15} - + + (defun remove-annihilations (cmds) + (cond + ((null cmds) nil) + ( + (and + (cdr cmds) + (equal (first cmds) '(step)) + (equal (second cmds) '(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)) + )))) - Figure singularity plot + (defun simplify-machine (ast) + (let* + ( + (cmds (rest ast)) + (reduced (remove-annihilations cmds)) + ) + (if + (equal reduced cmds) + ast + (simplify-machine `(progn ,@reduced)) + ))) + -

    - Evaluating this form in the first order at the point t=5 returns a (divide 0 0). It is a strange thing, because when we plot h(t) values, against t there is an obvious correct value on the curve at t=5. There is no special feature that would make it questionable. -

    +

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

    -

    - Suppose we move to a second order evaluation, and for places the computation does not work, we return the machine that isn't evaluating. That is similar to what we did to get (divide 0 0), but the zeros in that expression came from a prior step first order evaluation. Let us instead give the quotient composer two machines to compose, and have it return a value when reduction to the first order is possible, and return the full problem as posed to it when it can not be reduced. -

    + + (defparameter + *simplified-five-minus-3-ast* + (simplify-machine *primitive-five-minus-3-ast*) + ) - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
    Count (t)Quotient (f(t)/g(t))1st Diff Ratio (δ^1 f(t) / δ^1 g(t))
    031/151/3
    130/122/3
    228/94/3
    324/68/3
    416/316/3
    5(divide f(5) g(5))32/3
    632/364/3
    796/6128/3
    8224/9256/3
    9480/12512/3
    + ;; *simplified-five-minus-3-ast* evaluates to: + ;; '(progn + ;; (write s) (step) + ;; (write s) (step)) +     + +

    This technique of composing Turing Machine programs in the presence of simplification is closely related to that of symbol computation and expression simplification that we find in math tools such as Mathematica. We can imagine our Turing Machines as functions with names, and then symbolic computation leaves them unevaluated as here. Then the Mathematica Simplify is the compiler optimization simplifier as above. A difference in these two systems is that of the functions being reduced to Turing Machine head and tape transport unit instructions.

    + +

    The multiplicative inverse of the additive identity

    - The quotient machine, (divide f(5) g(5)), is no more representative of the value we expected here, than was (divide 0 0). However, as we have the whole program, we could pass it to a L'Hôpital evaluator and get a value back. But I am wondering if we can't design function extension form that extends to the value and beyond without any hiccups, as most apparently there is a value to extend to. + Generally it is more efficient to perform arithmetic in the first order. Also, it is easier to write Turing Machine control programs if we take Natural Number arithmetic as already available, say, from a subroutine library. On processors fixed word length arithmetic is built into the hardware. Where second order computation becomes useful is in places where a result cannot be computed in the first order.

    - 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. + The IEEE 754 floating point standard includes error algebra tags. These are explored in depth by Popova, Evgenija D. "On a Formally Correct Implementation of IEEE Computer Arithmetic." Journal of Universal Computer Science 1, no. 7 (1995): 560 569. This is a form of second order arithmetic, because each of the error tags is standing in for a machine that did not complete. When a computation fails to result in a first order object, this becomes a gateway for replacing the result with a second order object.

    -

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

    + Let us take the multiplicative inverse of the additive identity as an example, AKA division by zero. In the second order, when we divide, say 6/0, the machine will not reduce. It will return a second order value:

    + + (divide 6 0) + + +

    Now consider the compiler optimization like simplification of this expression:

    + + + (divide (divide 6 0) (divide 3 0)) + + +

    The result will be:

    + + + (multiply 2 (divide 0 0)) + +

    - Perhaps if we were performing nonstandard analysis, and extending by increments of epsilon in the domain at each step, the nonstandard analysis naturalization function would find that the differential value can be used as the value at the singularity. But here we are discussing finite differences H. Jerome Keisler, Elementary Calculus: An Infinitesimal Approach, 2nd ed. (Boston: Prindle, Weber and Schmidt, 1986).. We are not doing a local analysis here so as to derive a principle, but rather are trying to evaluate a function in the macro view. + There is no special help here. Hence, (divide 0 0) remains as an error flag.

    - So then, perhaps we set the value at the singularity to x build out the difference table, then solve for x? + The divide machine cannot be run to produce a value, as any value from the field assigned to it would lead to contradictions. Stated more precisely, for x · y = q operations, when given an x and a q value, there is only one possible y value, and it can be recovered with q/x. However, when x is zero, and only when it is zero, q is solely determined by x independent of y, so y is ignored; it could be any value. There is no way to recover it from q/x.

    - Figure with x variable. - +

    Evaluating and Extending

    - As Newton pointed out, we can know the differences on the D_0 row of the table from the quotient function: + When a machine is 1) programmed to perform a function f, 2) has its tape initialized with a constant input value, say t (which can be a vector of values), and 3) is then run, writing the result f(t) and halting; we say that the run evaluates the function at t.

    - - D_{0,n} = \sum_{k=0}^n (-1)^{n-k} \binom{n}{k} \frac{f(k)}{g(k)} - -

    - For k=5 the difference evaluates to be (divide 0 0), as it did for the quotient, and it also fails for all values above k=5 due to the summation. So we can not use this to solve for x. + When an evaluator erases the input and leaves only the result in its place, we say it is a substitution evaluator. It is an inconsequential modification to add multiple tapes each with their own tape head to a Turing Machine, so it is possible that an evaluator will have a dedicated tape for the input, a dedicated tape for the output, and have zero or more additional tapes for scratch work. In which case, instead of substitution, one tape is mounted as an input, the machine is run until it halts, and then separately the result tape can be unmounted to potentially be used in a downstream computation.

    - As the second order evaluation returned (divide f(k)|k=5 g(k)|k=5), we can use L'Hôpital evaluator to resolve this indeterminate form D_{0,5}. Note this is during the creation of the D_0 vector, so it is part of the simplification step, rather than being part of the evaluation of the quotient. The result will thus be used in producing an extension machine that extends through the singularity, so the user will not see any exceptional higher order values while extending h(t). + In a variation of analytical evaluation, we can instead mount an initial value for a function, and call a machine to repeatedly extend the function. To state this more precisely, when a machine tape is given the initial value of f(t_i) on its input tape, and then when run until it halts having written the result f(t_{i+1}) to the tape, we say that running the machine extends the function. Typically extension machines are designed so they can be used recurrently to extend the function indefinitely, thus producing a sequence of function values, f(t_0), f(t_1), f(t_2), \ldots.

    - The L'Hôpital evaluator will discover that a transcendental constant is required. It will be returned as a higher order object, a machine definition, because the value can not be written to the tape. + The difference between adjacent function values in the above sequence is called the first finite difference. The forward first difference is defined as: + δ_i = f(t_{i+1}) - f(t_i). + While the backwards first difference is + δ_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.

    - - T = \frac{32 \ln(2)}{3} - - -

    The resulting D_0 vector for the quotient is:

    - - Figure D_0 h(t) - - Figure D table for h(t) -

    - I find it fascinating to watch the transcendental difference values march down the table, then all cancel out after h(5) is generated. + A second difference can be defined as the difference between two adjacent first differences. A second difference can be added to a prior first difference to create the next first difference, which could then be added to a prior function value to extend the function to its next value. This pattern can be extended to any number of levels.

    - So the value of h(5) is transcendental, but all the machinery we were using, up until using L'Hôpital evaluator, was closed over the rational field. That is why no matter how we tried to organize the difference tables, there was no way to find h(5), or to find a D table for extending through it. This situation occurred due to introducing the 2^t function. Had we remained with finite length D tables, i.e. finite degree polynomials, we could have used deconvolution of the D_0 vectors, or synthetic division on the polynomials, to create the quotient. + The mechanical application of finite differences was famously leveraged by Charles Babbage in the design of his Difference Engine. By examining the discrete changes between consecutive outputs of a polynomial function, a person can observe that the higher order differences eventually reduce to a constant. This structure allows the computation of subsequent sequential values using only addition, bypassing the need for complex multiplication machinery.

    - -

    And for the victory lap, evaluation versus higher order computation and function extension:

    +

    + Let us construct a forward difference pyramid for the polynomial f(t) = t^2. +

    - - + + + - - - - + - - - - - - + + - - + + - - - - - - - - - - - + + + - - - - - - - + - - - + + + +
    Count (t)Direct Evaluation (f(t)/g(t))Extended Quotient Vector (H(t))f(t) = t^21st Diff (δ^1)2nd Diff (δ^2)
    031/1531/15
    0 130/1230/12
    228/928/9
    11 324/624/62
    2 416/316/3
    5(divide 0 0)\frac{32 \ln(2)}{3}
    632/332/32
    39 796/696/6
    8224/9224/9
    9480/12480/12416
    -

    Chapter discussion

    +

    + In order to design for indefinite extension, the Turing Machine tape must retain the function value alongside with its forward differences. Because the second difference is constant higher order differences are all zero. Hence the tape requires a three component vector to hold the differences. +

    -

    The fundamental claim of computational analysis is that all functions can be viewed as discrete entities. Take this simple function:

    +

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

    - f(t) = t^3 + Initial Tape (t=0): [0, 1, 2] + Call 1 (t=1): [1, 3, 2] + Call 2 (t=2): [4, 5, 2] + Call 3 (t=3): [9, 7, 2] + Call 4 (t=4): [16, 9, 2] -

    It is said to be a continuous function over the real field. However, from a computational perspective, it is a string of 8 discrete symbols. A person might ask then, "If the function is not continuous, then how can a person take a derivative?" Often people view a derivative as a tangent line to a curve drawn on a plot. The computational analyst's answer is to use a machine that manipulates the symbols; it will move the 3 down in front of the t, decrement the power, and write 2. Those are all discrete operations.

    - -

    The point of this chapter is to state that computational analysis exists, rather than to present a comprehensive computational analysis system. If a person is looking for practical systems for extending functions that expand precision, or for second order computation, there are options.

    - -

    Hans J. Boehm and Robert Cartwright's work of expanding the precision of a computation on demand continued to mature. Boehm, while working at Google, authored a Java constructive reals library that powers the bundled Android calculator. When a person types in an expression, the system builds an Abstract Syntax Tree (AST) of the expression. The display interface determines how many digits fit on the screen and demands exactly that much precision from the root of the tree. The root function then recursively demands progressively higher precision from its operand functions until it achieves the strict error bounds required to guarantee every digit displayed on the screen is mathematically correct Hans J. Boehm, "Small data computing: Correct calculator arithmetic," Google Research, 2015. This library uses constructive real arithmetic to guarantee fully accurate results through demand driven evaluation.. -

    - -

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

    + For Call 1, the input tape is the Initial Tape. In Call 1 the machine will take the function value on the input tape, 0, and add the first difference, 1, writing the result 1, to the result tape. The machine will then continue on and take the first difference on the input tape, 1, and add the second difference on the input tape, 2, writing the result first difference to the result tape, 3. Then finishing up, the machine will not find a third difference on the input tape, so it will copy the second difference found on the input tape as the second difference for the result tape.

    -

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

    + For Call 2, the input tape is the result tape from Call 1. Execution then proceeds identically to Call 1. This pattern repeats for all successive calls. A person can see the values of t^2 as the first number on each result tape. Any polynomial can be computed in this manner, and the only ALU required is an adder that is also capable of subtraction.

    -

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

    +

    Lemma: Only row 0 is needed

    -

    Hence what would be useful for a replacement of the IEEE 754, would be variable precision number standard. There is one being proposed by John Gustafson called the Posit number representation John L. Gustafson, The End of Error: Unum Computing, Chapman and Hall/CRC, 2015. Posits serve as a hardware friendly alternative to IEEE 754 floating point numbers, providing variable precision mechanics.. +

    + The extension function can be called any number of times when the initial tape is identical to row 0 of the table of finite differences. No other row is needed from the table of finite differences.

    -

    This section reviewed finite difference methods as a means to implement function extensions. A person should notice that finite differences are one among many methods for extending functions, and they are not always the best choice. In modern computing it is not common to implement function extensions. Rather it is more common to increment a value across a domain, while completely repeating the evaluation for each new domain value, for example when computing values to place on a plot. However, independent of their importance in applied computing, function extension and difference methods are of theoretical importance for analysis, particularly when applied to nonstandard analysis. These speak to the thesis of computational naturalism in the derivation of mathematics, rather than as a proposed method of implementing computational programs. +

    + This follows from the mechanical procedure given above for computing the next row of the table from any given row.

    +

    Lemma: Evaluating call \omega requires an initial tape populated with components 0 through \omega of row 0

    - - Address - - -

    Unary Representation address

    +

    + Let the extent refer to the maximum index for accessing a component of a vector; the extent is often denoted as \omega. Performing extensions to calculate the function value at call \omega makes use of the initial tape up to index \omega, or as many nonzero values as are available up to that extent. +

    - A person 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 a person were to run the Natural Number Machine and observe as it writes to the tape, that person would watch as the Natural Numbers are printed one after another: '·s·ss·sss·ssss· ...'. Here '·' represents zero, and 's·' represents one, etc. Because the Natural Number Machine never halts, the machine cannot be used to initialize a tape, but an analyzer can evaluate the machine to make conclusions about what it would write if it were run. + To make this precise, let us define the difference vector at call k as D_k. The components of this vector are D_{k, 0}, D_{k, 1}, \ldots up to the maximum available difference. The first component, D_{k, 0}, is the function value itself. The component D_{k, 1} is the first difference, and so on.

    - In contrast, a function extension version of the Natural Number sequence generator can be run. The function extension machine would be given as input a prior function extension result, or an initial empty tape. It would then modify the tape to contain the next Natural Number, as per the sequence that the Natural Number machine would write, if it could be run. This is accomplished through two subroutine calls: find_empty and increment. The find_empty machine checks the symbol under the head. Upon finding it is not the empty symbol, the machine steps right and checks the next cell, repeating until it finds the empty symbol, whereupon it halts. The increment machine then writes an 's' onto the tape and halts. Recurrent calls to the Natural Number extender then produce a sequence of result tapes: [], [s], [ss], …. Similarly, a programmer can write a machine called decrement, though the programmer must note that decrementing can return the left-of-leftmost symbol. + Thus, this lemma claims that to compute D_{\omega, 0}, the highest component index accessed from the initial tape vector D_{0, i} will be i = \omega.

    - To say that 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 run. Conversely, if B were said to be greater than A, that would mean B occurs further to the right. It is a simple matter for a programmer to write a decider machine for this. The decider is given two input tapes for the two numbers to compare, and it keeps a head on each. It then steps forward until neither head has an 's' under it. If empty symbols are found simultaneously on both tapes, then the two numbers are equal; otherwise, the number with an empty symbol under the head is the lesser number. + Note that to compute the D_{k, 0} result by the mechanical procedure given above requires adding the input tape first difference to the prior difference. That is, D_{k, 0} = D_{k-1, 0} + D_{k-1, 1}. Hence we see immediately the lemma holds for the first call where k = \omega = 1.

    - As such, a person can assign a Natural Number to each cell of a given tape by using a mechanical procedure. Given a machine, say P, and an address machine, say A_P, each time P is stepped right, a call is made to run increment on A_P. Similarly, each time P is stepped left, a call is made to run decrement on A_P. In this manner the tape on A_P will always hold the address that machine P's head is on. + For an arbitrary k value we discovered that the highest index required of the D_{k-1, i} vector is i=1. + The value D_{k-1, 1} is computed from our mechanical procedure as + D_{k-1, 1} = D_{k-2, 1} + D_{k-2, 2}. Given we already know that to compute the value merely requires the prior value and first difference, we find that the largest index needed from vector D_{k-2, i} is 2.

    - The Natural Number found on A_P is then called the address for the cell that machine P's head is on. As each increment and decrement of the address is a constant time operation, keeping the address of the cell the head is on is computationally inconsequential. + There is a strict linear progression here. The computation of any component D_{k, i} inherently requires D_{k-1, i} and D_{k-1, i+1}. Therefore, each step backwards in time k expands the required index i by exactly one. By induction, computing the base value D_{\omega, 0} at call \omega requires tracing back \omega steps to the initial tape at k=0, which forces the maximum accessed index to be 0 + \omega = \omega. Thus, the highest required component from the initial tape is D_{0, \omega}.

    - An address space is a set of addresses for contiguous cells. The tape's address space is the set of addresses for all the cells on the tape. Typically the address of 0 is given to the leftmost among the contiguous cells. + The exact algebraic composition of this mechanical expansion is formalized by Newton's calculus of finite differences Isaac Newton formalized this interpolation method in 1675, later published in his Methodus Differentialis (1711). For a comprehensive foundational treatment, see George Boole, A Treatise on the Calculus of Finite Differences (Cambridge: Macmillan and Co., 1860), Chapter II.. Instead of executing the machine incrementally, a person can calculate the function value at call \omega directly as a linear combination of the initial tape components using Newton's forward difference formula:

    +

    + D_{\omega, 0} = \sum_{j=0}^{\omega} \binom{\omega}{j} D_{0, j} +

    -

    Binary Arabic representation address

    +

    + Because the binomial coefficient \binom{\omega}{j} evaluates to exactly zero for any integer j > \omega, the summation naturally truncates at index \omega. This algebraic property perfectly mirrors the physical boundary established by the machine execution trace. Furthermore, the relationship is symmetric. A person can compute the specific components of the initial tape, D_{0, n}, directly from the sequence of evaluated function calls, D_{k, 0}, using the alternating binomial sum: +

    - Would it be computationally consequential if binary Arabic representation were used instead of unary for addresses? For unary representation each increment was constant time, but with Arabic addresses, increments have a carry. Would the carry cause stepping to the right, combined with calling the address machine, to become slower and slower as the machine steps further and further? + D_{0, n} = \sum_{k=0}^{n} (-1)^{n-k} \binom{n}{k} D_{k, 0}

    - For this discussion, the Arabic representation address is variable precision, so it will grow as the count becomes larger. The empty symbol will serve as the terminator. + As a consequence of this lemma, we know that for any finite number of calls, i.e. finite \omega, that a finite prefix of D_0 is used.

    +

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

    +

    - For Arabic_increment, the machine reads the cell under the head; upon finding a 0 or the terminator, it writes a 1 and halts. Upon finding a 1, it writes a 0, steps right, and repeats the procedure. + 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.

    - - increment: - a = TTU.read() - if a == 0 or a == □: - TTU.write(1) - halt - TTU.write(0) - TTU.step() - goto increment - +

    + Taking successive finite differences reduces the degree of the polynomial by exactly one at each step. Consequently, the \omegath difference evaluates to a constant, and the next difference evaluates to exactly zero. +

    -

    Here TTU is the tape transport unit. It has the number to be incremented mounted on it. This number is either zero, which would mean the leftmost cell is empty, or it is of the same form as a result from a Natural Number extension machine. A TTU.read places a copy of the symbol instance found in the cell under the head into the read buffer automatically when the machine enters a new state on the programmed controller, so it is not counted as a step. In contrast, the other actions are associated with the state of the programmed controller, so when the machine arrives at a write, step, or halt node, it means that the programmed state controller has taken a step. Sequential instructions mean unconditional next state choices, whereas an if signals a conditional next state choice. The if condition is a logical proposition based on the read symbol.

    +

    Lemma: A D_0 vector of finite extent \omega generates a polynomial function of degree \omega

    -

    The loop form here is worth taking note of, as it will come up again. The controller executes a first action, that of a read, followed by a middle break test, and then the recursive form actions.

    +

    + If an initial difference vector D_0 has an extent of \omega, the sequence of function values generated by the machine corresponds to a polynomial of exactly degree \omega. A person can demonstrate this by algebraically recovering the polynomial constants, a_i, directly from the initial tape components, D_{0, i}. +

    - Each row shows an input tape, and actions taken to write the result tape. For any given row, the result tape is the same as the input tape on the next row down. The table lists 7 increments, which is sufficient to reach the maximum count that can be held by a 3 bit counter. + Consider an extent of \omega = 0, forming a polynomial of degree 0, f(t) = a_0. Evaluating at t = 0 yields f(0) = a_0. Because the machine's initial value is D_{0,0}, a person establishes a_0 = D_{0,0}.

    - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
    inputactioncost (steps)
    0write 1, halt (result is maximum 1 bit count)2
    1 write 0, step, write 1, halt4
    01write 1, halt (result is maximum 2 bit count)2
    11write 0, step, write 0, step, write 1, halt6
    001write 1, halt2
    101write 0, step right, write 1, halt4
    011write 1, halt (result is maximum 3 bit count)2
    111
    +

    + When a person extends the extent to \omega = 1, the next term is added to form f(t) = a_0 + a_1 t. The first forward difference at t = 0 is D_{0,1} = f(1) - f(0) = (a_0 + a_1) - a_0 = a_1. Therefore, a_1 = D_{0,1}. Note that the addition of the linear term did not change the evaluation at t = 0; the a_0 constant remains firmly anchored to D_{0,0}. +

    - The number of programmable controller state transition steps required to reach a maximum 1 bit, 2 bit, and 3 bit count are: [2, 8, 22]. Note these are cumulative. The three bit maximum count cost includes that of the two bit maximum count cost, etc. Each maximum count is exponentially larger, so a better measure is the average cost per step: [2/1, 8/3, 22/7] = [2, 2.667, 3.143] + Extending to \omega = 2, the polynomial becomes f(t) = a_0 + a_1 t + a_2 t^2. The second difference at t = 0 is calculated as D_{0,2} = f(2) - 2f(1) + f(0). Substituting the polynomial yields D_{0,2} = (a_0 + 2a_1 + 4a_2) - 2(a_0 + a_1 + a_2) + a_0 = 2a_2. Thus, a person recovers a_2 = D_{0,2} / 2. The lower coefficient then adjusts to a_1 = D_{0,1} - a_2.

    - For an n bit counter, the sequence of costs follows a pattern. Half of the increments evaluate one bit (costing 2 steps), a quarter evaluate two bits (costing 4 steps), an eighth evaluate three bits (costing 6 steps), and so forth, over the 2^n - 1 increments required to reach the maximum n bit count: + Continuing to \omega = 3, the polynomial is f(t) = a_0 + a_1 t + a_2 t^2 + a_3 t^3. Evaluating the third difference D_{0,3} isolates the highest order term, yielding D_{0,3} = 6a_3. This allows immediate recovery of the highest constant: a_3 = D_{0,3} / 6.

    - \sum_{k=1}^{n} 2k · 2^{n-k} = 2^{n+2} - 2n - 4 -

    - To find the average cost per increment to reach each maximum, an analyst divides by the total number of increments, which is 2^n - 1: + Once a_3 is known, the shifting nature of the lower order constants becomes apparent through back substitution. The second difference equation expands to D_{0,2} = 2a_2 + 6a_3. Substituting the known a_3 allows recovery of a_2 = (D_{0,2} - 6a_3) / 2. Similarly, the first difference equation expands to D_{0,1} = a_1 + a_2 + a_3, which resolves to a_1 = D_{0,1} - a_2 - a_3. Through all of this shifting, a_0 = D_{0,0} remains entirely unperturbed.

    - \text{Average Cost} = \frac{2^{n+2} - 2n - 4}{2^n - 1} = \frac{4(2^n-1)+4-2n-4}{2^n-1} -

    - This simplifies algebraically to: + To observe the structural integrity of this progression, a person can array these relationships into a system of equations mapping the initial tape to the polynomial constants:

    - \text{Average Cost} = 4 - \frac{2n}{2^n - 1} + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
    DifferenceEquation
    D_{0,0}= a_0
    D_{0,1}= a_1 + a_2 + a_3 + \ldots + a_\omega
    D_{0,2}= 2a_2 + 6a_3 + \ldots
    D_{0,3}= 6a_3 + \ldots
    \ldots\ldots
    D_{0,\omega}= \omega! a_\omega

    - As the address space grows, the bit width n increases. The polynomial term 2n is outpaced by the exponential denominator 2^n - 1, causing the fractional terms to converge to zero. The average work done by the machine head converges to exactly four tape actions per increment. Constant time, same as for unary. This is a surprising counter intuitive result. + A pattern emerges. Because each successive forward difference operator annihilates the lowest power of t, the resulting algebraic system is upper triangular. For any extent \omega, the \omegath difference equation reduces to D_{0,\omega} = \omega! a_\omega. This structural guarantee permits a person to reliably recover a_\omega = D_{0,\omega} / \omega!. Because an initial tape of extent \omega dictates that D_{0,\omega} is nonzero, a_\omega is guaranteed to be nonzero. All subsequent lower order constants are then systematically resolved through cascading back substitution.

    - Consequently, maintaining an Arabic address on a secondary Address Machine remains a constant time operation in the amortized sense, making it computationally inconsequential to the complexity class of the base machine. However, if a problem were to increment and decrement repeatedly around a binary power count, the behavior would be the limiting logarithmic time due to the length of the counter. An unlucky situation like this is called aliasing. + To observe the formal mechanics of this progression, a person can alternatively array these relationships into a matrix equation mapping the polynomial constants, a_i, to the initial tape differences, D_{0,n}. The coefficients of this transformation are defined by the Stirling numbers of the second kind, denoted S(i,n):

    -

    - The model used here to define an address is analogous to keeping a pointer into memory. Each step then increments or decrements the pointer. Conventional processors do the converse of the Turing Machine model presented here. For a processor, the address is the base object, while the head location is what is implied by the address. On processors, pointers will be one word in width. In small geometries where computation element delay dominates, two operand adders tend towards logarithmic complexity evaluation times against bit width, and the constants are small. Because of this, it is practical to perform word width addition operations atomically in one machine cycle. In fact, for some machines, the adder time likely sets the clock period. Such an adder will be used for address arithmetic; consequently, a programmer cannot arrange a program to expose aliasing in the address increment time to the real world. It remains a theoretical observation. -

    + + \begin{bmatrix} D_{0,0} \\ D_{0,1} \\ D_{0,2} \\ \vdots \\ D_{0,\omega} \end{bmatrix} = + \begin{bmatrix} + 0! S(0,0) & 0! S(1,0) & 0! S(2,0) & ⋯ & 0! S(\omega,0) \\ + 0 & 1! S(1,1) & 1! S(2,1) & ⋯ & 1! S(\omega,1) \\ + 0 & 0 & 2! S(2,2) & ⋯ & 2! S(\omega,2) \\ + \vdots & \vdots & \vdots & \ddots & \vdots \\ + 0 & 0 & 0 & ⋯ & \omega! S(\omega,\omega) + \end{bmatrix} + \begin{bmatrix} a_0 \\ a_1 \\ a_2 \\ \vdots \\ a_\omega \end{bmatrix} +

    - An address is sent on a trip through the memory hierarchy to locate the corresponding memory cell, ultimately landing on a memory decoder over a physically implemented memory. Address decoders resemble carry chains, and they also have logarithmic physical evaluation times as word width grows. Hence, a fixed width word holding an address gets decoded in approximately constant time measured in clock ticks. However, the trip through the memory hierarchy is not negligible. + For any extent \omega, the final row of this strictly upper triangular matrix again simplifies to D_{0,\omega} = \omega! a_\omega.

    - Direct address decoding operates independently of reference locality. This fundamentally differs from a Turing Machine head, which incurs a linear computation cost strictly proportional to the distance traveled. However, direct decoding is only the base of the memory hierarchy. + The main diagonal contains strictly non zero factorials, ensuring the matrix is invertible. By inverting this matrix, a person replaces the cascading back substitution with a direct, closed form equation to recover any constant a_i. The inversion utilizes the signed Stirling numbers of the first kind, denoted s(n,i) (see the Appendix on Stirling numbers).

    - It is possible that decoding occurs separately in a row and column manner, and changes in the lower bits of the address walk a buffered row that was found in a prior access. This makes access to neighbor cell addresses within a row a low expense operation. However, this depends on memory implementation. One layer up, it is common for memory to be made of interleaved banks, so neighbor access that remains in the leaf collection is generally faster than that which requires fetching a new leaf set. + a_i = \sum_{n=i}^{\omega} \frac{s(n,i)}{n!} D_{0,n}

    - There will, however, be a more dominant effect. For programs with islands of locality of reference, instructions or data will be discovered in a cache. Caches bring in two types of locality: that of access within a cache line, which makes neighbor walks that stay in the line fast, and cache line prefetch and replacement policies, which assume for any given fetch address that a subsequent fetch will be nearby in memory. These effects lead to similar memory behavior as a head on tape, where a single step to a neighbor is faster than taking many steps to find memory further away, but there is not a one to one correspondence. + Thus, extending this procedure \omega times definitively recovers the constants for exactly a polynomial of degree \omega.

    - Memory accesses into the processor local memory file are even faster. If locality of reference, even in an abstract sense, remains tight, then memory cells can be accessed in a minimal amount of time. + This mechanical recovery of standard polynomial constants is completely analogous to Newton's interpolation formula Ibid.. Instead of resolving the standard constants a_i through an upper triangular matrix, a person can construct the polynomial directly by treating the initial tape components as the exact coefficients for a basis of binomial terms:

    - For programs with large memory footprints and sparse memory access patterns, the dominant factor becomes the virtual memory subsystem. Here locality again comes into play as the translation lookaside buffer provides stateful location context, and the neighbor relationship between pages is sometimes taken into account for performance reasons. However, once a program starts performing at virtual memory page fetch times instead of cache access, or even local system memory access times, the program is said to be page thrashing, and it becomes very slow. It is also possible for small programs to have memory access patterns that alias against the memory subsystem's heuristics and lead to page thrashing. For a typical system, a programmer can write a small program to demonstrate this. + f(t) = \sum_{n=0}^{\omega} D_{0, n} \binom{t}{n}

    - In summary then, using Arabic representation for addressing is not statistically computationally consequential. On the other hand, the idea of using a decoded address in place of a tape head raises computational model issues. So much so that it would not be an exaggeration to say that the very goal of modern computer architecture is to ensure that, within an execution context, address decode does not become computationally consequential. Architects employ a memory hierarchy to do this, and that memory hierarchy rewards locality of reference, but access times are not linear in time relative to distance from prior access. Instead they are clumped into a constant time access abstract concept of locality groups where the time to access each group grows exponentially with the distance from the processor. + Because the nth binomial coefficient expands into a polynomial of exactly degree n, and the summation is bounded by the finite extent \omega where D_{0, \omega} is definitively nonzero, the constructed function f(t) is structurally guaranteed to be a polynomial of degree \omega.

    -

    - Let us put this into perspective. Suppose in ancient Roman times that a clock tick for a computer was scaled to be one day long, so that the action involves sending letters rather than variable values. Under this scale, a single nanosecond of real world execution time equates to three days. Suppose a program initiated a read request for a location in memory on the Ides of March, the date when Caesar was assassinated on -0043-03-15. Surely that was a big day for posting letters. The following table provides the historical date that the variable value would finally be loaded into the processor, depending on the memory tier being accessed: +

    Difference table for an exponential function

    + +

    + Here is the table of finite differences for the function 2^t.

    - - - - - + + + + + - - - - - + + + + + - - - - - + + + + + - - - - - + + + + + - - - - - + + + + + - - - - - + + + + +
    Memory TierReal World LatencyScaled DelayScaled Arrival EraHistorical ContextCount (t)f(t) = 2^t1st Diff (δ^1)2nd Diff (δ^2)3rd Diff (δ^3)
    L1 Cache Hit1 ns3 days-0043-03-18Three days after the assassination.01111
    DRAM (Main memory)100 ns300 days-0042-01-09Nearly a year later, during the Liberators' civil war.12222
    NVMe SSD Page Swap15 µs45,000 days0080123 years later, exactly as the Colosseum is completed in Rome.2444
    SATA SSD Page Swap100 µs300,000 days0778821 years later, during the reign of Charlemagne and the Frankish Empire.388
    Magnetic HDD Page Swap10 ms30,000,000 days82092Tens of thousands of years in the future, long after current human civilizations are dust.416

    - In computer architecture, there is a rule that the slower the access time, the larger the amount of data that should be transferred. The idea is then that of access time per bit, instead of access time per fetch. A common example given is that of a station wagon of hard drives driven across the country. Andrew S. Tanenbaum famously coined this concept in his 1981 textbook Computer Networks, stating: "Never underestimate the bandwidth of a station wagon full of tapes hurtling down the highway." This physical data transfer method is universally referred to as a sneakernet. Ten terabits, at three days, equates to 26 nanoseconds per bit. Not bad, if a user can wait three days to continue the program, but aliasing between data sets would make a program very slow. The Turing Machine model does not capture the effects of clumped data accesses. + The first difference of 2^t is also 2^t, so row 0 of the table will have an infinite number of values. Fortunately, due to the lemma stating that evaluating call \omega requires an initial tape populated with components 0 through \omega of row 0, exactly those components are needed for the recurrence to proceed. Furthermore, when new values are needed, they are easily computed. A programmer need not store the entire infinite first row of the difference table on a static tape.

    - - - Area and partitioning -

    - We call a subset of contiguous cells from a tape an area. An area with a single cell is called a singleton, one with two cells is called a pair. An area has a leftmost cell and a rightmost cell. For a singleton area, those will be the same cell. + Instead of attempting to write an infinite sequence to a physical tape, a person can encapsulate the generation logic within a dedicated Turing Machine. In the tradition of constructive arithmetic associated with Boehm, this generator machine acts as a virtual tape. When the primary extension machine requires the next difference component, it queries the generator machine, which computes and yields the value on demand. This lazy evaluation strategy elegantly handles functions with infinite difference sequences without exhausting finite memory.

    -

    The left neighbor cell to the leftmost cell of a given area is considered to be the left neighbor cell to the area. Similarly, the right neighbor cell to the rightmost cell of a given area is considered to be the right neighbor cell to the area. If the given area is located at the left end of the tape, then it has no left neighbor cell. If the given area is open on the right, then it has no right neighbor cell. -

    +

    Composition of recurrence functions

    -

    A tape partition is a set of areas that completely span a tape. For any partition of a single ended Turing Machine tape, at least one of the areas will necessarily be infinite. -

    +

    If we desire to compose recurrence functions, in the first order or the second order, the call counts must first be synchronized.

    -

    Head partition

    +

    Say for example, we have a machine called fizz that adds 3 to the input on the tape, and another machine called buzz that adds 5 to the input on the tape, and we wanted to compose the two machines. We would have to define what a call to the resultant machine means to the machines in composition.

    -
      -
    1. The left side: The finite set containing all of the cells to the left of the head cell.
      2. -
    2. Head: the head cell.
      3. -
    3. The right side: the infinite set containing all the cells to the right of the head.
      4. -
    +

    If one call to the resultant machine makes the equivalent of one call to the fizz, and one to buzz, the the resultant machine can be simplified to add 8 to its input tape each time it is called. In contrast if one call to the resultant machine makes the equivalent of 5 calls to fizz, and 3 calls to buzz, then the resultant machine reduces to adding 30 to the input tape per call. The two machines are very different.

    -

    If the head is on the leftmost cell, there is no left side area.

    +

    Performing operations with recurrence functions requires integrating a call algebra in addition to integrating the machines. Often this is handled by considering the machines being composed to be subroutines, and the outer controller than explicitly calls them. The call algebra can then be dynamic depending on the input. Calls can be skipped due to being inside conditionals, or performed an arbitrary number of times in loops. Though simple control structures that are static are more math like, and are more likely to be more affected by optimizations (simplifications).

    -

    Leftmost/remaining partition

    +

    A pole and zero cancellation

    -
      -
    1. Leftmost: the leftmost cell.
      2. -
    2. Remaining: the infinite set including the right neighbor of the leftmost cell, and all cells further to the right.
      3. -
    +

    + Here we circle back to the division by zero problem, though this time while extending functions. Let us begin with the two functions, f(t) = 2^t - 32 and g(u) = u - 15. Both have D_0 vectors, though the one for the exponential function is defined by a machine rather than by a value on a tape. +

    -

    Active area partition

    +

    + We cannot do function based arithmetic on these until we synchronize them. Suppose that for each call of the f machine, there will be three calls to the g machine. So we can make a new machine that is called once, each time f is called, g(t) = 3t - 15. +

    - A nonempty tape, one with at least one cell holding an alphabet symbol, can be partitioned into the following areas: + Now suppose we want to express the quotient of these two functions.

    -
      -
    1. The left empty tail: if the leftmost cell of the tape is an alphabet cell, there is no left empty tail. Otherwise, it consists of the leftmost cell and the empty cells, if any, to the right of the leftmost cell, up to, but not including, the first alphabet cell.
      2. + + h(t) = \frac{f(t)}{g(t)} = \frac{2^t - 32}{3t - 15} + -
    2. Active area: a finite area for computational problems, containing the cells extending from the leftmost alphabet cell up to and including the rightmost alphabet cell. It is possible that the leftmost alphabet cell and the rightmost alphabet cell will be the same cell.
      3. + Figure singularity plot -
    3. The right empty tail: the infinite set extending from the right neighbor of the rightmost cell of the active area, extending rightward.
      4. -

    - A noncomputational tape is one that cannot be initialized by a Turing Machine, but can still be surmised to exist, perhaps in analysis due to its properties. The empty tape is an example. The tape holding the Natural Numbers is another example. For noncomputational tapes that have the property that the active area is open on the right, there is no right empty tail. + Evaluating this form in the first order at the point t=5 returns a (divide 0 0). It is a strange thing, because when we plot h(t) values, against t there is an obvious correct value on the curve at t=5. There is no special feature that would make it questionable.

    -

    Area implied partition

    -

    - The existence of a finite given area implies a three area partition: the left side, the given area, and the right side. If the given area is located at the left end of the tape, there is no left side area. If the given area is open on the right, there is no right side area. + Suppose we move to a second order evaluation, and for places the computation does not work, we return the machine that isn't evaluating. That is similar to what we did to get (divide 0 0), but the zeros in that expression came from a prior step first order evaluation. Let us instead give the quotient composer two machines to compose, and have it return a value when reduction to the first order is possible, and return the full problem as posed to it when it can not be reduced.

    -

    The impossibility of recognizing an empty tape

    + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
    Count (t)Quotient (f(t)/g(t))1st Diff Ratio (δ^1 f(t) / δ^1 g(t))
    031/151/3
    130/122/3
    228/94/3
    324/68/3
    416/316/3
    5(divide f(5) g(5))32/3
    632/364/3
    796/6128/3
    8224/9256/3
    9480/12512/3

    - Recognition is a process where a Turing Machine decides if a pattern is present on a tape solely by reading symbols found on the tape. No meta information, such as a message communicating something about the area being examined or the nature of the program that wrote the symbols, can be taken into account. + The quotient machine, (divide f(5) g(5)), is no more representative of the value we expected here, than was (divide 0 0). However, as we have the whole program, we could pass it to a L'Hôpital evaluator and get a value back. But I am wondering if we can't design function extension form that extends to the value and beyond without any hiccups, as most apparently there is a value to extend to.

    - The active area partition of a tape only works for tapes that have at least one alphabet cell. As soon as a machine does its first write of an alphabet symbol, it is known the tape has at least one alphabet symbol. However, what if a tape of unknown status, whether completely empty or containing an alphabet cell, is mounted on a tape machine, and it is desired that the machine recognize if the tape is empty or has an alphabet cell? This is the equivalent problem of looking for the leftmost cell of an active area. + 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.

    -

    - Recognizing that a tape is empty is generally impossible. Suppose it were attempted, and a machine started scanning the tape rightward from the leftmost cell; for every cell that is discovered to be empty, the machine would have to scan further rightward to check for an alphabet cell. If the tape is truly empty, the recognizer would never stop scanning, so no decision would ever be rendered. +

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

    -

    The impossibility of recognizing the rightmost cell of the active area

    -

    - In general, a Turing Machine cannot step across a tape reading cells to recognize the rightmost cell of the active area, or equivalently, the leftmost cell of the right empty tail. Suppose a recognizer attempted this by starting in the active area and stepping right, and the machine discovered an empty cell. The machine would be unable to distinguish between the case of said empty cell being embedded within the active area (meaning more alphabet cells lie further to the right), or the case where said cell is genuinely the leftmost cell of the right tail. To resolve the ambiguity, the machine would be obligated to continue stepping right. Yet, there would never come a time where finding another empty cell would avoid leading back to the exact same case ambiguity, so the machine would forever step right without returning a decision. + Perhaps if we were performing nonstandard analysis, and extending by increments of epsilon in the domain at each step, the nonstandard analysis naturalization function would find that the differential value can be used as the value at the singularity. But here we are discussing finite differences H. Jerome Keisler, Elementary Calculus: An Infinitesimal Approach, 2nd ed. (Boston: Prindle, Weber and Schmidt, 1986).. We are not doing a local analysis here so as to derive a principle, but rather are trying to evaluate a function in the macro view.

    - It follows that if knowledge of the end of the active area is needed, this information must be encoded as a message. For example, a special symbol can be reserved in the alphabet specifically to serve as the end of active area marker. Each time a machine steps beyond the current end of active area marker and does a write, it writes the marker in the right neighbor cell, and goes back and erases the old mark. This method is related to communications theory and the science of signaling. Here, the active area marker is an out-of-band control signal. + So then, perhaps we set the value at the singularity to x build out the difference table, then solve for x?

    -

    - If a tape is written by an initializing tape machine, unmounted, and then mounted on a second analyzing tape machine, the analyzing tape machine is starting with a populated tape. Similarly, a mathematician can, by decree, define an initial tape that holds predefined alphabet symbols. In such a scenario, the initializing machine and the analyzing machine must use a shared communication protocol for signaling the end of the active area. They cannot operate independently or the analyzing machine would not be able to find the end of the active area. This shared protocol then represents information held by a mediator, said mediator could be used at a higher level to write the control for the two machines, or it could be consulted when the two machines are run. Hence, the mediator is either an author, or a service provider, or possibly both. -

    + Figure with x variable. -

    - By definition, a computation must finish in a finite number of steps. It follows that the active area when a Turing Machine halts a computation will always be finite. Consequently, if a Turing Machine initially starts working with a tape that was computed by another Turing Machine, the length of the input will be finite. Still, that input will be in the active area, so the receiving Turing Machine will need to read control data left on the tape under a common communication protocol to be able to find the bounds of the input area. -

    - When an input tape is provided as a general mathematical object, either decreed by definition or perhaps abstracted from 'what a Turing Machine computation would produce in the limit of step count', then the input can be either finite or infinite. + As Newton pointed out, we can know the differences on the D_0 row of the table from the quotient function:

    -

    In band and out-of-band control

    + + D_{0,n} = \sum_{k=0}^n (-1)^{n-k} \binom{n}{k} \frac{f(k)}{g(k)} +

    - Because of the impossibility of recognizing certain tape features, when a tape is written by one Turing Machine, then used by another, there must be some sort of system for messaging control. There are two approaches for mixing data and control together: one is in band signaling, while the other is out-of-band signaling. + For k=5 the difference evaluates to be (divide 0 0), as it did for the quotient, and it also fails for all values above k=5 due to the summation. So we can not use this to solve for x.

    - In band control occurs when control signals or structural metadata are mixed directly into the same channel and alphabet as the data payload. In band signaling leads to ambiguities between what is control and what is data. As we saw, there are cases where a recognizer, i.e., merely examining the data, is completely incapable of resolving even the simplest of control questions. A conventional approach for resolving these ambiguities makes use of escape sequence schemes that grow in length as the levels of communication grow. This has always been an afterthought, a sort of hack. + As the second order evaluation returned (divide f(k)|k=5 g(k)|k=5), we can use L'Hôpital evaluator to resolve this indeterminate form D_{0,5}. Note this is during the creation of the D_0 vector, so it is part of the simplification step, rather than being part of the evaluation of the quotient. The result will thus be used in producing an extension machine that extends through the singularity, so the user will not see any exceptional higher order values while extending h(t).

    - In contrast, out-of-band control communicates structural information through a strictly separate channel or by utilizing symbols definitively excluded from the programmer visible data alphabet. The rightmost tape marker is an out-of-band mechanism because it utilizes an expanded hardware tape alphabet strictly reserved for machine management, guaranteeing it can never be conflated with the user's data. Modern architectures often lack the luxury of inventing new symbols to serve as control rather than data. Another out-of-band signaling technique is to structure the data into channels; such structure is called formatting. We find formatting on hard drives, in frame based and packet based communication channels, and in data structures. -

    - -

    Virtual cells

    - -

    A given finite area that is not sitting on the end of the tape will have a left neighbor area and right neighbor area that are not in the area. If the given area is sitting on the end of the tape there will be no left neighbor area. If the area is open on the right, there will be no right neighbor area.

    - -

    Now imagine we define a Turing Machine such that when it steps right, it steps to the right neighbor area, and when it steps left, if there is a left area, it steps to that, otherwise it returns a left-of-leftmost symbol. The read instruction reads all of the cells in the area, and similarly the write instruction writes them all. Then for this machine the areas are virtual tape cells. -

    - -

    An example of this from conventional computing is where memory is accessed in units of bytes, but a program works with units of words.

    - -

    Virtual tape

    - -

    As established, the Turing Machine head transport returns a distinct left-of-leftmost symbol when stepping left off the end of the tape. The programmed controller, the statement machine, then uses an arc defined specifically for this symbol. It is a distinct symbol that cannot be written to the tape. + The L'Hôpital evaluator will discover that a transcendental constant is required. It will be returned as a higher order object, a machine definition, because the value can not be written to the tape.

    -

    Various portions of this text have mentioned calling a Turing Machine as a subroutine. This is described as unmounting the tape from the calling machine, mounting it on the subroutine machine, running the subroutine machine until it halts, then unmounting the tape from the subroutine machine, and mounting it back on the calling machine. However, this would be a manual process. To automate the process, we use a Universal Turing Machine. It has the definition for the calling machine and the subroutine machine on its tape. We can add an additional tape to the machine to hold the stack. Then a subroutine call happens much as it does in conventional software. -

    + + T = \frac{32 \ln(2)}{3} + -

    A gasket machine is actually a set of subroutines with one corresponding to each of the tape transport instructions. -

    +

    The resulting D_0 vector for the quotient is:

    -

    - There is a small problem, in that the left-of-leftmost symbol was stipulated as being separate from the alphabet, and only alphabet symbols and the empty symbol can be written to the tape. There are a couple of possible solutions. One solution is to add a symbol to the alphabet that is also taken to mean 'left of leftmost', say gasket-left-of-leftmost. Then machines that make use of gaskets can recognize this new symbol for its meaning. Another alternative, that will be used for the remainder of our discussion, is to define a separate control alphabet of symbols that are distinct from data alphabet symbols, but can also be written and read from the tape. We will add to this alphabet, empty, left-of-leftmost, and a new control symbol used by gaskets,right-of-rightmost. -

    + Figure D_0 h(t) -

    Now suppose defining a Turing Machine that initially has the head on the leftmost cell of a specific area. When step left is called, the tape transport immediately returns the left of leftmost symbol, independent of whether the area is actually at the physical left end of the tape or not. -

    + Figure D table for h(t)

    -Now suppose defining a Turing Machine that initially has the head on the leftmost cell of a specific area. When step left is called, the tape transport immediately returns the left of leftmost symbol, independent of whether the area is actually at the physical left end of the tape or not. -

    - -

    Suppose further that this area is finite. If the machine attempts to step right from the rightmost cell of this finite area, the tape transport returns, in analogy, right-from-rightmost symbol. Such a machine defines a virtual tape over an area. + I find it fascinating to watch the transcendental difference values march down the table, then all cancel out after h(5) is generated.

    -

    Partitions on a finite virtual tape

    -

    - When a Turing Machine operates on a finite virtual tape, the structural logic of the partitions established earlier must be updated to reflect the absolute rightward boundary. + So the value of h(5) is transcendental, but all the machinery we were using, up until using L'Hôpital evaluator, was closed over the rational field. That is why no matter how we tried to organize the difference tables, there was no way to find h(5), or to find a D table for extending through it. This situation occurred due to introducing the 2^t function. Had we remained with finite length D tables, i.e. finite degree polynomials, we could have used deconvolution of the D_0 vectors, or synthetic division on the polynomials, to create the quotient.

    -
      -
    1. For the Head partition and Area implied partition, the right side is no longer infinite. It is a finite set containing all cells extending from the right neighbor of the head (or area) up to the absolute rightmost cell of the virtual tape. If the head (or area) includes the rightmost cell of the virtual tape, the right side set does not exist.
      2. -
    2. For the Leftmost/remaining partition, the remaining area is now a finite set terminating at the rightmost cell of the virtual tape.
      3. -
    3. For the Active area partition, the right empty tail is similarly a finite set extending to the rightmost boundary of the virtual tape. If the rightmost alphabet cell occupies the rightmost cell of the virtual tape, the right empty tail does not exist.
      4. -
    - - - Metrics - -

    Address defined area

    - -

    We defined a tape as having a single feature, that of a leftmost cell, along with a linear neighbor topology. When a tape is mounted it gains a second feature, that of the cell the head is on. The leftmost cell was fixed in place, while any other single cell on the tape can be featured as the cell the head is on. When we introduced areas, we picked up two new features, that of the leftmost cell of the area, and the rightmost cell of the area. Again, those features could coincide with the former features. We noted that the features partitioned a tape thus defining more areas, and more features. -

    -

    - When cells were defined we noted that they were sets, and that these sets had identity and could be referred to. We needed that to be the case so as to build the tape topology using neighbor properties. Had the tape been singly linked, perhaps we could have used the cells to represent themselves in the properties, but when we doubly linked it, a given cell had to appear in two places, as the right neighbor of its left neighbor, and the left neighbor of its right neighbor, so we stipulated the sets as being identifiable. Initially we did not say how they would be identified. This is common in mathematics, but we soon cleared this up by formalizing the concept of a symbol. -

    +

    And for the victory lap, evaluation versus higher order computation and function extension:

    -

    - When discussing symbols we noted they could be natural numbers, and even went so far as to point out that addresses were symbols, though we had not yet defined them. They are familiar to anyone involved in computing, so again, it did not present a serious problem. Here we have now formalized them. -

    + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
    Count (t)Direct Evaluation (f(t)/g(t))Extended Quotient Vector (H(t))
    031/1531/15
    130/1230/12
    228/928/9
    324/624/6
    416/316/3
    5(divide 0 0)\frac{32 \ln(2)}{3}
    632/332/3
    796/696/6
    8224/9224/9
    9480/12480/12
    -

    - So we now have two means for identifying a feature. One means is to state its address, and the other is to put a tape machine head on it. -

    +

    Chapter discussion

    -

    As we noted in the section discussing area, an area has two distinguishing features, being that it has a leftmost cell, and a rightmost cell. That definition is topological. If we start with the leftmost cell of a tape, we are either already on the leftmost cell of a defined area, or we can step right to find it. At the point of finding it we know this leftmost cell is part of the area, then we are either already on the rightmost cell, or we can continue to step right on cells in the area until we find the rightmost cell in the area. The right neighbor of the rightmost cell in the area, and all cells to that right of that, are excluded from the area. -

    +

    The fundamental claim of computational analysis is that all functions can be viewed as discrete entities. Take this simple function:

    -

    With addresses we can now define an area with two addresses, two natural numbers, the address of the leftmost cell, and that of the rightmost cell. All natural numbers greater than or equal to the address of the leftmost cell, or less than or equal to the address of the rightmost cell, are addresses of cells that are in the area. This feels more satisfactory for most of us, as now we are talking about arithmetic rather than graph topology. Though should the topology of the tape be generalized, this could become limiting. It reminds me of Frege's admonition that perhaps math should be built on top of geometry. -

    + + f(t) = t^3 + -

    Distance and extent

    +

    It is said to be a continuous function over the real field. However, from a computational perspective, it is a string of 8 discrete symbols. A person might ask then, "If the function is not continuous, then how can a person take a derivative?" Often people view a derivative as a tangent line to a curve drawn on a plot. The computational analyst's answer is to use a machine that manipulates the symbols; it will move the 3 down in front of the t, decrement the power, and write 2. Those are all discrete operations.

    -

    The distance between two cells is the absolute difference in their addresses. When we talk about the distance between the leftmost cell of an area and the rightmost cell of an area, we call this number the area's extent.

    +

    The point of this chapter is to state that computational analysis exists, rather than to present a comprehensive computational analysis system. If a person is looking for practical systems for extending functions that expand precision, or for second order computation, there are options.

    -

    In an analogous manner to defining an address space for a tape, we can define an address space for an area. Accordingly, the leftmost cell of the area is assigned address zero, and the address increments cell by cell going to the right. A finite area will have a finite address space, with the address of the rightmost cell being the largest address in the address space. +

    Hans J. Boehm and Robert Cartwright's work of expanding the precision of a computation on demand continued to mature. Boehm, while working at Google, authored a Java constructive reals library that powers the bundled Android calculator. When a person types in an expression, the system builds an Abstract Syntax Tree (AST) of the expression. The display interface determines how many digits fit on the screen and demands exactly that much precision from the root of the tree. The root function then recursively demands progressively higher precision from its operand functions until it achieves the strict error bounds required to guarantee every digit displayed on the screen is mathematically correct Hans J. Boehm, "Small data computing: Correct calculator arithmetic," Google Research, 2015. This library uses constructive real arithmetic to guarantee fully accurate results through demand driven evaluation..

    -

    It is interesting that the extent of an area will be the same, whether it is calculated from the address space of the tape, or the address space of the area. In fact, the extent will always be identical to the largest address in the address space. We will use the Greek symbol omega, \omega, to symbolize an extent. We can give it a subscript with the name of an area if the correspondence is not already clear. The choice of \omega makes sense here because \omega is an inclusive bound, i.e. it is the rightmost letter included in the Greek alphabet. Thus it is the extent of the Greek alphabet. -

    - -

    Length

    - -

    If cells in an area are transacted, the cost of the area is the cost of a cell multiplied by the count of cells. Vincent Atanasoff probably found himself needing to know such a count when ordering capacitors. The count of cells in an area is also known as the area's length. We will use the Greek symbol Ï¡, pronounced as sampi, to refer to the length. The length of an area, the count of its cells, will always be one greater than its extent, Ï¡ = \omega + 1. This symbol makes sense here, as the Greek number system fell short of letters, so the symbol Ï¡ was tacked on to the end of the alphabet, but did not belong to the alphabet. -

    - -

    The count of cells in an area, the length of an area, and the cardinality of the address space for an area are all the same number, Ï¡. The extent of an area, \omega, is an address in an area's address space, whereas the cardinality of an area, Ï¡, falls outside it. This has implications. Because extent is an address, extent and addresses can always use the same number representation. In contrast, there is no such guarantee for cardinality, Ï¡. Take for example an area that contains 256 cells. The addresses run from zero to 255, and all can be represented with an 8 bit binary number. However, the number 256 requires 9 bits, and thus would not fit in an 8 bit address register. This one of the reasons that code will have fewer end case problems when expressing the size of objects with extents, rather than with lengths. -

    - -

    Is the cardinality of an open on the right area a Natural Number?

    - -

    So we find an interesting situation with the cardinality of an address space for an area that is open on the right. It goes like this.

    - -

    How cardinality is computed

    - -
      -
    1. We set Turing Machine P with its head on the leftmost cell of an area. We mount the initial tape, '·', on the A machine.
      2. -
    2. We step P and simultaneously run the A machine. Stepping stops when P reaches the rightmost cell of the area. At this point, the tape on the A machine holds the address space extent.
      3. -
    3. The A machine is run an additional time. The output on the tape is defined to be the cardinality of the address space, aka the cardinality.
      4. -
    - -

    Lemma 1, the A machine produces Natural Numbers

    - -

    This follows from its definition; it is literally the increment from the Natural Numbers Machine.

    - -

    Lemma 2, cardinality is a natural number

    - -

    Cardinality is produced by repeatedly calling the A machine, and the A machine produces Natural Numbers.

    - -

    Lemma 3, cardinality is not in the address space

    - -

    At the end of the second step in the procedure for producing the cardinality, the tape of the A machine held the extent of the address space. Then in step 3, A was called again, thus leaving a number one larger than the extent on its tape. The extent is the largest number in the address space, hence cardinality is larger than all numbers in the address space. Thus cardinality is not in the address space.

    - -

    Lemma 4, the address space of an open on the right area is identical to the Natural Numbers.

    - -

    Composing the A machine with an unterminated loop call, where each result is written to a tape with a terminator between entries, results in the same machine as the Natural Numbers Machine.

    - -

    The apparent contradiction.

    - -

    By Lemma 2, cardinality is a Natural Number. By Lemma 3 cardinality is not in the address space. By Lemma 4 the address space is identical to the Natural Numbers.

    - -

    Resolution

    - -

    The resolution lies in the computational reality of Step 2. For an area that is open on the right, the stepping of machine P never halts. Because Step 2 never terminates, Step 3 is never executed. The A machine never runs that final, additional time. Therefore, the cardinality of an open area is never actually produced by the machine. In the language of Computational Naturalism, Lemma 2 is false for an infinite area; the cardinality of an open on the right area is excluded from being a Natural Number because a Natural Number Machine cannot reach it in the first order.

    - -

    So then can we add a property to cardinality, such that a second order analysis could use this property to continue downstream analysis? In short we could say that cardinality has no first order value, but it has a second order one. This is analogous to inventing a new type of number, analogous to a complex number with a second component. I.e., there is no 'real' solution, but there is an 'imaginary' one. Or analogous to error algebra, where a number value is replaced with a rule on how to handle downstream operations when it is given as an input. +

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

    -

    Such a value would be a new Turing Machine, one that composes a call to the never halting Natural Number machine followed by an increment operation. It cannot be run, but it perfectly explains the situation to an analyst. Perhaps we name this machine \aleph_0. +

    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.

    -

    What if extent was used instead of cardinality?

    - -

    - Had extent been used instead of cardinality, we would lack the final increment step in the three step computing procedure. However, step 2 still cannot complete. Rather than a value, the result of the second order analysis would be a machine that produces ever larger Natural Numbers. We can call this machine \aleph_{-1}. -

    +

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

    -

    - Now here is an interesting result: +

    Hence what would be useful for a replacement of the IEEE 754, would be variable precision number standard. There is one being proposed by John Gustafson called the Posit number representation John L. Gustafson, The End of Error: Unum Computing, Chapman and Hall/CRC, 2015. Posits serve as a hardware friendly alternative to IEEE 754 floating point numbers, providing variable precision mechanics..

    - - \aleph_{0} - \aleph_{-1} = 1 - - -

    - Neither machine can be run. However we can compose the two machines, then simplify the composition. When we do so, the ever larger Natural Number machines annihilate each other, and the increment machine remains. The increment machine can be run, so we end up with an output value. +

    This section reviewed finite difference methods as a means to implement function extensions. A person should notice that finite differences are one among many methods for extending functions, and they are not always the best choice. In modern computing it is not common to implement function extensions. Rather it is more common to increment a value across a domain, while completely repeating the evaluation for each new domain value, for example when computing values to place on a plot. However, independent of their importance in applied computing, function extension and difference methods are of theoretical importance for analysis, particularly when applied to nonstandard analysis. These speak to the thesis of computational naturalism in the derivation of mathematics, rather than as a proposed method of implementing computational programs.

    - -

    Size

    - -

    Consider the case of a partitioned tape. Then consider that we write a gasket, such that we have a higher level Turing Machine that considers each of the areas of the partition as a cell. So then, initially the Turing machine starts with its head on the leftmost area, stepping right steps to the right neighbor area etc. In this manner we abstract the concept of a cell to areas. A length then becomes a count of areas; however the size remains a count of the cells. Something similar is done in the C language, where the length of an array is a count of the elements in the array, but the size of the array is a count of bytes. A byte being an addressable unit in physical memory, and thus the underlying cell that everything is built up from.

    + Multiple machines and sharing tapes @@ -3913,7 +3937,7 @@ Now suppose defining a Turing Machine that initially has the head on the leftmos

    Does computation theory matter to computing?

    - Let us put this into perspective. Suppose in ancient Roman times that a clock tick for a computer was scaled to be one day long. Under this scale, a single nanosecond of real world execution time equates to three days. Suppose a program initiated a read request for a location in memory on the Ides of March, the date when Caesar was assassinated on -0043-03-15. The following table provides the historical date that the variable value would finally be loaded into the processor, depending on the memory tier being accessed: + Let us put this into perspective. Suppose in ancient Roman times that a clock tick for a computer was scaled to be one day long. Under this scale, a single nanosecond of real world execution time equates to three days. Suppose a program initiated a read request for a location in memory on the Ides of March, the date when Caesar was assassinated on 0043-03-15. The following table provides the historical date that the variable value would finally be loaded into the processor, depending on the memory tier being accessed:

    -- 2.20.1