From c5df51119e7978b018beb38cd0a29364b957b3ce Mon Sep 17 00:00:00 2001 From: Thomas Walker Lynch Date: Mon, 8 Jun 2026 16:19:06 +0000 Subject: [PATCH] doc work --- document/TM-2026.html | 542 +++++++++++++++++++++++++----------------- 1 file changed, 324 insertions(+), 218 deletions(-) diff --git a/document/TM-2026.html b/document/TM-2026.html index 0212791..3143e70 100644 --- a/document/TM-2026.html +++ b/document/TM-2026.html @@ -18,25 +18,33 @@

Preface

- This is the first volume of the book Tom's Turing Complete Computer Architecture. The initial chapters here set down the theory of the TM, Tape Machine. Following the theory chapters is a description of a software library for using the TM as a general iterator and container. The TM software library was first released in 2022 for Common Lisp on MELPA. Since then, ad hoc versions were developed in C, Java, and Python. The TM-2026 GitHub project has as its purpose unifying the various language versions with a revised command language. + This is the first volume of the book Tom's Turing Complete Computer Architecture. The initial chapters here set down the theory of the TM, Tape Machine. Following the theory chapters is a description of a software library for using the TM as a general iterator and container. The TM software library was first released with the first edition of this volume in 2022 written in Common Lisp and placed on MELPA. Since then, ad hoc versions were developed in C, Java, and Python. The TM-2026 GitHub project has as its purpose unifying the various language versions with a revised command language. The larger objective of these volumes is to morph the Turing Machine into a modern architecture, thus bridging computation theory to computing. The TM software library is a useful fallout of this work.

Introduction

- In their 1928 book Grundzüge der theoretischen Logik, Hilbert and Ackermann asked the question, "Does there exist an algorithm that, given any statement in first-order logic, can decide whether that statement is universally valid (i.e., provable from the axioms)?" They called this the Entscheidungsproblem, which in English translates to the decider problem. The Turing machine was introduced by Alan Turing in 1936 . The abstraction was formally refined in early textbooks by Stephen Kleene , Martin Davis , and Marvin Minsky , leading to the modern standard presentations by authors such as John Hopcroft and Jeffrey Ullman , as well as Lewis and Papadimitriou . Turing used his model to prove that no decider program can be written such that, when a program is given to the decider to analyze, the decider can always answer 'yes' or 'no' to the question of whether the given program will halt. This resolved the Entscheidungsproblem in the negative. + In their 1928 book Grundzüge der theoretischen Logik , Hilbert and Ackermann asked the question, "Does there exist an algorithm that, given any statement in first order logic, can decide whether that statement is universally valid (i.e., provable from the axioms)?" They called this the Entscheidungsproblem. The Turing Machine abstraction was introduced by Alan Turing in his 1936 paper and used as a device to prove that no first 'analyzer' program can universally analyze and decide if a second 'studied' program will halt when it is run . An answer to this halting problem question, i.e., "The studied machine halts," or "The studied machine does not halt," would indeed be a statement in first order logic. Thus, by showing no analyzer can universally make such a determination, Turing proved that no decider could exist for the Entscheidungsproblem.

- For Hilbert and Ackermann's question to be truly answered by Alan Turing, a mathematical isomorphism between Turing Machine programs and algorithms as understood by Hilbert must be established. Turing addressed this in his paper, and with many reviewers over decades acting as a jury, he did so successfully. + The Turing Machine formalism was further refined and turned into a basis for computation theory in early textbooks by Stephen Kleene , Martin Davis , and Marvin Minsky , leading to the modern standard presentations by authors such as John Hopcroft and Jeffrey Ullman , as well as Lewis and Papadimitriou .

- For Turing's purposes in his 1936 paper, the equivalence between algorithms and Turing Machine programs was sufficient to tie the theory he presented into the targeted problem. However, in our computing epoch the Turing Machine can be used as the basis of computation theory, so if we could connect it to modern computer architectures, we would know that computation theory results apply to them. If the connection happens to be imperfect, that might elucidate the limitations of relying upon computation theory. + For Turing's proof to be known to apply to the + Entscheidungsproblem, he had the additional burden of establishing + that Hilbert and Ackermann's intuitive concept of an algorithm was functionally equivalent to a Turing Machine program. Turing + addressed this issue in his paper, and with many reviewers + over decades acting as a jury, he did so successfully.

- Although the Universal Turing Machine conceptually introduced programs stored as data on a tape, Turing could not provide the formal explanation of the connection to modern architectures, if for no other reason than the fact such architectures did not yet exist. The practical engineering context of 1936 was limited to calculating machines programmed via patch panels. Though Charles Babbage's 1842 Analytical Engine touched on these concepts, they would wait until the 1940s to re-emerge. For example, there is no explanation in his paper as to why a von Neumann architecture machine (1945) running a program would have the same computation theoretic results as a Turing Machine (1936). Here, by modern, I refer to physical computer organizations utilizing random-access system memory, dedicated instruction fetch streams with dynamic branching, and discrete processing units. To establish this missing connection, the volumes of the TTCA, starting in the following chapters, transform the Turing Machine into a modern architecture in a stepwise fashion, while ensuring that at each step the modifications are inconsequential to existence proofs and complexity class results. + For Turing's purposes in his 1936 paper, establishing functional equivalence between algorithms and Turing Machine programs was sufficient. Today, however, the Turing Machine can also serve as a foundational model for computation theory. Thus, to guarantee that computation theoretic results apply to modern architectures, a rigorous connection between the abstract model of the Turing Machine and that of modern computer architectures is required. Imperfections in this connection would then point to limitations in applying computation theory to modern programs. +

+ +

+ Although the Universal Turing Machine conceptually introduced programs stored as data on a tape, Turing could not provide a formal connection to modern architectures, simply because such architectures did not yet exist. Here, by modern, I refer architectures utilizing random-access system memory, dedicated instruction fetch streams with dynamic branching, and discrete processing units. Though Charles Babbage's 1842 Analytical Engine touched on these concepts, they would wait until the 1940s to re-emerge. The practical engineering context of 1936 was limited to calculating machines programmed via patch panels. Hence, for example, there is no explanation in his paper as to why a von Neumann architecture machine (1945) running a program would exhibit the computation theoretic results derived from a computation theory based on the Turing Machine (1936). To establish this missing connection, the volumes of the TTCA, starting in the following chapters, transform the Turing Machine into a modern architecture in a stepwise fashion, while ensuring that at each step the modifications are inconsequential to computational theoretic existence proofs and complexity class results.

@@ -44,7 +52,7 @@

- In 1967, Marvin Minsky addressed this very topic in saying: "We need not think of the machine's tape as infinite. We imagine instead that the machine begins with a finite tape, but that, whenever an end is encountered, another unit of tape is attached." In 1967, this was a perfectly natural thing to suggest, as computers utilized magnetic tape memory on manually mounted reels, and it was entirely possible for a computation to stop and request a new reel of tape to be mounted. Contemporary computer architectures could achieve similar effects by swapping memory pages out to ever-expanding pools of networked auxiliary storage. In practice, however, once local storage is depleted, the operating system abruptly terminates the process rather than pausing to autonomously provision additional capacity. This observation highlights the necessity to consider the OS as part of the architecture, i.e. information that is valuable to programmers when they design the logic of programs. + In 1967, Marvin Minsky addressed this very topic in saying: "We need not think of the machine's tape as infinite. We imagine instead that the machine begins with a finite tape, but that, whenever an end is encountered, another unit of tape is attached." In 1967, this was a perfectly natural thing to suggest, as computers utilized magnetic tape memory on manually mounted reels, and it was entirely possible for a computation to stop and request a new reel of tape to be mounted. Contemporary computer architectures could attempt to achieve similar effects by swapping memory pages out to ever-expanding pools of networked auxiliary storage. However, if they did this, they would eventually reach an address space depleted fault. In practice, once local storage is depleted, the operating system abruptly terminates the process rather than pausing to autonomously provision additional capacity.

@@ -59,7 +67,8 @@ Turing's a-machine utilizes binary. George Boole's work (1847, 1854) was well established by then, so from a theoretical standpoint, it was a sensible simplification. However, utilizing binary within the context of a machine effectively bridged the gap to the more practically minded engineers of the time. Alan Turing's paper arrived at the same time that switched telephone networks had reached a scale that made them difficult to maintain without systematic approaches. These networks were built upon electromechanical relays, which were decisively binary devices. At least seven men in addition to Alan Turing appear to have independently contemplated the intersection of Boolean algebra, logic, and physical computing: Victor Shestakov (1935, proposed mapping Boolean algebra to electromechanical relay circuits), Konrad Zuse (1936, adopted base 2 architecture to bypass the physical complexity of decimal mechanical gears), Akira Nakashima (1936, published the mathematical equivalence of Boolean algebra and two-terminal switching networks), Louis Couffignal (1936, proved calculating machines must shift to binary linkages to reduce physical friction), Claude Shannon (1937, published the definitive mathematical proof mapping Boolean algebra to electrical relays), George Stibitz (1937, constructed the first electromechanical binary adder), and John Vincent Atanasoff (1937, adopted binary to keep the vacuum tube count of electronic circuits physically viable).

-

The computer manufacturing abstraction stack

+ +

The computer design abstraction stack

There are a number of discernable levels to the computer manufacturing abstraction stack, going from the highest down to the lowest level: @@ -75,11 +84,15 @@

- The bottom level is concrete, while the others are abstract. + Mathematical logic underpins the computation theory layer. Computation theory speaks of the time and space complexity of algorithms and the existence of solutions to decider problems, which in turn guides the goals of the architecture and organization layers.

- A realization is a physical box full of plastic, metal, fiberglass, and silicon, along with a smattering of exotic materials. A realization is made by manufacturing engineers, technicians, and product line workers, with the assistance of some of the most sophisticated machines ever built by humankind. + An architecture provides the programmer with information that is valuable when designing the logic of programs. This includes all ilks of programmers, including OS programmers, driver programmers, and application programmers. This is sometimes called the instruction set architecture. In addition to specifying the instructions, it includes specifying the behavior of the interrupt subsystem, the method of doing I/O (typically memory-mapped or dedicated I/O instructions), DMA, the special registers and their effects, and the standards to be followed for each if any. More recently, this also includes specifying how programs can make use of secure areas. The architecture is specified by an architect. +

+ +

+ Organization is the register-transfer level description of the machine, which includes internal buses, external buses and the state machines that implement the protocols used, control units, interrupt structures, methods of doing I/O, and ALU layout. It dictates the logical arrangement of hardware and the procedures that force the data to flow to satisfy the architectural constraints. The organization is made by a design architect. This level, and the next level, are defined in detail in the classic text by Hamacher, Vranesic, and Zaky .

@@ -87,19 +100,176 @@

- Organization is the register-transfer level description of the machine, which includes internal buses, external buses and the state machines that implement the protocols used, control units, interrupt structures, methods of doing I/O, and ALU layout. It dictates the logical arrangement of hardware and the procedures that force the data to flow to satisfy the architectural constraints. The organization is made by a design architect. This level, and the next level, are defined in detail in the classic text by Hamacher, Vranesic, and Zaky . + A realization is a physical box full of plastic, metal, fiberglass, and silicon, along with a smattering of exotic materials. A realization is made by manufacturing engineers, technicians, and product line workers, with the assistance of some of the most sophisticated machines ever built by humankind.

- An architecture provides the programmer with information that is valuable when designing the logic of programs. This includes all ilks of programmers, including OS programmers, driver programmers, and application programmers. This is sometimes called the instruction set architecture. In addition to specifying the instructions, it includes specifying the behavior of the interrupt subsystem, the method of doing I/O (typically memory-mapped or dedicated I/O instructions), DMA, the special registers and their effects, and the standards to be followed for each if any. More recently, this also includes specifying how programs can make use of secure areas. The architecture is specified by an architect. + If a computer manufacturer keeps the architecture as a constant, all other levels can change, and a customer will be able to run the same software. The same organization can be used with different implementations. Minor changes in manufacturing process can sometimes be used with an older implementation, for example a simple transistor shrink.

- Mathematical logic underpins the computation theory layer. Computation theory speaks of the time and space complexity of algorithms and the existence of solutions to decider problems, which in turn guides the goals of the architecture and organization layers. + The ENIAC, sometimes credited as the first electronic computer, is an extreme example of using an older implementation in a new process. Rings of ten tubes were wires in circular shift registers so as to act like gears. Binary switch implementations were found in relay computers, and then in the Anastov-Berry machine and ESAC. +

+ +

The levels are not independent

+ +

+ The layers are merely idealizations. In both practice and theory it is not possible to completely disentangle them. On a new machine of the same architecture, it is common that some software will require updates to run, and almost certainly specific operating system support will be required. +

+ +

+ An architect almost always has a reference organization in mind, and design architects work with design engineers to know what is practical, and design engineers work with manufacturing engineers to know what can be built. +

+ +

+ The common understanding of the word 'architecture' is that of a what Hamacher and Zaky calls an organization. For example, even the most experienced of architects will say things like a microprocessor has a "superscalar architecture", though whether a processor is a scalar, superscalar, or VLIW machine is clearly a question of computer organization. +

+ +

+ In fact, architecture instructs organization. When we design an instruction set that has load instructions, it implies that there will be an instruction fetch, and thus an instruction bus. Furthermore the load data has to come from somewhere, so there will be data fetch and a data bus. Could both be the same bus? If not, then we have a "Harvard Architecture". The fact is, almost no one involved in computer design completely divorces architecture from organization. +

+ +

+ This cascades down the stack, as organization instructions implementation, etc. For example, if the architecture has an instruction that names one of N registers as an operand, then the organization has a register file that data flows to and from, and busses to carry that data, the design will specify a register file and layout the busses, and the manufacturing people will build them. +

+ +

Consequentiality

+ +

+ The Turing Machine is an abstraction, as are architectures, organizations, and implementations. Only a computer realization is concrete, but even then we can make observations that are analogous to properties of an abstraction. +

+ +

+ When transforming machine M_0 into machine M_1, we say the transformation is inconsequential if any computation theory analysis applied to M_1 will yield the same answer as it would if applied to M_0; otherwise, the transformation is consequential. The remainder of this section says the same in formal language. +

+ +

+ Suppose that machine abstraction M_1 is the result of a transformation, T, applied to machine abstraction M_0. +

+ + + M_0 \xrightarrow{T} M_1 + + +

+ We can then assign a property to T called its consequentiality, as follows. +

+ +

+ We begin with a set of questions that are legal to ask under computation theory C for a machine M_0: +

+ + + Q_0 = C, M_0 \colon \{ \langle q, d \rangle \} + + +

+ Here q is a question, and d is the domain of computational inputs for machine M_0 under C. This is given information. +

+ +

+ Then we pose these questions, and receive the answers. +

+ + + A_0 = C(M_0, Q_0) + + +

+ Here A_0 is a set of vectors, with each vector having the form \langle a, q, d \rangle, where a is the answer, and the remaining components distinguish the correspondence with the question. +

+ +

+ If any question in Q_0, for the given machine over the given domain, is not legal to ask of M_1 under C, then we say that T is consequential over Q_0. Otherwise, we continue with asking the same questions about M_1: +

+ + + A_1 = C(M_1, Q_0) + + +

+ If and only if A_0 = A_1, we say that transform T is inconsequential over Q_0; otherwise, we say T is consequential over Q_0. +

+ +

+ Now let us generalize. First, let us define the set of all input domains that are legal for machine M_0, and can be analyzed using C. +

+ + + D(C, M_0) \rightarrow D + + +

+ Then let us define the set of all questions of decidability, along with the two questions of time and space complexity, that can legally be asked under C of machine M_0 over the domains in D. +

+ + + Q(C, M_0, D) \rightarrow Q + + +

+ We must establish the theoretical baseline by posing these generalized questions to our initial machine: +

+ + + A_0 = C(M_0, Q) + + +

+ If any question in Q is not legal to ask of M_1 under C, then we say that T is a consequential transform. Otherwise, we continue on to ask the same questions concerning M_1: +

+ + + A_1 = C(M_1, Q) + + +

+ If and only if A_0 = A_1, we say that transform T is inconsequential under C, and otherwise it is consequential under C. As we are only discussing C in this paper, the "under C" qualification can be dropped as it is clear by context. +

+ + + +

Is realization consequential?

+ +

+ + + +

+ The very title of this book has built in the same pitfall, as mostly what we discuss is the flow of data between named components, i.e. register transfer level description, which is organization. Computer architecture is often expressed by describing a reference organization. +

+ + + + +

+ A key question then, do different computer organizations have consequential effect. By consequential effect we mean to ask if they exhibit different behavior than that predicted by computer theory. It is certainly possible to force this to happen. Suppose for example, we make a computer that has a clock such that clock pulses are exponentially further apart on every clock tick. Then a linear time program running on the computer would have logarithmic time asymptotic behavior with ever more input data. +

+ +

+ A slowing clock could happen due to some peculiar extenuating circumstances, perhaps because a battery is going dead, but is not a normal situation, and there is a reason for that. If a computer works with a clock period of p0, then any longer clock period would be unnecessarily wasting time.

- The Turing Machine is a computation theory object that is suggestive of a simple architecture; however, a little work is needed to complete architecture analog. The fundamentals are present, the read/write head, the tape, the procedure for using the tape, but other components are missing. The manipulation of symbols remains ungrounded. The tape is not well defined. The use of emptiness is non-architecture like. The tape transport is not articulated, though it is implied. The read buffer that holds a value read, so the programmed controller can do write without clobbering the read data needed for the next transition is not identified as a component. As we proceed, we will likely discover other missing components. + Nor is it practical to go the other direction, and make an exponential time program run in linear time by having an every faster clock. The simple reason being that the designers will have already set the clock to the fastest that it can safely go. +

+ +

+ Adding two Arabic representation numbers of ever lengthening operands is asymptotically a linear time problem. For numbers of fixed length, where that fixed length is not very long, a lookup table can be used. As such each addition would require the same amount of time, but this is merely making the worse case time for bit widths up to the lookup table with the time for all addition. It hides the trend curve, but does not replace it. As th + + In theory any program could be run in constant time by using a lookup table. + + What about going the other direction? If we have an ever faster + + + To answer this question we would have to be specific about the organization, but on the face of it the answer is "no". Take a superscalar architecture. Suppose that it were possible to run two instructions on every clocks cycle, that is merely a linear term improvement in the step count for completing the program. It doesn't change the asymptotic 'complexity' of programs. A linear time program is still a linear time program, etc. +

+ +

+ The Turing Machine is a computation theory object that is suggestive of a simple architecture, and a computer organization. Any student who has had to do homework problems centered on Turing Machines, will have tracked the flow of data through the machine, i.e. worked at the register transfer level. This makes the Turing Machine a computer organization. All descriptions of Turing Machines + + + however, a little work is needed to complete architecture analog. The fundamentals are present, the read/write head, the tape, the procedure for using the tape, but other components are missing. The manipulation of symbols remains ungrounded. The tape is not well defined. The use of emptiness is non-architecture like. The tape transport is not articulated, though it is implied. The read buffer that holds a value read, so the programmed controller can do write without clobbering the read data needed for the next transition is not identified as a component. As we proceed, we will likely discover other missing components.

@@ -523,260 +693,194 @@

-

The programmed controller

- -

- There are two distinct centers of logical control for the Turing Machine. The one we are most familiar with from the many descriptions of the Turing Machine in papers is called the 'state controller'; however, this term becomes confusing when we realize there are additional controllers involved. Hence, we call this component the programmed controller. It is customized for each different problem the Turing Machine will work on, while the other controllers give the Turing Machine its fixed characteristics. -

- -

Components

- -

The programmed controller contains the following components:

- - -

- Each state corresponds to a symbol. Here, instances of the state symbols appear in a different context than that of the data alphabet symbols or the empty-symbol, and thus they do not need to be distinct from them. In real machines, state symbol instances are unsigned integers. -

- -

- The alphabet of states is specified in the architecture, and in the design stage becomes a table in a document where each row relates a bit vector with a name. It remains a documented abstraction to the designers, but can become embodied in programs where meaningful print statements are needed. Perhaps in a CAD tool such as a hardware debugger. -

- -

- The current state register holds an instance of the current state symbol. During reset its value is forced to be an instance of the initial state symbol. During normal operation it is successively updated with the prior next state choice. -

- -

- The current state register output is wired to the comparator, along with the halt symbol. A positive match across the comparator asserts a gating signal that halts the machine clock. This halts the internal procedures (discussed in a later chapter), which guarantees that no further step pulses will arrive at the programmed controller. -

- -

- The current state register is used to lookup a row in the instruction table. Each defined row contains an instruction that is sent to the tape transport unit. A retrieved instruction provides the specific control code and, in the case of a write instruction, the argument symbol to be written. If the current state yields no match in the instruction table, the logic defaults to issuing a 'no-op', no operation instruction. While a 'no-op' need not be physically acted upon by the tape transport, the fixed wiring typically propagates the signal regardless. -

- -

- The current state register, concatenated with the output of the read buffer, is used to lookup a row in the next state table. It yields the subsequent state, or an indication that the given input is not found. -

- -

- The current state register is also used to lookup a row in the default next state table while ignoring the read buffer output. An entry for a given state might not exist here either. -

- -

- The 'lookup' operation can be implemented in a number of ways, at the election of the design engineers. In the simplest form a lookup indexes into an array, though this can be inefficient. For such small machines a hash table is an unlikely alternative. More likely is content addressable memory, a programmable logic array, or custom combinational logic. -

- -

- The programmer must provide the state alphabet, the instruction table, and the next state table. To do this, the programmer benefits from understanding how the programmed controller works. When preparing to provide the tables, the programmer can draw a state machine graph. There are two styles of state machine graphs: the Mealy style and the Moore style. The Mealy style has outputs specified on the edges, while the Moore machine has outputs associated with states. They are equivalently expressive, though the Moore style more easily leads to the table values for the programmed controller described in this section. -

- -

- Each defined row of the instruction table specifies a state-specific instruction to be given to the tape transport unit. The instruction will be one from the set: { no-op, step-left, step-right, and write(value) }, where the value parameter for a write instruction is coded directly as part of the instruction. -

- -

Control logic

- -

- The following procedure is embodied as further control logic in the Turing Machine. This procedure is fired upon receiving a step pulse. At the time the procedure is entered, the head is stable upon a cell. We list phases so as to avoid any apparent race conditions. This does not dictate to the designers that the clock must have phases, though that isn't excluded either. -

- -

Deterministic (Uniplex) programmed control procedure

- -

Upon each step pulse:

- -

Phase 1:

-
    -
  1. read the symbol instance indicated by the head into the read data buffer
    2. -
- -

Phase 2:

-
    -
  1. lookup the current state in the instruction table
    2. -
  2. lookup the current state concatenated with the read data buffer in the next state table
    3. -
  3. lookup the current state in the default next state table
    4. -
- -

Phase 3:

-
    -
  1. if the current state is found in the next state table, use the retrieved value as the next state. Otherwise, if the current state is found in the default next state table, use the default state as the next state. Otherwise, use the error state as the next state.
    2. -
  2. if an instruction was retrieved from the instruction table, the tape transport executes it. Otherwise, the tape transport executes the default 'no-op' instruction.
    3. -
- -

Phase 4:

-
    -
  1. write the next state to the current state register
    2. -
  2. controller remains quiescent waiting for the next step pulse
    3. -
+

The programmed controller

+

+ There are two distinct centers of logical control for the Turing Machine. The one we are most familiar with from the many descriptions of the Turing Machine in papers is called the 'state controller'; however, this term becomes confusing when we realize there are additional controllers involved. Hence, we call this component the programmed controller. It is customized for each different problem the Turing Machine will work on, while the other controllers give the Turing Machine its fixed characteristics. +

-

Theoretical significance

+

Components

-

- In common books and papers about the Turing Machine, a step is defined as one step of the programmed controller, i.e. one pass through the four phase procedure given above. Decider proofs ask if the comparator will match the halt state within a finite number of steps. Time complexity proofs take a formulation of step count to reach the halt state, parameterized against the size of the input, and report the order of the highest term as it is asymptotically dominant. Hence we speak of constant, linear, polynomial, and exponential time complexity algorithms. A similar method of analysis, that of memory usage with step count, parameterized against input size, is used for space complexity. -

+

The programmed controller contains the following components:

+ -

- For a real machine, the step pulse will be derived from the machine clock. The clock will have a constant period, so there is a constant duration of time that will be the same for each pass through the execution procedure. Thus, if we replace the step count with a count of clock ticks, we will get the same decider and complexity results as we would have from step counts. This fits the definition we have been using for inconsequential. -

+

+ Each state corresponds to a symbol. Here, instances of the state symbols appear in a different context than that of the data alphabet symbols or the empty-symbol, and thus they do not need to be distinct from them. In real machines, state symbol instances are unsigned integers. +

+

+ The alphabet of states is specified in the architecture, and in the design stage becomes a table in a document where each row relates a bit vector with a name. It remains a documented abstraction to the designers, but can become embodied in programs where meaningful print statements are needed. Perhaps in a CAD tool such as a hardware debugger. +

-

An alternative: stored program and sequencer

+

+ The current state register holds an instance of the current state symbol. During reset its value is forced to be an instance of the initial state symbol. During normal operation it is successively updated with the prior next state choice. +

-

- The Universal Turing Machine, proposed by Alan Turing, introduced a profound architectural inversion: relocating the defining state tables from hardwired logic, or manually configured patch panels, directly onto the tape itself. This enables replacing the custom programmed controller with a fixed controller that derives its behavior dynamically from the tape data. Consequently, a single, immutable hardware architecture can simulate the execution of any conceivable Turing Machine. -

+

+ The current state register output is wired to the comparator, along with the halt symbol. A positive match across the comparator asserts a gating signal that halts the machine clock. This halts the internal procedures (discussed in a later chapter), which guarantees that no further step pulses will arrive at the programmed controller. +

-

- In addition, encoding a machine's control logic as parseable data on tape establishes an ontology of analysis, a framework where a machine can analyze another machine to establish some properties the other machine might have. We say 'some' because at least one limitation has been proven. Alan Turing proved that such an analyst cannot in general determine if said other machine has the property that it would halt for any input when run. -

+

+ The current state register is used to lookup a row in the instruction table. Each defined row contains an instruction that is sent to the tape transport unit. A retrieved instruction provides the specific control code and, in the case of a write instruction, the argument symbol to be written. If the current state yields no match in the instruction table, the logic defaults to issuing a 'no-op', no operation instruction. While a 'no-op' need not be physically acted upon by the tape transport, the fixed wiring typically propagates the signal regardless. +

-

- We can optimize this representation. Instead of storing the state tables verbatim, we can list a sequence of instructions directly on the tape. To achieve this, the architecture expands to support two distinct categories of instructions: the physical tape transport instructions we defined previously, and a newly introduced category of control instructions. The programmed controller is then replaced with a fixed hardware controller called a sequencer. -

+

+ The current state register, concatenated with the output of the read buffer, is used to lookup a row in the next state table. It yields the subsequent state, or an indication that the given input is not found. +

-

- Because the original state tables allowed for non-linear execution paths, the instruction sequence on the tape cannot always execute in a straight line. Therefore, the architect must include at least two control instructions: a halt instruction and a test-and-branch instruction. The sequencer starts at the first instruction in the program, perhaps at the leftmost cell on the tape, and evaluates it. If it is a control instruction, the sequencer acts upon it directly to alter the flow of execution or stop the machine. Otherwise, if it is a physical instruction for the head unit, the sequencer passes it down to the tape transport. -

+

+ The current state register is also used to lookup a row in the default next state table while ignoring the read buffer output. An entry for a given state might not exist here either. +

-

- Because we have not yet derived Natural Numbers or memory addresses in this architecture, a test-and-branch instruction cannot jump to a numerical address. Instead, it must operate topologically. A topological branch instruction simply commands the sequencer to scan the tape for a specific target symbol, and resume executing instructions from that physical location. -

+

+ The 'lookup' operation can be implemented in a number of ways, at the election of the design engineers. In the simplest form a lookup indexes into an array, though this can be inefficient. For such small machines a hash table is an unlikely alternative. More likely is content addressable memory, a programmable logic array, or custom combinational logic. +

-

- As noted in the prior section, an instruction consists of an instruction code and potentially an argument. There are many choices that can be made in instruction set design. Among those choices, almost all will be inconsequential from a computation-theoretic point of view, but almost all will introduce strict efficiency trade-offs in physical hardware. -

---- -

Data must be an instance of an alphabet symbol or an instance of the empty-symbol.

+

+ The programmer must provide the state alphabet, the instruction table, and the next state table. To do this, the programmer benefits from understanding how the programmed controller works. When preparing to provide the tables, the programmer can draw a state machine graph. There are two styles of state machine graphs: the Mealy style and the Moore style. The Mealy style has outputs specified on the edges, while the Moore machine has outputs associated with states. They are equivalently expressive, though the Moore style more easily leads to the table values for the programmed controller described in this section. +

-

In addition, we should not forget the implied read command that returns a value from the tape at the start of each step, and buffers it for use by the fixed procedure.

+

+ Each defined row of the instruction table specifies a state-specific instruction to be given to the tape transport unit. The instruction will be one from the set: { no-op, step-left, step-right, and write(value) }, where the value parameter for a write instruction is coded directly as part of the instruction. +

-

The arcs are triples of symbols, <from-state, to-state, value>.

+

Control logic

-

The from-states, to-states, and values are set when the controller is defined.

+

+ The following procedure is embodied as further control logic in the Turing Machine. This procedure is fired upon receiving a step pulse. At the time the procedure is entered, the head is stable upon a cell. We list phases so as to avoid any apparent race conditions. This does not dictate to the designers that the clock must have phases, though that isn't excluded either. +

+ +

Deterministic (Uniplex) programmed control procedure

-

The value is an instance of either an alphabet symbol or the empty-symbol.

+

Upon each step pulse:

- - We require that for each from-state that there exists exactly one arc for each member of the alphabet, one for the empty-symbol, and for states with a step-left command, that there be one arc for the left from leftmost error. - +

Phase 1:

+
    +
  1. read the symbol instance indicated by the head into the read data buffer
    2. +
-

Arcs can be dropped from diagrams if we can prove that they cannot be used.

+

Phase 2:

+
    +
  1. lookup the current state in the instruction table
    2. +
  2. lookup the current state concatenated with the read data buffer in the next state table
    3. +
  3. lookup the current state in the default next state table
    4. +
-

As a notational convenience we might also reduce the work of listing so many arcs by adopting the convention of explicitly providing only unique arcs, and then saying the rest of the arcs are identical to a default arc or an error arc.

+

Phase 3:

+
    +
  1. if the current state is found in the next state table, use the retrieved value as the next state. Otherwise, if the current state is found in the default next state table, use the default state as the next state. Otherwise, use the error state as the next state.
    2. +
  2. if an instruction was retrieved from the instruction table, the tape transport executes it. Otherwise, the tape transport executes the default 'no-op' instruction.
    3. +
-

Here we present the fixed procedure in the form of a main procedure and two subprocedures, 'Initialize', and 'Take a Step'. To perform a computation follow the steps in Main, and its subprocedures, until being told to halt:

+

Phase 4:

+
    +
  1. write the next state to the current state register
    2. +
  2. controller remains quiescent waiting for the next step pulse
    3. +
-

Deterministic (Uniplex) Procedure

-

Setup (manual):

-
    -
  1. mount the tape
    2. -
  2. push the reset button
    3. -
+

Consequentiality of architectural level control

-

Initialize (reset procedure):

-
    -
  1. step the head left until an 'left of leftmost' error from the tape transport unit, the head will then be on the leftmost cell
    2. -
  2. set the current-state of the provided state machine controller to the initial-state
    3. -
  3. set the state controller stepping counter to 0
    4. -
  4. upon release of reset, perform 'Step'
    5. -
+

+ In common books and papers about the Turing Machine, a step is defined as one step of the programmed controller, i.e. one pass through the four phase procedure given above. Decider proofs ask if the comparator will match the halt state within a finite number of steps. Time complexity proofs take a formulation of step count to reach the halt state, parameterized against the size of the input, and report the order of the highest term as it is asymptotically dominant. Hence we speak of constant, linear, polynomial, and exponential time complexity algorithms. A similar method of analysis, that of memory usage with step count, parameterized against input size, is used for space complexity. +

-

Step:

-
    -
  1. read the symbol instance indicated by the head into the read data buffer
    2. -
  2. execute the command corresponding to the current-state
    3. -
  3. select the arc that has a from-state matching the current-state, and a value matching the instance in the read buffer. Take that arc's next-state and make it the machine's next-state.
    4. -
  4. make the next-state the current-state
    5. -
  5. increment the step counter
    6. -
+

+ For a real machine, the step pulse will be derived from the machine clock. The clock will have a constant period, so there is a constant duration of time that will be the same for each pass through the execution procedure. Thus, if we replace the step count with a count of clock ticks, we will get the same decider and complexity results as we would have from step counts. This fits the definition we have been using for inconsequential. +

-

Main:

-
    -
  1. Initialize
    2. -
  2. if the current-state is the halt-state, then halt
    3. -
  3. wait for the clock to synchronize, then Take a Step
    4. -
  4. go to 2
    5. -
-

We initialize the machine by instantiating the input on the tape, putting the head on the leftmost cell of the tape, setting the current state to the initial-state, and zeroing the step counter.

+

An alternative: stored program and sequencer

-

We take a step by first reading the symbol under the head and storing that value in our read data buffer, executing the command associated with the state, and then following the arc selected by the element we buffered.

+

+ The Universal Turing Machine, proposed by Alan Turing, introduced a profound architectural inversion: relocating the defining state tables from hardwired logic, or manually configured patch panels, directly onto the tape itself. This enables replacing the custom programmed controller with a fixed controller that derives its behavior dynamically from the tape data. Consequently, a single, immutable hardware architecture can simulate the execution of any conceivable Turing Machine. +

-

We must read the element into the buffer before executing the command because the command might perform a write to the cell. If a machine were to write a new symbol to the tape before the transition arc was evaluated, the original symbol would be destroyed, and the controller would lose the information required to determine its next state. The read data buffer physically isolates the state controller from this write-overwrite hazard.

+

+ In addition, encoding a machine's control logic as parseable data on tape establishes an ontology of analysis, a framework where a machine can analyze another machine to establish some properties the other machine might have. We say 'some' because at least one limitation has been proven. Alan Turing proved that such an analyst cannot in general determine if said other machine has the property that it would halt for any input when run. +

-

Consequently, as part of the Turing Machine definition, we required the buffer for holding the read value.

+

+ We can optimize this representation. Instead of storing the state tables verbatim, we can list a sequence of instructions directly on the tape. To achieve this, the architecture expands to support two distinct categories of instructions: the physical tape transport instructions we defined previously, and a newly introduced category of control instructions. The programmed controller is then replaced with a fixed hardware controller called a sequencer. +

-

Walking through this procedure is variously known as running the machine, performing a computation, evaluating the input, evaluating the function, or simply as computing.

+

+ Because the original state tables allowed for non-linear execution paths, the instruction sequence on the tape cannot always execute in a straight line. Therefore, the architect must include at least two control instructions: a halt instruction and a test-and-branch instruction. The sequencer starts at the first instruction in the program, perhaps at the leftmost cell on the tape, and evaluates it. If it is a control instruction, the sequencer acts upon it directly to alter the flow of execution or stop the machine. Otherwise, if it is a physical instruction for the head unit, the sequencer passes it down to the tape transport. +

-

Note that while walking through this procedure we are always in exactly one state. This is because we required that there be one arc for each letter in the alphabet, empty-symbol, and possibly the left from leftmost error. We say that this property means that the machine is deterministic.

+

+ Because we have not yet derived Natural Numbers or memory addresses in this architecture, a test-and-branch instruction cannot jump to a numerical address. Instead, it must operate topologically. A topological branch instruction simply commands the sequencer to scan the tape for a specific target symbol, and resume executing instructions from that physical location. +

-

To make a non-deterministic machine we allow multiple arcs to have the same read value as a second member, and we modify the second step of the procedure to follow all arcs that have matches with the symbol returned by the buffer.

+

+ As noted in the prior section, an instruction consists of an instruction code and potentially an argument. There are many choices that can be made in instruction set design. Among those choices, almost all will be inconsequential from a computation-theoretic point of view, but almost all will introduce strict efficiency trade-offs in physical hardware. +

-

When we do this we might find that zero, one, or many of the arcs are followed in one step, and thus that we have a probability to have zero or more next states.

+

Machine control

-

Conceptually each of these states corresponds to a separate machine head with its own read buffer.

+

+ In the prior two sections we discussed the configurable part of the Turing Machine control. Here we complete the picture by describing the fixed portion. +

-

At the end of the step we rename our next state set to be the current state set.

+

Setup

+
    +
  1. select and mount a tape
    2. +
  2. push the reset button
    3. +
-

Should the halt-state ever be placed in the current state set, then we halt the machine.

+

Reset

+
    +
  1. step the head left until an 'left of leftmost' error from the tape transport unit, the head will then be on the leftmost cell
    2. +
  2. hit reset on the programmed controller, or the sequencer, depending on which is being used
    3. +
  3. wait until the release of the reset button
    4. +
-

Should the current state set become empty without ever having reached a halt-state, we say the machine has failed.

+

Main:

+
    +
  1. Based on the value of the reset line coming from the rest button: +
      +
    1. true: Reset +
    2. Based on the value of the halt line coming from the comparator: +
        +
      1. true: freeze here until reset is asserted, and go to step 1. +
      2. false: on each clock tick send a step pulse to the programmed controller or sequencer, depending on which is used. +
      +
    +
-

Non-Deterministic (Multiplex) Procedure

+

+ We can read this procedure with the caveat, "if we could realize such a machine, this is what we would do. Later, these directions can be modified and applied to the machine variation that has an expanding tape. +

-

Initialize:

-
    -
  1. mount the tape
    2. -
  2. for each initial-state, place an <initial-state, head location on leftmost> pair into the current state set
    3. -
  3. set the step counter to 0
    4. -
+

+ To start the machine we must first select a tape. Common choices are an empty tape, a tape with data on it the machine is to decide matches a given language pattern, a tape with a Turing Machine on it to be analyzed. After the tape is selected it is mounted on the Turing Machine, then the reset button is hit. +

-

Take a Step:

-
    -
  1. clear the next state set
    2. -
  2. For each <state, head-location> member of the current state set: -
      -
    1. read the symbol instance from the corresponding head-location into the read data buffer
      2. -
    2. execute the command corresponding to the state (updating the head-location or tape)
      3. -
    3. for each arc matching the state and the buffered symbol, add a <next-state, updated head-location> pair into the next state set
      4. -
    -
    3. -
  3. rename the next state set to be the current state set
    4. -
  4. increment the step counter
    5. -
+

+ After the reset button is released, the machine begins stepping. If the program is a computation, the machine will eventually halt. If the machine eventually halts, then we know the associated program was computation. Otherwise we do not know. Any amount of time we wait where the machine has not halted, we will not know that it will ever halt. Hence, we can not in general use 'running a Turing Machine' as a means to determine if a given program is computational. (We could instead try to answer the question 'is it computational' through analysis, but there too, Turing has shown that in general that will not work either.) +

-

Main:

-
    -
  1. Initialize
    2. -
  2. if the halt-state is a member of the current state set, then halt. If the current state set is empty, then halt with an error.
    3. -
  3. wait for the clock to synchronize, then Take a Step
    4. -
  4. go to 2
    5. -
-

As reviewed by Papadimitriou , such non-deterministic machines can be converted to deterministic ones. This is done by calling each unique 'state set' a state.

-

A person might recall from the definition of a symbol, that any mathematical object for which instances are comparable can be used.

That includes sets. When two current state sets have the same members, we say they are instances of the same state. When they have different members we say they are different states.

-

Orders of analysis

-

Turing Machines that halt in finite number of steps for any finite input are computational. I.e. for any given non-computational Turing Machine there will exist at least one input for which computation will never complete.

+

Turing Machines that halt in finite number of steps for any finite input withing a stipulated domain are said to be computational over that domain. It is also the case that for any given non-computational Turing Machine over a given domain there will exist at least one input for which the machine will never halt.

By analyzing a machine we might learn that some machine, say M, is conditionally computational on a given set of inputs, say I.

@@ -1517,6 +1621,8 @@
  • [f g h] – indirect function call. f is a variable replaced by its value, and that value is then looked up and called as a function. g and h are variables replaced by their values and passed as arguments. The result of the function replaces the entire form.
    • + + -- 2.20.1