From b3eca3089bbbb3e6fa23d957855711cd83523eb5 Mon Sep 17 00:00:00 2001 From: Thomas Walker Lynch Date: Thu, 23 Jul 2026 14:14:25 +0000 Subject: [PATCH] . --- document/book/TM-2026.html | 111 +- document/book/TTCA_machine.svg | 17984 ++++++++++++++++++++++--------- document/book/gemini-svg.svg | 161 - 3 files changed, 12944 insertions(+), 5312 deletions(-) delete mode 100644 document/book/gemini-svg.svg diff --git a/document/book/TM-2026.html b/document/book/TM-2026.html index 578281a..a920f6b 100644 --- a/document/book/TM-2026.html +++ b/document/book/TM-2026.html @@ -1221,18 +1221,18 @@

Adding heads is not a general method for improving performance complexity. A quadratic performance improvement does not always occur and when it does it is not strong enough to change the asymptotic performance if there are higher-order terms in a step count polynomial. Furthermore, eliminating shuttling will never reduce a linear step count to a constant time step count; the simple reason is that n is unbounded, while adding k heads can only divide the work by a fixed constant k. Consequently, while the transformation is consequential in specific cases, it cannot change the broader time complexity class.

-The TTCA Machine design + The TTCA Machine design
Figure 1: A Turing Machine
Figure 1 A Turing Machine
-

The prior chapter on the computation theoretic TTCA machine serves as the architectural template. The controller is practical to implement, and it is specified in terms of tables. In order to extend the tape, the machine will stop and ask the operator to mount a new reel. As this is a constant time operation, it is computation theoretic inconsequential.

+

The prior chapter on the computation theoretic TTCA machine serves as the architectural template, with only a few variations. The architecture has no 'unspecified' symbol. Rather an actual value is transacted. The controller is practical to implement, and it was specified in terms of tables, which can be implemented. In order to extend the tape, the machine will stop and ask the operator to mount a new reel. As this is a constant time operation, it is computation theoretic inconsequential.

Because a Turing Machine can only reach another cell further out on the tape by stepping to it, space complexity and time complexity are related. A program that runs for ten steps can consume at most ten cells of tape. However, if that program merely bounces between two cells, it will require less than that—precisely two cells. A program that counts the number of characters on its input tape using Arabic notation will execute in asymptotically linear time, as demonstrated later in the section analyzing the increment operation. Its working footprint, however, will be logarithmic in space complexity, because that is how fast an Arabic representation grows with a count.

-

If a program ran at human operator speed, it would be quite slow, likely so much so that the operator waiting for the results would abandon the process. This highlights another attribute of good programs: utility. It also demonstrates one of the limitations of computation theoretic analysis. Nevertheless, formal analysis retains a critical purpose. The execution time of an exponential time program explodes relative to the length of the input, quickly requiring more time than the universe has existed. Computation theory does not instruct upon wall-clock time; rather, it describes behavior against increasing input lengths for worst-case operands, which has important implications for wall-clock time.

+

If a program ran at human operator speed, it would be quite slow, likely so much so that the operator waiting for the results would abandon the process. This highlights another attribute of good programs: utility. It also demonstrates one of the limitations of computation theoretic analysis. Nevertheless, formal analysis retains an important purpose. The execution time of an exponential time program explodes relative to the length of the input, quickly requiring more time than the universe has existed. Computation theory does not instruct upon wall-clock time; rather, it describes behavior against increasing input lengths for worst-case operands, which has important implications for wall-clock time.

The same can be said for space complexity. Suppose a program doubled its memory footprint each time its input string increased by one. If an individual proton could hold one bit of memory, say via its spin, an input increase of merely 270 characters for such a program would exhaust all the protons in the universe. Allocating a cell of space requires the machine to take a step, so time complexity is at least equal to space complexity. If a computer ran at 10 GHz and a step required 10^{-10} seconds, this same extension would require 6 \times 10^{63} years. For perspective, the universe is approximately 1.4 \times 10^{10} years old.

@@ -1241,11 +1241,11 @@

As a possible practical solution, note that if the program does not exhaust the current tape, the operator will never be called. How much tape is required to ensure this? An analyst could choose worst-case operands and measure the footprint when the program runs. At first, this appears to be the familiar 'my number is bigger than your number, I'll tell you mine after you tell me yours' game, which can be viewed as the definition for the countable infinity. However, there is a loophole. Running the system once with the worst-case operands to establish time and space ceilings guarantees the program can be allocated sufficient resources later for other operands. This is a practical approach, provided the program is a workhorse utility rather than an algorithm searching for a solution to an unsolved problem that only needs to run once.

-

Suppose a controller is not analyzed to determine its computation theoretic complexity, or even tested against worst-case inputs, but is instead run with random or everyday input to gather performance measurements. This process is called profiling. After many runs, a programmer might surmise the behavioral limits of the program. However, many programs are neither linear systems nor smooth functions. With a different set of inputs than those used for profiling—perhaps even values strictly adjacent to prior inputs—the program behavior can shift drastically. Take, for example, the Pentium divider. It did not matter how many millions of times the result was accurate; the fact remains that customers later found an input that yielded wildly inaccurate results. Only by elevating the analysis to the structural logic of the code can such an eventuality be categorically ruled out. This is why the K5 transcendental function development project included a proof writing, see 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.

+

Suppose a controller is not analyzed to determine its computation theoretic complexity, or even tested against worst-case inputs, but is instead run with random or everyday input to gather performance measurements. This process is called profiling. After many runs, a programmer might surmise the behavioral limits of the program. However, many programs are neither linear systems nor smooth functions. With a different set of inputs than those used for profiling, perhaps even values adjacent to prior inputs, the program behavior can shift drastically. Take, for example, the Pentium divider. It did not matter how many millions of times the result was accurate; the fact remains that customers later found an input that yielded wildly inaccurate results. Only by elevating the analysis to the structural logic of the code can such an eventuality be categorically ruled out. This is why the K5 transcendental function development project included a proof writing phase, see 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.

Head unit, HU

-

An HU contains a head and a local controller. The local controller supports these commands, but only when a tape is mounted under it:

+

An HU contains a head and a local controller. The local controller supports these commands:

  1. read → σ
    2. @@ -1253,21 +1253,22 @@
  2. status → γ
-

One or more head units are plugged into the TTU, which is described in the next section. Commands are only sent to the head unit when a tape is mounted on the TTU, and they are sent by the TTU. The machine at large does not have an interface to the HU. - The status command returns the name of the cell type of the cell the head is on. The head controller communicates with other components of the machine to ascertain the status, which is one of:

+

One or more head units are plugged into the TTU, which is described in the next section. Commands are only sent to the head unit when a tape is mounted on the TTU, and they are sent by the TTU. The machine at large does not have an interface to the HU.

+ +

The status command returns the name of the cell type of the cell the head is on. The head controller communicates with other components of the machine to ascertain the status, which is one of:

    -
  1. leftmost → σ
    2. +
  2. leftmost
  3. rightmost
    4. -
  4. medial → γ

    -
  5. island → γ

    +
  6. medial
    7. +
  7. island
-

A status of rightmost or island would never be returned for a computer theoretic Turing Machine tape, but it can be for an area of a tape, and such an area can be virtual tape. We will use this model to reconcile the difference between the architectural finite tape, and that of the infinite theoretical tape. Area is discussed in the section dedicated to that topic.

+

A status of rightmost or island would never be returned for a computation theoretic Turing Machine tape, but it can be for an area of a tape, and such an area can be a virtual tape, as is described in the later section on Area.

Tape transport unit, TTU

-

The TTU is where tapes are mounted and unmounted, and heads are plugged into. When multiple heads are plugged in, the controller passes control among them so it appears that heads never collide. The TTU controller has these components: +

The TTU is the component where tapes are mounted and unmounted, and where read/write heads are installed. When multiple heads are plugged in, the controller passes control among them so it appears that heads never collide. The TTU controller has these components:

    @@ -1277,17 +1278,17 @@
  1. a single symbol FIFO command buffer, written by the programmed controller, acted upon immediately by the TTU
-

The TTU interfaces with the executor, which in turn contains the customer programmed control unit, the CPCU. The executor is single threaded, and issues commands to the TTU.

+

The TTU interfaces with the executor, which in turn contains the customer programmed control unit, the CPCU. The executor is single-threaded and issues commands to the TTU:

    -
  1. read head → σ → σ
    2. -
  2. write σ head
    3. -
  3. status head → γ
    4. +
  4. read head → σ
    5. +
  5. write σ head
    6. +
  6. status head → γ
  7. left
  8. right
-

For the first three commands the head argument multiplexes the command to the specified head. If the TTU has one head, the head argument is optional. The last two commands cause the tape to be moved, such that relatively, the head moves left or right by one cell.

+

For the first three commands, the head argument multiplexes the command to the specified head. If the TTU has one head, the head argument is optional. The last two commands cause the tape to be moved such that, relatively, the head moves left or right by one cell.

The customer programmed control unit, CPCU

@@ -1333,36 +1334,80 @@ -

The top section has two toggle buttons. One turns the machine on, the other selects run or single step mode. Just to the left of the two toggles are indicator lights. To the right of the toggle buttons are two push buttons. One for reset, which sends the machine back to S0, the other for stepping the machine when it is in single step mode. -

+

The top section has two toggle switches. One turns the machine on, and the other selects run or single-step mode. Just to the left of the two toggles are indicator lights. To the right of the toggle switches are two push buttons. One is for reset, which sends the machine back to state S_0, and the other is for stepping the machine when it is in single-step mode.

+ +

The second section is the transition condition panel. It is a rectangular matrix 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 gate symbol.

-

The second section is the next state panel. It is a rectangle of holes that fit the banana plugs ends of a patch chord. Each column is a current state. Each row is a gate symbol.

+

Below the transition condition panel is the destination state panel. All three rows of this panel are functionally identical; they merely provide physical space so multiple patch cords can be plugged into a single state column.

-

Below the rectangular next state panel, is the next state panel. All three rows of the panel are the same, they nearly create room so multiple patch cords can be plugged in.

+

Below the destination state panel are the default state transition panels. There is one for the state default transition, and one for the global default transition, as described by the computation theoretic TTCA machine.

-

Below the next state pantel are the default state transition panels. One for the default next state, and one for the global next state, as described by the TTCA theoretic machine.

+

To program the controller, the programmer connects the patch cords. Shown in the diagram is a patch cord routing from the (S_2, g_2) intersection to S_3. This physically realizes a state transition arc for the controller. If the active gating value has no patch cord plugged in, the machine instead uses the state default transition. For a state default transition, a patch cord is plugged into the column for the current state on the default transition panel and routed to the desired next state. Finally, if no patch cord is plugged in that would otherwise define the next state, the global default patch cord is followed.

-

To program the controller, the programmer plugs in patch cords. Shown in the diagram is a patch cord going from S2,g2, to S3. This realizes a state transition arc for the controller. If the gating value has no patch cord plugged in, the machine instead uses the default transition. For a default transition a patch cord is plugged into the column for the current state, on the default transition table, and that is patched into the next state. Finally, if not patch cord is plugged in that would define the next state, the global default patch cord is followed to the next state.

+

Not shown in this diagram is a row of toggle switches, one per state; if flipped on, the corresponding state becomes a halting state. Also omitted is the action selection panel. It is another rectangular matrix, with rows for actions and columns for the states, allowing each state to be assigned to a specific machine action. Note that this describes the control panel for a single-head TTU machine.

-

Not shown on this diagram is the row of toggle switches, one per state, that if flipped on, the state becomes a halting state. Also not show is the action selection panel. It is another rectangle, with rows for actions, and a top row for the state. Each state can then be assigned to an action. Note, this is the control panel for a single TTU machine.

The machine block diagram

+
+ Figure TTCA block diagram +
Figure TTCA block diagram
+
-

The structural portion of the programmed controller:

+

Components

    -
  1. the TTU command set as selectable actions
    2. -
  2. the current state register, decoded to illuminate the panel light
    3. -
  3. the reset control line, from the reset button
    4. -
  4. the clock
    5. -
  5. multiple comparators, on bus from the g register
    6. +
  6. Executor
    7. +
      +
    1. clock
      2. +
    2. Control Panel
      3. +
        +
      1. Power Switch
        2. +
      2. Single Step Switch
        3. +
      3. Reset Button
        4. +
      4. Single Step Button
        5. +
      +
    + +
  7. g register
    8. +
  8. status bus
    9. +
  9. Status Decoder
    10. + +
  10. d register
    11. +
  11. data bus
    12. + +
  12. Customer Programmed Control Unit, CPCU
    13. +
      +
    1. current state register, q
      2. +
    2. next state table
      3. +
    3. action table
      4. +
    4. halt state decoder and switches
      5. +
    +
+ +

The Executor provides the ultimate control of the machine, telling registers when to sample or latch, enabling bus drivers, and distributing the clock and reset signals. These control signals are not shown in this block diagram (it is not a schematic).

+ +

There are two registers in the register file. The d register, holds data values that are being carried. The d register has no path to the customer programmed controller. The g register holds the status value used for gating the controller. +

+ +

The symbols used for status and gating the programmed controller occur within an enumeration. Each is given a value that corresponds to its the row index on the control panel. The value on the status bus then is latched by the g register and goes to a decoder which has one output line per symbol. Decoding the status then results in a one hot value sent to the state transition logic for gating to the next state. Due to the enumeration, the decoder displaces the need for a bank of comparators each checking for a distinct symbol on the status bus.

+ +

The halt state detection works in a similar manner. The current state register is also a one hot encoding, with a bit per state. A wire from each bit goes to the executor where it meets the bank of halt switches. the output of which is wire OR'ed together to create the halt signal. Thus for halt to be asserted, the given state must be turned on in the switch bank. +

+ +

Upon reset the current state register all of the machine registers are cleared to zeros. Also, the power on switch has a capacitor timer that holds reset for a safe amount of time while the machine comes up.

+ +

Timing

+ +

A magnetic tape head reads when the tape is moving, so ironically it is like the emacs cursor. The read will occur when the machine steps and the data will be waiting in the data buffer for a read command. The head will wait at the other side of the cell. Unlike the theoretical tape, there is interstitial space between the cells where the head can wait for the next command, then swipe further right. In a real machine blocks of cells will always be read, and the buffer will be much deeper.

+ +

On a read for the g register

-

The comparators are used to used to match the identifier with a the values read from each of the buffers. Note that if the same next state is specified for the same start state, then it is the same as though the identifiers are in disjunction. Also the no-op command to create conjunctive decisions. Hence as a shorthand notation arcs can be labeled with propositions made from the buffer values.

+

So on the falling edge of the clock, the state is latched. State signal ripples through the action table. As the q register is stored one hot, this happens very quickly. The command arrives at the TTU, and is decoded. The decoder can be avoided by having the action table send the already decoded value.

-

Upon reset the current state register is written with the initial state. When the current state register is set to the halt state, the machine stops. If no next state is found for a given state, the error state is written to the current_state_register and the machine halts.

+

As the read is to be used for control, i.e. to cause a state transition, the bus control signals will be setup such that the status register of the TTU is sent through the g register, through the g value decoder, and in to the customer programmed controller. There the one hot value will pass through a patch cord, destined to be latched at the next falling clock edge.

-

On the rising edge of the clock, the TTU writes the data and status buffers, and the state command is written to the TTU command buffer. On the falling edge of the clock, the TTU completes the state command, and the next state is written to the current state register.

+

On the rising edge of the clock, the gate value is latched. The flip flops that drive the gate lights are sampled. This assures that the next state transition signals are held stable ...

Stored Program Control

diff --git a/document/book/TTCA_machine.svg b/document/book/TTCA_machine.svg index d5a977f..1cfc912 100644 --- a/document/book/TTCA_machine.svg +++ b/document/book/TTCA_machine.svg @@ -22,9 +22,9 @@ inkscape:pagecheckerboard="0" inkscape:deskcolor="#d1d1d1" showgrid="true" - inkscape:zoom="0.96102398" - inkscape:cx="534.3259" - inkscape:cy="311.12647" + inkscape:zoom="1.5540715" + inkscape:cx="467.80344" + inkscape:cy="447.21236" inkscape:window-width="1920" inkscape:window-height="1131" inkscape:window-x="0" @@ -33,7 +33,54 @@ inkscape:current-layer="svg311">CPCUCPCU(Programmed Controller)Next StateTable (δ)(Programmed Controller)g REGISTER(Gate/Status)d REGISTERNext StateTable (δ)g registerComparators== σ== leftmost==rightmostgdecoder== σ== leftmost==rightmostTTU [n]TTU [n]TTU [1]TTU [1]TTU [0]TTU [0]DatadataUNIT 0TAPETAPE......qstatusq one hotstatuscommandMuxcommandControlAction TableTable (λ)MuxdMuxHaltSwitchBankEXECUTORr/wControl + d="M 176.95293,286.74145 V 228.99326" + id="path28482" + style="stroke-width:6;stroke-dasharray:none" + sodipodi:nodetypes="cc" /> diff --git a/document/book/gemini-svg.svg b/document/book/gemini-svg.svg deleted file mode 100644 index 2152e1e..0000000 --- a/document/book/gemini-svg.svg +++ /dev/null @@ -1,161 +0,0 @@ - - - - - - - - - - - - - - - - - Reset Button - - - - Clock - - - - - EXECUTOR - - - Reset Logic - - - Step/Phase - Control - - - Step Pulse - - - - CPCU - (Programmed Controller) - - - Next State - Logic (δ) - - - Action - Logic (λ) - - - q - - - - g REGISTER - (Gate/Status) - - - d REGISTER - (Data) - - - q REGISTER - - - - - - Comparators - - - == σ - - - == leftmost - - - == unspecified - - - Default (dflt) - - - - To Next State Logic - - - - - TTU [n] - - - - TTU [1] - - - - TTU [0] - - - Command - Buffer (FIFO) - - - Status - Buffer (FIFO) - - - Read Data - Buffer (FIFO) - - - HEAD UNIT 0 - (Local Controller) - - - - - - TTU Command Bus - - - - Status Bus - - - - Read Data Bus - - - - Write Data - - - - - - - - - - - - - TAPE - ... - - - - Read / Write - - -- 2.20.1