From 4d4683a44c70e4d5a6d8bfd292b52e2333ff8f86 Mon Sep 17 00:00:00 2001 From: Thomas Walker Lynch Date: Tue, 28 Jul 2026 15:04:51 +0000 Subject: [PATCH] . --- document/book/TM-2026.html | 453 +++++++++++++++++---------------- document/book/TTCA_machine.svg | 2 +- 2 files changed, 237 insertions(+), 218 deletions(-) diff --git a/document/book/TM-2026.html b/document/book/TM-2026.html index f244e5d..74a4d9b 100644 --- a/document/book/TM-2026.html +++ b/document/book/TM-2026.html @@ -23,13 +23,16 @@ Preface -

Dear Zen master, here I submit my thesis for your consideration.

+

All communication is founded upon common knowledge, so here are some notes on the conventions used in this book.

-

All communication is founded upon common knowledge, so here are some notes on the style of English prose used in this book.

+

Generally in this book, containers such as sequences and sets are capital letters, even when in Greek. Mathematical objects that are not containers are represented with lower case letters. Character pairs or full symbol names can also be used to represent mathematical objects. The context will make it clear if a non-letter unicode character is used to represent a container or a non-container. +

+ +

The unicode middle dot, ·, is used as an ad hoc namespace operator in identifiers. Hence, N{·}x, would be the variable x from the N namespace. This is a typography symbol. It can be seen for example when words are broken into symbols, e.g. 'op·er·a·tor', and sometimes in names, such a 'Leonardo da·Vinci', and 'Vincent van·Gogh'. It is accepted in identifiers by modern C compilers, and it is part of the RT·gcc compiler mods for gcc.

-

Anyone familiar with my writing knows that I have experimented with gender forms in technical language for reasons of inclusion. For example, I used the plural-as-singular style in early writings and was applauded by some, though categorized as illiterate by others. Since then, I have evolved a writing style that emphasizes using roles as subjects: the mathematician, the author, the programmer. Such subjects are singular, so for grammatical agreement, I use the inclusive he. It is structurally much cleaner to use he as inclusive of all readers than it is to force "they" to take on a singular form. I strictly reserve "a person" for abstract generalizations where the subject is truly an unknown third party, including an AI.

+

I have experimented with modern gender forms in technical language in past writings. For example, I used the plural-as-singular style in one piece, and was applauded by some, though categorized as illiterate by others. Since then, I have evolved a writing style that emphasizes using roles as subjects: the mathematician, the author, the programmer. Such subjects are singular, so for grammatical agreement, I use the inclusive he. It is structurally much cleaner to use he as inclusive of all people than it is to gray out an entire category of plural agreement pronouns by forcing words such as "they" to take on a singular form. I use "a person" when the subject is an unknown third party, potentially even being an AI. I prefer this over the 'one' of 'One does this, or one does that.' so that 'one' can be reserved to unambiguously refer to the natural number.

-

In the prior edition of this book, the preface included a discussion on the meaning of the word "may" according to RFC 2119, the guidelines for specification writing. There is an important distinction between the 'may' of options or permission, and the 'may' of probability. However, distinguishing between the two was too much of an ask of readers, most of whom skip the preface anyway. So in this edition, I avoid the temptation to use 'may' and replace it with a direct statement of what I mean. "It is of high probability that..." or "There are options for...". Directly saying what is meant—who would have thought of it? The RFC 2119 authors have clearly struggled with this as well, as they now require the words they discuss to be strictly capitalized to prove they have a proscribed meaning.

+

In the prior edition of this book, the preface included a discussion on the meaning of the word "may" according to RFC 2119, the guidelines for specification writing. There is an important distinction between the 'may' of options or permission, and the more colloquial 'may' of probability. However, distinguishing between the two was too much of an ask of readers, most of whom skip the preface anyway. So in this edition, I avoid the temptation to use 'may' and replace it with a direct statement of what I mean. "It is of high probability that..." or "There are options for...". Directly saying what is meant, who would have thought of it? The RFC 2119 authors have apparently struggled with this as well, as they now require the MAY and other words that appear in RFC 2119 to be capitalized so as to dodge the grammar debate.

@@ -45,7 +48,7 @@

- In 1901 Bertrand Russell found a well formed set formulation using Frege's set theory that did not correspond to a set. As Frege's work was based on this set theory, this called into question his entire work. Russell pointed out that it was possible to define a set of all sets that do not contain themselves. However this was a paradox, because if said set contained itself, it shouldn't, and if it didn't it should. Thus the formulation failed to define a set because the logical condition cannot be satisfied Bertrand Russell, The Principles of Mathematics (Cambridge: Cambridge University Press, 1903), Chapter X, 'The Contradiction'.. Russell communicated this to Frege in a letter dated 1902 06 16, shortly before his second volume was going to print Bertrand Russell to Gottlob Frege, June 16, 1902, reprinted in Jean van Heijenoort, From Frege to Gödel: A Source Book in Mathematical Logic (Cambridge: Harvard University Press, 1967), 124 125. Gottlob Frege, Grundgesetze der Arithmetik, Vol. 2 (Jena: Hermann Pohle, 1903), Appendix (Nachwort), 253. Frege writes: 'Hardly anything more unfortunate can befall a scientific writer than to have one of the foundations of his edifice shaken after the work is finished.'. Frege hurriedly authored an appendix (the Nachwort) admitting his system was compromised Frege was a quiet, rigid man who had spent decades building his logical fortress in almost total academic obscurity. Frege was personally devastated by Russell's letter. Shortly after, he suffered the loss of his wife, fell into severe depression, and his academic output almost entirely ceased. In 1924, a year before his death, he wrote unpublished diaries explicitly surrendering his life's work, declaring that logicism was a mistake and that mathematics must actually be derived from geometry. Note I. Grattan Guinness, The Search for Mathematical Roots, 1870 1940 (Princeton: Princeton University Press, 2000). For an analysis of Frege's intellectual decline, personal tragedies, and his unpublished 1924 1925 diaries where he formally surrenders the logicist program, see Chapter 7.. + In 1901 Bertrand Russell found a well-formed set formulation using Frege's set theory that did not correspond to a set. As Frege's work was based on this set theory, this called into question his entire work. Russell pointed out that it was possible to define a set of all sets that do not contain themselves. However this was a paradox, because if said set contained itself, it shouldn't, and if it didn't it should. Thus the formulation failed to define a set because the logical condition cannot be satisfied Bertrand Russell, The Principles of Mathematics (Cambridge: Cambridge University Press, 1903), Chapter X, 'The Contradiction'.. Russell communicated this to Frege in a letter dated 1902 06 16, shortly before his second volume was going to print Bertrand Russell to Gottlob Frege, June 16, 1902, reprinted in Jean van Heijenoort, From Frege to Gödel: A Source Book in Mathematical Logic (Cambridge: Harvard University Press, 1967), 124 125. Gottlob Frege, Grundgesetze der Arithmetik, Vol. 2 (Jena: Hermann Pohle, 1903), Appendix (Nachwort), 253. Frege writes: 'Hardly anything more unfortunate can befall a scientific writer than to have one of the foundations of his edifice shaken after the work is finished.'. Frege hurriedly authored an appendix (the Nachwort) admitting his system was compromised Frege was a quiet, rigid man who had spent decades building his logical fortress in almost total academic obscurity. Frege was personally devastated by Russell's letter. Shortly after, he suffered the loss of his wife, fell into severe depression, and his academic output almost entirely ceased. In 1924, a year before his death, he wrote unpublished diaries explicitly surrendering his life's work, declaring that logicism was a mistake and that mathematics must actually be derived from geometry. Note I. Grattan Guinness, The Search for Mathematical Roots, 1870 1940 (Princeton: Princeton University Press, 2000). For an analysis of Frege's intellectual decline, personal tragedies, and his unpublished 1924 1925 diaries where he formally surrenders the logicist program, see Chapter 7..

@@ -74,11 +77,11 @@

- In 1931 Kurt Gödel published his incompleteness theorems Kurt Gödel, "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I," Monatshefte für Mathematik und Physik 38 (1931): 173 198.. By mapping formal logic into arithmetic, he demonstrated that any consistent formal system sufficiently powerful to perform basic arithmetic, let us call it system S, will inevitably contain well formed formulas that are mathematically true yet cannot be proven within the system itself For the definitive English translation, see Jean van Heijenoort, From Frege to Gödel: A Source Book in Mathematical Logic, 1879 1931 (Cambridge: Harvard University Press, 1967), 596 616.. Gödel achieved this by engineering a specific formula that evaluates to the claim: "G: There exists no sequence of valid logical steps within system S that proves G." If system S is consistent, it cannot output a proof for G; thus, the claim G makes is factually accurate, rendering it true but mechanically unprovable. Furthermore, Gödel demonstrated that system S cannot output a proof of its own consistency. This result fractured David Hilbert's 1900 vision of utilizing a weaker, strictly "finitistic" logical subsystem to definitively prove that the axioms of arithmetic are entirely free of contradictions David Hilbert, "Mathematical Problems," Bulletin of the American Mathematical Society 8 (1902): 437 479.. If the full, powerful system S physically lacks the mechanical capacity to verify its own consistency, Hilbert's weaker finitistic subsystem is definitively incapable of accomplishing the task. Gödel's work established a hard mechanical boundary, asserting that truth and provability are distinct concepts in classical mathematics. + In 1931 Kurt Gödel published his incompleteness theorems Kurt Gödel, "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I," Monatshefte für Mathematik und Physik 38 (1931): 173 198.. By mapping formal logic into arithmetic, he demonstrated that any consistent formal system sufficiently powerful to perform basic arithmetic, let us call it system S, will inevitably contain well-formed formulas that are mathematically true yet cannot be proven within the system itself For the definitive English translation, see Jean van Heijenoort, From Frege to Gödel: A Source Book in Mathematical Logic, 1879 1931 (Cambridge: Harvard University Press, 1967), 596 616.. Gödel achieved this by engineering a specific formula that evaluates to the claim: "G: There exists no sequence of valid logical steps within system S that proves G." If system S is consistent, it cannot output a proof for G; thus, the claim G makes is factually accurate, rendering it true but mechanically unprovable. Furthermore, Gödel demonstrated that system S cannot output a proof of its own consistency. This result fractured David Hilbert's 1900 vision of utilizing a weaker, strictly "finitistic" logical subsystem to definitively prove that the axioms of arithmetic are entirely free of contradictions David Hilbert, "Mathematical Problems," Bulletin of the American Mathematical Society 8 (1902): 437 479.. If the full, powerful system S physically lacks the mechanical capacity to verify its own consistency, Hilbert's weaker finitistic subsystem is definitively incapable of accomplishing the task. Gödel's work established a hard mechanical boundary, asserting that truth and provability are distinct concepts in classical mathematics.

- In April 1936, Alonzo Church leveraged Gödel's foundational papers to directly answer the Entscheidungsproblem Alonzo Church, "An Unsolvable Problem of Elementary Number Theory," American Journal of Mathematics 58, no. 2 (April 1936): 345 363.. Working independently, Alan Turing had arrived at his own mechanical solution, and upon seeing Church's April publication, Turing rushed to submit his manuscript on 28 May 1936, appending a proof that his mechanical architecture was mathematically equivalent to Church's lambda calculus 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. Received May 28, 1936, published November 30, 1936.. As Hilbert and Ackermann concede in the 1938 second edition of their textbook, Church's results demonstrated that "the quest for a general solution of the decision problem must be regarded as hopeless" David Hilbert and Wilhelm Ackermann, Principles of Mathematical Logic, 2nd ed. (New York: Chelsea Publishing Company, 1950), 124.. By giving the "somewhat vague intuitive concept of recursion a certain precise formalization," Church proved the "non existence of such a recursive procedure" that could mechanically yield a value of truth or falsehood for every individual formula Ibid., 124.. + In April 1936, Alonzo Church leveraged Gödel's foundational papers to directly answer the Entscheidungsproblem Alonzo Church, "An Unsolvable Problem of Elementary Number Theory," American Journal of Mathematics 58, no. 2 (April 1936): 345 363.. Working independently, Alan Turing had arrived at his own mechanical solution, and upon seeing Church's April publication, Turing rushed to submit his manuscript on 28 May 1936, appending a proof that his mechanical architecture was mathematically equivalent to Church's lambda calculus 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. Received May 28, 1936, published November 30, 1936.. As Hilbert and Ackermann concede in the 1938 second edition of their textbook, Church's results demonstrated that "the quest for a general solution of the decision problem must be regarded as hopeless" David Hilbert and Wilhelm Ackermann, Principles of Mathematical Logic, 2nd ed. (New York: Chelsea Publishing Company, 1950), 124.. By giving the "somewhat vague intuitive concept of recursion a certain precise formalization," Church proved the "non-existence of such a recursive procedure" that could mechanically yield a value of truth or falsehood for every individual formula Ibid., 124..

@@ -103,7 +106,7 @@

- While Gödel, Church, and Turing established the primary boundaries of computation, they did not work in a vacuum. During this period, the broader academic community worked to synthesize the definitive mechanics of effective calculability. Jacques Herbrand and Gödel formalized general recursive functions between 1931 and 1934 Kurt Gödel, "On Undecidable Propositions of Formal Mathematical Systems," mimeographed lecture notes, Institute for Advanced Study, Princeton, 1934.. Emil Post independently defined "Finite Combinatory Processes" in 1936, outlining a theoretical architecture functionally identical to Turing's model Emil L. Post, "Finite Combinatory Processes Formulation 1," The Journal of Symbolic Logic 1, no. 3 (September 1936): 103 105.. Stephen Kleene subsequently unified these disparate threads, proving the strict mathematical equivalence of Church's lambda calculus, Herbrand Gödel recursive functions, and Turing's mechanical architectures Stephen C. Kleene, "General Recursive Functions of Natural Numbers," Mathematische Annalen 112 (1936): 727 742.. + While Gödel, Church, and Turing established the primary boundaries of computation, they did not work in a vacuum. During this period, the broader academic community worked to synthesize the definitive mechanics of effective calculability. Jacques Herbrand and Gödel formalized general recursive functions between 1931 and 1934 Kurt Gödel, "On Undecidable Propositions of Formal Mathematical Systems," mimeographed lecture notes, Institute for Advanced Study, Princeton, 1934.. Emil Post independently defined "Finite Combinatory Processes" in 1936, outlining a theoretical architecture functionally identical to Turing's model Emil L. Post, "Finite Combinatory Processes Formulation 1," The Journal of Symbolic Logic 1, no. 3 (September 1936): 103 105.. Stephen Kleene subsequently unified these disparate threads, proving the strict mathematical equivalence of Church's lambda calculus, Herbrand-Gödel recursive functions, and Turing's mechanical architectures Stephen C. Kleene, "General Recursive Functions of Natural Numbers," Mathematische Annalen 112 (1936): 727 742..

@@ -149,12 +152,12 @@ - The computer design abstraction stack + The computer design abstraction stack

The six levels

- There are a number of discernible levels to the computer design abstraction stack: + These are the discernible levels of the computer design abstraction stack:

    @@ -176,7 +179,7 @@

    The classic text by Hamacher, Vranesic, and Zaky carefully defines the organizational level as sitting between architecture and implementation V. Carl Hamacher, Zvonko G. Vranesic, and Safwat G. Zaky, Computer Organization, 5th ed. (New York: McGraw Hill, 2002).. - 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, and ALU layout. Crucially, it is at this level that decisions regarding instruction level parallelism are made, such as whether the processor will employ a scalar, superscalar, or VLIW design, the depth of its execution pipelines, the use of out of order execution, branch prediction strategies, and the specific hierarchy of hardware caches. It dictates the logical arrangement of hardware and the procedures that force the data to flow to satisfy the architectural constraints. Organization is sometimes called micro architecture, and it is made by a design 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, and ALU layout. Crucially, it is at this level that decisions regarding instruction level parallelism are made, such as whether the processor will employ a scalar, superscalar, or VLIW design, the depth of its execution pipelines, the use of out-of-order execution, branch prediction strategies, and the specific hierarchy of hardware caches. It dictates the logical arrangement of hardware and the procedures that force the data to flow to satisfy the architectural constraints. Organization is sometimes called micro architecture, and it is made by a design architect.

    @@ -206,7 +209,7 @@

    - The common understanding of the word 'architecture' is what Hamacher and Zaky call 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. + The common understanding of the word 'architecture' is what Hamacher and Zaky call 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, is clearly a question of computer organization.

    @@ -231,7 +234,7 @@

    - When a transform applied to machine m_i produces machine m_{i.1}, and this latter machine gets the same results for the same computational inputs, and furthermore, if any computation theory analysis applied to m_{i.1} yields the same answer as it would when applied to m_i — we say that the transform is computation theoretic inconsequential. Otherwise, the transformation is said to be computation theoretic consequential. The remainder of this section defines these terms more precisely. + When a transform applied to machine m_i produces machine m_{i.1}, and this latter machine gets the same results for the same computational inputs, and furthermore, if any computation theory analysis applied to m_{i.1} yields the same existence and big O results as it would when applied to m_i, we say that the transform is computation theoretic inconsequential. Otherwise, the transformation is said to be computation theoretic consequential. The remainder of this section defines these terms more precisely.

    Definition of the same results transform property

    @@ -352,7 +355,7 @@ M = (Q, Σ, Γ, δ, q_0, □, F) -

    Where the components have the following meanings:

    +

    Each component of the Machine, M, is defined as follows:

    -

    I have introduced the qualifier programmed in front of the finite state machine controller because each Turing Machine that accomplishes a different task has a different finite state machine controller. The rest of the Turing Machine remains fixed. Hence, when a mathematician defines a custom task controller, he is essentially programming the machine.

    +

    I introduced the qualifier programmed in front of the finite state machine controller because each Turing Machine that accomplishes a different task has a different finite state machine controller. A program is then a set of assignments to the variable parts of the Turing Machine definition. Notice that additional variables are needed by the Turing Machine executor beyond those that appear in the definition, such as the current state variable. In alternative terminology, the definition above defines a Turing Machine type, and a set of assignments to the variable parts of the definition constitutes an instance. Accordingly, then, when a computer arithmetician says he has two Turing Machines, he is saying that he has two distinct sets of Turing Machine variable assignments, and as these sets are distinct, each can be manipulated independently.

    -

    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. In the architecture description given below, those symbols exclusive to the larger set are called control symbols. Hopcroft and Ullman include the empty symbol as a control symbol. However, they have simultaneously listed it as a separate component.

    +

    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 read value from the tape. Each state transition function includes actions to be taken; hence, their programmable controller is a Mealy style state machine. The step action is mandatory, though it can be in either direction. The write action must be specified, but the write could 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 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.

    -

    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. When analyzing the time complexity of an algorithm, this overhead doubles the constant on the linear term, leaving the asymptotic order of complexity entirely unchanged. The outcomes of decider programs are unaffected. Therefore, utilizing a single ended tape is a computation theoretic inconsequential variation of the two way tape machine. +

    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.

    Hopcroft and Ullman explain a step of the machine by showing a representation of the tape with the state variable melded in to the left of the currently scanned symbol. Suppose δ(q, X_i) = (p, Y, L); i.e., the next move is leftward. Then, @@ -526,7 +529,7 @@ -

    This shows string reversal to be an O(n^2) complexity problem, which might appear to some to be a peculiar result, as the same problem can be solved in O(n) time with a C program. This justifies further analysis.

    +

    This shows string reversal to be an O(n^2) complexity problem, which might appear to some programmers as a peculiar result, as the same problem can be solved in O(n) time with a C program. This justifies further analysis.

    Reversing a string does not intrinsically require making decisions based on the values in the string that is being reversed; however, a Turing Machine must use the value under the head for the next state transitions. Also, the only memory a controller has is through adding control path branches, so to "carry the symbol right" requires a branch in the state controller per symbol to remember what the symbol is. Consequently, had the input alphabet been larger, this controller would have required proportionally more states, as noted on the diagram.

    @@ -546,7 +549,7 @@ -

    These equations show that the state controller size explodes with word width. It would be impractical to implement for all but the smallest of word sizes. This is one of the reasons that computation theory books use modest-sized symbol alphabets in their examples, perhaps the first few letters of the Latin alphabet, or the letter 's' for unary arithmetic. Previous sections discussed challenges transitioning the Turing Machine to a real architecture due to the tape length, and how this could be mitigated. In contrast, there is no practical mediation for implementing a Turing Machine controller even for modest-sized real problems.

    +

    These equations show that the state controller size explodes with word width. It would be impractical to implement for all but the smallest of word sizes. This is one of the reasons that computation theory books use modest-sized symbol alphabets in their examples, perhaps the first few letters of the Latin alphabet, or the letter 's' for unary arithmetic. Previous sections discussed challenges transitioning the Turing Machine to a real architecture due to the tape length, and discussed how this could be mitigated. In contrast, there is no practical mediation for implementing a Turing Machine controller even for modest-sized real problems.

    This raises a question: if the Turing machine is to instruct upon the limitations of real computation, what are the implications stemming from its state controller being impractical? As one such implication, when a Turing Machine proof shows that a number is computable, it doesn't necessarily instruct upon how it could be computed. When a reader picks up a text on applied number theory, also called computer arithmetic, he is unlikely to find a chapter on Turing Machines.

    @@ -561,7 +564,7 @@
    - T_0 = [ \lbrace \rbrace, \lbrace \rbrace, \lbrace \rbrace, \dots ] + T_0 = [ \{ \}, \{ \}, \{ \}, \dots ]
    @@ -584,7 +587,7 @@ if not is_empty(c): c.pop() # Clear the cell if it holds something if x != 'empty': - c.put(x) # Place the new symbol unless we are just erasing + c.put(x) # Place the new symbol unless we are erasing

    Now imagine machine B, where the concept of an empty cell is jettisoned, and what remains is the mere memory of emptiness, a symbol called empty. Then using the language of mathematics, the mathematician defines an initial empty tape as:

    @@ -599,7 +602,7 @@

    It is possible to build a mapping between the machine A and machine B. The read and write operations are placed into correspondence. The empty set as a member of tape sequence of machine A is placed into correspondence with the empty symbol of machine B. The other components are defined identically, and map directly. This creates an isomorphism between the two machines. Hence, they are equally expressive. However, machine B is simpler, so it is understandable that computer theoreticians have settled on this definition.

    -

    If we view the empty symbol from within the definition of machine B, it is a category error. It is a sequence element not a container. Even if it were allowed that a position within a sequence were a container and thus could have the property of being empty, the symbol represents that there is no symbol in the very location it is found. Hence, to ascribe an appropriate meaning to the empty symbol, the entire system must be kept including the mapping to machine A, then the empty symbol found on machine B means that if machine A were used instead, the same location in the tape sequence would be an empty set. However, this feels unsatisfactory, because in all other respects, machine B is a perfectly well defined Turing Machine all by itself.

    +

    If we view the empty symbol from within the definition of machine B, it is a category error. It is a sequence element rather than a container. Even if it were allowed that a position within a sequence were a container and thus could have the property of being empty, the symbol represents that there is no symbol in the very location it is found. Hence, to ascribe an appropriate meaning to the empty symbol, the entire system must be kept including the mapping to machine A, then the empty symbol found on machine B means that if machine A were used instead, the same location in the tape sequence would be an empty set. However, this feels unsatisfactory, because in all other respects, machine B is a perfectly well defined Turing Machine all by itself.

    Going back to Turing's moniker of blank does limit the focus solely to machine B, because the original paper by Turing states the definition of blank meaning "no symbol", as was already discussed. Calling it blank is merely the same name colored by the engineering of wood pulp. However, there is a pleasing property of the blank, i.e. the empty symbol, that is valuable and unique to it. It prints as a space in diagrams given in text books and in the output of Turing Machine simulators. There is an analogous symbolic system that also has this characteristic, and is being leveraged in these situations: the ASCII hex 20, called SP. It prints as a space leaving an area of the paper it is printed on blank. Perhaps a better name for the ersatz empty symbol is SP.

    @@ -621,9 +624,9 @@ The computation theoretic TTCA Machine -

    This chapter presents a modified computation theoretic Turing Machine with three structural additions. First, it separates control flow from data flow, ensuring that payload symbols do not needlessly expand the control state machine. Second, it unifies the control and data symbol sets into a single alphabet to natively support explicit communications protocols even in the presence of recursion and self-recursion. Finally, it implements a cascading next-state evaluation hierarchy, permitting the programmer to formally define and handle meta-symbols such as unspecified, while also making it more convenient to code communication protocols.

    +

    This chapter presents a modified computation theoretic Turing Machine with three structural additions. First, it separates control flow from data flow, ensuring that payload symbols do not needlessly expand the control state machine. Second, it unifies the control and data symbol sets into a single alphabet to natively support explicit communications protocols even in the presence of recursion and self-recursion. Finally, it implements a cascading next-state evaluation hierarchy, permitting the programmer to formally define and handle meta-symbols while also making it more convenient to program communication protocols.

    -

    The unspecified symbol

    +

    The unspecified meta-symbol

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

    @@ -631,11 +634,11 @@

    While using the standard library to write tapes, the uninitialized part of the tape could not be read until after it was written, so early tape machines indeed enforced the "read only after write" rule. However, if the programmer were to seek the head back into the device file to do fresh work and perform reads and writes, the device EOF would be nowhere in sight. The burden of the "read only after write" rule would then fall on the shoulders of the programmer, as would the task of structuring the data.

    -

    Core memory, and later system memory, was random access and initially fully accessible. The data would be whatever scrambled mess the machine booted with, or in early virtual memory systems, whatever was left over from the prior use of the page. The approach of recycling pages was a security hazard, so today a page is initially allocated from a read-only zero page, and due to a copy-on-write trap, a new page will be created in memory then the original page copied to it, thus scrubbing it with zeros. For pointers the zero pointer is an a sense an empty symbol, and an attempt to dereference it will cause a fault. However, on real machines, there are many integer values used, and these can also be zero. Thus the zeros of the new page are not identical to saying the page contains all empty symbols. In this system, the programmer is again burdened with maintaining the "read only after write" rule. Compilers and interpreters will attempt to help with this by throwing errors upon the use of uninitialized data that they detect.

    +

    Core memory, and later system memory, was random access and initially fully accessible. The data would be whatever scrambled mess the machine booted with, or in early virtual memory systems, whatever was left over from the prior use of the page. The approach of recycling pages was a security hazard, so today a page is initially allocated from a read-only zero page, and due to a copy-on-write trap, a new page will be created in memory then the original page copied to it, thus scrubbing it with zeros. The zero pointer is in a sense an empty symbol, as an attempt to dereference it will cause a fault. However, on real machines, there are many integer values used, and these can also be zero. Thus the zeros of the new page are not identical to saying the page contains all empty symbols. In this system, the programmer is again burdened with maintaining the "read only after write" rule. Compilers and interpreters often help with this by attempting to detecting the use of uninitialized data and throwing an error.

    A violation of "read only after write" could be detected by a modified computation theoretic Turing Machine if, instead of an empty symbol, the initial tape is filled with the unspecified symbol. The end objective is to detect an erroneous condition, which is useful for debugging and testing. Conventionally, mathematicians do not concern themselves with the test and debug phases of programming a Turing Machine, but rather concern themselves with answering computation theoretic questions about known working Turing Machine programs. Though perhaps an algorithm could be studied for this very quality of not ever making decisions based on unspecified data. Nor do real machines have an unspecified symbol; rather, a program reads garbage from memory locations with unspecified data. There is precedent for an x, unknown, logic state in hardware simulators.

    -

    Like the empty symbol, unspecified is a meta-symbol. It describes the data, or lack thereof, rather than being the data. Specifically, the unspecified symbol says that another machine, a machine A, would have a singular alphabet symbol at the memory location, but our machine B is not being instructed as to which symbol it is. Because the Turing Machine state transition function requires a specific symbol value, reading an unspecified symbol would break the machine. Of course, that would be a bad thing, so some sort of modification to the Turing Machine definition is required for working with an unspecified symbol.

    +

    Like the empty symbol, unspecified is a meta-symbol. It describes the data, or lack thereof, rather than being the data. Specifically, the unspecified symbol says that another machine, a machine A, would have a singular alphabet symbol at the memory location, but our machine B is not being informed as to which symbol it is. Because the Turing Machine state transition function requires a specific symbol value, reading an unspecified symbol, and then using it to make a decision as though it were a concrete symbol, would be an error, unless that control path was for the very purpose of detecting this error.

    Reasons that memory can be unspecified include:

      @@ -644,7 +647,7 @@
    1. The data is effectively unspecified because the program, by design, does not make decisions based upon its value.
    -

    An example of effectively unspecified data would be a program that reverses a string without looking at the values being reversed. A string reverse function need not inspect the value of the string; it only needs to recognize the structural boundaries established by the writing protocol. Yet the conventional Turing Machine is incapable of doing this, and worse, as we saw, there is a proportional increase in the number of states for the reverse string controller when the number of symbols, symbols that could have been ignored for control purposes, is expanded.

    +

    An example of effectively unspecified data would be a program that reverses a string without looking at the values being reversed. A string reverse function need not inspect the value of the string; it only needs to recognize the structural boundaries established by the writing protocol. Yet the conventional Turing Machine is incapable of doing this, and worse, as we saw, there is an explosion in the number of states for the reverse string controller against word length.

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

    @@ -656,30 +659,34 @@
  1. The machine utilizes a Moore-style programmed state controller, so that actions can be managed separately from state transitions.
  2. 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. Here, s stands for 'status', while d stands for 'data'.
      2. +
    2. 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.
    3. Write and read actions are given an operand designating the target or source register respectively, either s or d.
    3. -
  3. 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 S_i, σ, S_{i+1} \rangle): +
  4. 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):
      -
    1. state-specific transition default pairs, which have the form \langle S_i, S_{i+1} \rangle
      2. -
    2. status-specific transition default pairs, which have the form \langle σ, S_{i+1} \rangle
      3. -
    3. a global default transition, which has the form S_{i+1}
      4. +
    4. state-specific transition default pairs, which have the form \langle q_i, q_{i+1} \rangle
      5. +
    5. status-specific transition default pairs, which have the form \langle σ, q_{i+1} \rangle
      6. +
    6. a global default transition, which has the form q_{i+1}
+

Here the subscript i is a device used to emphasize that q_i and q_{i+1} can be any members of the total set of states, Q. State q_0 refers specifically to the initial state. Also note, later the spartan q will be used to denote the contents of the q register, the current state register.

+ +

The Hopcroft and Ullman machine definition specified a next state function, δ. Here we instead use next state tables that cascade, and as tables are containers, we denote these using a capital letter as Δ_0, Δ_1, Δ_2, and Δ_3. +

The new machine evaluates next-state transitions through these four layers, in order, progressing to the next layer only when no transition is found in the prior layer:

  1. Conditional (Δ_0): Selects the transition rule that matches the current state and the value of the status register.
    2. -
  2. State Default (Δ_1): If no conditional next state rule is found, selects the default transition rule that matches the current state.
    3. -
  3. Status Default (Δ_2): If no next state rule has been found, selects the default transition rule that matches the current machine status.
    4. -
  4. Global Default (Δ_3): An unconditional transition of last resort if no prior layer provides a valid next state.
    5. +
  5. State Default (Δ_1): Selects the default transition rule that matches the current state.
    6. +
  6. Status Default (Δ_2): Selects the default transition rule that matches the current machine status.
    7. +
  7. Global Default (Δ_3): A single table that holds the next state of last resort.
- +

Programmers will typically use the Global Default arc, Δ_3, to take the machine to an error state when they have mistakenly left the next state transition undefined. However, it is conceivable for some machines that if no other next state is defined, there is a single logical state that should be visited, and this condition is not an error. If no Global Default arc is specified, and no next state is found, the machine hangs.

-

This approach of cascading next-state decisions does more than merely make the machine more convenient to program; it also enables a programmer to support an unspecified symbol. For example, a programmer can incorporate a first-order unspecified symbol by first adding it to the alphabet Σ, adding a Q_unspecified state to Q, and then adding a status default arc to Δ_2 of \langle \mathtt{s{\cdot}unspecified}, \mathrm{Q\_unspecified} \rangle. Finally, the programmer adds Q_unspecified to the set of halting states. Then, if the machine attempts to make a decision upon the unspecified symbol, the machine will transition to the Q_unspecified state and halt. Such a machine can then be analyzed to see if it ever visits the Q_unspecified state, although the analyst must take care, because if he puts some thought into this, he will realize that no such universal analyzer can exist.

+

This approach of cascading next-state decisions does more than merely make the machine more convenient to program; it also enables a programmer to support an unspecified symbol. For example, a programmer can incorporate a first-order unspecified symbol by first adding it to the alphabet Σ, adding a Q_unspecified state to Q, and then adding a status default arc to Δ_2 of \langle \mathtt{s{·}unspecified}, \mathit{Q\_unspecified} \rangle. Finally, the programmer adds Q_unspecified to the set of halting states. Then, if the machine attempts to make a decision upon the unspecified symbol, the machine will transition to the Q_unspecified state and halt. Such a machine can then be analyzed to see if it ever visits the Q_unspecified state, although the analyst must take care, because if he puts some thought into this, he will realize that no such universal analyzer can exist.

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.

@@ -689,23 +696,23 @@

The TTCA Machine fixed part

- \mathrm{MF} = (\mathrm{QF}, \mathrm{ΣF}, \mathrm{AF}) + \mathit{MF} = (\mathit{QF}, \mathit{ΣF}, \mathit{AF})
-

In the following, the middle dot acts as a namespace operator, N{\cdot}x. By doing this we assure there will be no aliasing with the symbols provided by the programmer when he defines a programmed state controller.

+

In the following, the middle dot acts as a namespace operator, N{·}x. By doing this we assure there will be no aliasing with the symbols provided by the programmer when he defines a programmed state controller.

The set of predefined states:

- \mathrm{QF} = \{\mathrm{QF}{\cdot}\mathtt{initial}\} + \mathit{QF} = \{\mathit{QF}{·}\mathtt{initial}\}

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 only fixed actions:

+

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

\begin{aligned} - \mathrm{AF} = \{& \\ + \mathit{AF} = \{& \\ & \mathtt{no\_op} \\ , & \mathtt{left} \\ , & \mathtt{right} \\ @@ -720,14 +727,14 @@

The set of predefined symbols:

- \mathrm{ΣF} = \{\mathrm{ΣF}{\cdot}\mathtt{leftmost}\} + \mathit{ΣF} = \{\mathit{ΣF}{·}\mathtt{leftmost}\}

Machine variables

- \mathrm{MV} = (q, s, d) + \mathit{MV} = (q, s, d)
@@ -742,25 +749,25 @@
- \mathrm{MP} = (\mathrm{QP}, \mathrm{ΣP}, \lambda\mathrm{P}, Δ_0, Δ_1, Δ_2, Δ_3, \mathrm{HP}) + \mathit{MP} = (\mathit{QP}, \mathit{ΣP}, \mathit{ΛP}, Δ_0, Δ_1, Δ_2, Δ_3, \mathit{HP})

A set of programmed state symbols:

- \mathrm{QP} + \mathit{QP}

A set of programmed data symbols:

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

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

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

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

where q_i is matched to the current state, and a is a member of \mathit{A}.

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

@@ -779,7 +786,7 @@
Δ_2 = \{ \langle σ, q_{i+1} \rangle, \dots \}
-

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

+

where σ matches the symbol in s register, and upon a match q_{i+1} will be taken as the next state.

The global default next state:

@@ -789,25 +796,38 @@

A set of programmer-defined halting states:

- \mathrm{HP} + \mathit{HP}

The TTCA Machine definition in total

- M = (q, s, d, Q, Σ, \mathrm{AF}, \lambda\mathrm{P}, Δ, \mathrm{HP}) + M = (q, s, d, Q, Σ, A, Λ, Δ, H)
+

The variables used by the executor, \mathit{MV} = (q, s, d).

+

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

- Q = \mathrm{QF} \cup \mathrm{QP} + Q = \mathit{QF} \cup \mathit{QP}

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

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

All members of the set of available actions are fixed:

+ +
+ A = \mathit{AF} +
+ +

The table of state-action pairs is strictly programmed.

+
+ Λ = \mathit{ΛP}

The ordered sequence of next state transition rules:

@@ -815,43 +835,47 @@ Δ = [Δ_0 \mid Δ_1 \mid Δ_2 \mid Δ_3]
+

The set of halt states is strictly programmed, and thus could be empty.

+
+ H = \mathit{HP} +
+

Computation theoretic TTCA Machine executor

-

To execute the programmed TTCA Machine, a person must maintain the current machine variables MV and evaluate the programmed logic in an repeating two-phase cycle, until a halting state is reached. Because this is a Moore-style architecture, the execution of an action is isolated from the evaluation of the next state transition.

+

Computer was at one time a job title. Turing described a clerk following directions to cause his machine to go, thus implying that mathematicians are mere automata chained to following the procedures they derive. So then an executor can be a person, perhaps a student who is studying the computation theoretic machine, and has a homework assignment of showing what it does.

+ +

The executor takes the TTCA machine through three stages of execution: initialization, programmed control, and halting. While going through these stages, the executor gives the \mathit{MV} variables values.

+ +

This description assumes support is programmed in for the first order unspecified symbol.

Initialization stage

Before the first cycle begins, a tape is selected and mounted. The read/write head is positioned over the leftmost tape cell. The machine variables are initialized as follows:

    -
  • The current state q is set to QF{·}\mathtt{initial}.
    • -
  • The data register d is initialized to hold the ΣF{·}\mathtt{unspecified} symbol.
    • -
  • The gate register g is initialized ΣF{·}\mathtt{unspecified} symbol.
    • +
  • The current state q is set to \mathit{QF}{·}\mathtt{initial}.
    • +
  • The data register d is initialized to hold the \mathit{ΣF}{·}\mathtt{unspecified} symbol.
    • +
  • The status register s is initialized to hold the \mathit{ΣF}{·}\mathtt{unspecified} symbol.
- +

Programmed control stage

Phase 1: The action

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

    -
  1. Locate the current state q within the programmed actions set λP.
    2. -
  2. Perform the associated action a ∈ AF.
    3. +
  3. Locate the current state q within the actions table Λ.
    4. +
  4. Perform the associated action λ.
+

If the action 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 Δ = [ΔF_0 | Δ_1 | Δ_2 | Δ_3]. The evaluation follows this hierarchy, stopping and branching at the first valid match:

-
    -
  1. Evaluate ΔF_0: Inspect the gate register g. If it holds the ΣF{·}\mathtt{unspecified} symbol, the next state becomes QF{·}\mathtt{unspecified\_decision}. This halts standard programmed execution.
    2. -
  2. Evaluate Δ_1: Search the programmed conditional rules for a triple that matches the current state q and the exact symbol currently held in the gate register g. If a match is found, the next state updates to the specified q_1.
    3. -
  3. Evaluate Δ_2: If no conditional rule matches, search the programmed default rules for a pair matching the current state q. If a match is found, the next state updates to the specified q_1.
    4. -
  4. Evaluate Δ_3: If all prior evaluations fail to yield a match, unconditionally update the next state to the global fallback transition specified by Δ_3.
    5. -
+

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.

Halting stage

-

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

+

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.

-

The TTCA Machine programmed string reverse

-

Because the TTCA Machine separates the data path from the control path, it is possible to reverse a string without inspecting the payload. The programmed controller only needs to recognize the structural boundaries of the data protocol. When a payload symbol is encountered, the controller executes a read_d action, placing the value into a data register, which is not examined for decision-making purposes. When a value is used to base a decision upon, the controller executes a read_g, placing the value into a register connected to the arc comparators. Because actions are bound to states rather than transitions, reading and stepping are distinct states. This combination of features results in a controller that has threads of serialized execution.

+

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.

# TTCA Machine String Reverse @@ -866,7 +890,7 @@ table: # Phase 1: Scan right to EOM and initialize the EOR marker. Q·initial: - λ: read_g + λ: read(s) δ: (EOM: Q·Setup_EOR) Q·Search_EOM_0 @@ -882,7 +906,7 @@ Q·Write_EOR Q·Write_EOR: - λ: write_σ(EOR) + λ: write(σ ,EOR) δ: Q·Fetch_0 @@ -893,7 +917,7 @@ Q·Fetch_1 Q·Fetch_1: - λ: read_g + λ: read(s) δ: (EOM: Q·Check_Boundary) (SP: Q·Check_Boundary) @@ -906,7 +930,7 @@ Q·Fetch_0 Q·Read_Data: - λ: read_d + λ: read(d) δ: Q·Check_Last_Char @@ -918,7 +942,7 @@ # Phase 3: Mark the location and carry the opaque data rightward. Q·Place_SP: - λ: write_σ(SP) + λ: write(σ ,SP) δ: Q·Carry_0 @@ -928,14 +952,14 @@ Q·Carry_1 Q·Carry_1: - λ: read_g + λ: read(s) δ: (EOR: Q·Drop) Q·Carry_0 # Phase 4: Deposit the data and advance the EOR boundary. Q·Drop: - λ: write_d + λ: write(d) δ: Q·Advance_EOR_0 @@ -945,7 +969,7 @@ Q·Advance_EOR_1 Q·Advance_EOR_1: - λ: write_σ(EOR) + λ: write(σ ,EOR) δ: Q·Return_0 @@ -956,14 +980,14 @@ Q·Return_1 Q·Return_1: - λ: read_g + λ: read(s) δ: (EOM: Q·Fetch_0) Q·Return_0 # Phase 6: Final symbol carry and clean halt. Q·Place_Last: - λ: write_σ(SP) + λ: write(σ ,SP) δ: Q·Carry_Last_0 @@ -973,13 +997,13 @@ Q·Carry_Last_1 Q·Carry_Last_1: - λ: read_g + λ: read(s) δ: (EOR: Q·Drop_Last) Q·Carry_Last_0 Q·Drop_Last: - λ: write_d + λ: write(d) δ: Q·Advance_EOR_Last_0 @@ -989,7 +1013,7 @@ Q·Advance_EOR_Last_1 Q·Advance_EOR_Last_1: - λ: write_σ(EOR) + λ: write(σ ,EOR) δ: Q·Done @@ -1000,56 +1024,56 @@

The number of states is constant at 24 independent of how much data is to be reversed. No arc refers to a payload value.

-

The form of this diagram shows a lead in, a long loop, and a tail leading to done. This is suggestive of code followed by a while loop that breaks out and then further code completes the program.

+

The form of this diagram shows a lead-in, a long loop, and a tail leading to done. This is suggestive of code followed by a while loop that breaks out, with further code completing the program.

void TTCA·reverse_string() { // Initialization: Scan to EOM and setup the EOR boundary - read_g(); - while(g != EOM){right(); read_g();} + read('s'); + while(s != EOM){right(); read('s');} right(); - write_σ(EOR); + write('σ' ,EOR); while(true){ // The Fetch Pivot: Locate the next unprocessed symbol left(); - read_g(); - while(g == EOM || g == SP){ + read('s'); + while(s == EOM || s == SP){ status(); // Termination: Short-circuit for empty string - if(g == leftmost) return; + if(s == leftmost) return; left(); - read_g(); + read('s'); } - read_d(); + read('d'); status(); // Center Break: Q·Check_Last_Char routes to the final chain - if(g == leftmost) break; + if(s == leftmost) break; // Main Carry Loop: Mark, carry, drop, and return to pivot - write_σ(SP); + write('σ' ,SP); right(); - read_g(); - while(g != EOR){right(); read_g();} - write_d(); + read('s'); + while(s != EOR){right(); read('s');} + write('d'); right(); - write_σ(EOR); + write('σ' ,EOR); left(); - read_g(); - while(g != EOM){left(); read_g();} + read('s'); + while(s != EOM){left(); read('s');} } // Final Symbol Chain: Handle the last payload without a return sweep - write_σ(SP); + write('σ' ,SP); right(); - read_g(); - while(g != EOR){right(); read_g();} - write_d(); + read('s'); + while(s != EOR){right(); read('s');} + write('d'); right(); - write_σ(EOR); + write('σ' ,EOR); // Termination: Q·Done return; @@ -1068,9 +1092,9 @@
-

Two headed reverse string example

+

Two-headed reverse string example

-

The reverse string machine spends a lot of time shuttling the head between two context areas. One context area for the original string, and one for the resulting reversed string. This suggests that a two head version would be faster. The following is the two head state machine definition:

+

The reverse string machine spends a lot of time shuttling the head between two context areas: one for the original string, and one for the resulting reversed string. This suggests that a two-head version would be faster. The following is the two-head state machine definition:

# TTCA Two-Head String Reverse @@ -1082,7 +1106,7 @@ table: # Phase 1: Both heads scan right to the EOM pivot Q·initial: - λ: read_g(0) + λ: read('s' ,0) δ: (EOM: Q·Check_Empty) Q·Scan_Right_0 @@ -1121,7 +1145,7 @@ # Phase 3: The Linear Copy Loop Q·Copy_Read: - λ: read_d(0) + λ: read('d' ,0) δ: Q·Copy_Status @@ -1132,12 +1156,12 @@ Q·Copy_Erase Q·Copy_Erase: - λ: write_σ(0 ,SP) + λ: write('σ' ,0 ,SP) δ: Q·Copy_Write Q·Copy_Write: - λ: write_d(1) + λ: write('d' ,1) δ: Q·Copy_Advance_1 @@ -1153,12 +1177,12 @@ # Phase 4: Final Symbol and Clean Halt Q·Copy_Last_Erase: - λ: write_σ(0 ,SP) + λ: write('σ' ,0 ,SP) δ: Q·Copy_Last_Write Q·Copy_Last_Write: - λ: write_d(1) + λ: write('d' ,1) δ: Q·Copy_Last_Advance @@ -1168,16 +1192,16 @@ Q·Write_EOR_Done Q·Write_EOR_Done: - λ: write_σ(1 ,EOR) + λ: write('σ' ,1 ,EOR) δ: Q·Done TTCAM 2 hd reverse machine -

Analysis of the two headed reverse string machine

+

Analysis of the two-headed reverse string machine

-

The number of states has dropped from 24 to 17, while the speed increase is dramatic, with the former quadratic performance becoming linear performance. The total number of steps for reversing an n symbol long string using a two-head TTCA architecture:

+

The number of states has dropped from 24 to 18, while the speed increase is dramatic, with the former quadratic performance becoming linear performance. The total number of steps for reversing an n symbol string using a two-head TTCA architecture:

@@ -1194,14 +1218,14 @@ void TTCA·reverse_string_2_head() { // Phase 1: Both heads scan right to the EOM pivot - read_g(0); - while(g != EOM){right(0); right(1); read_g(0);} + read('s' ,0); + while(s != EOM){right(0); right(1); read('s' ,0);} // Phase 2: Setup pointers or short-circuit on empty string status(0); - if(g == leftmost){ + if(s == leftmost){ right(1); - write_σ(1 ,EOR); + write('σ' ,1 ,EOR); return; } @@ -1210,68 +1234,67 @@ // Phase 3: The Linear Copy Loop while(true){ - read_d(0); + read('d' ,0); status(0); // Break out to process the final character - if(g == leftmost) break; + if(s == leftmost) break; - write_σ(0 ,SP); - write_d(1); + write('σ' ,0 ,SP); + write('d' ,1); right(1); left(0); } // Phase 4: Final character, advance, and clean halt - write_σ(0 ,SP); - write_d(1); + write('σ' ,0 ,SP); + write('d' ,1); right(1); - write_σ(1 ,EOR); + write('σ' ,1 ,EOR); return; } -

This machine has a single tape with two heads marking two separate context areas. Because the areas do not overlap, this situation is indistinguishable from the case of the machine having two separate tapes, each with its own head. Hartmanis and Stearns established the original proof that simulating a Turing Machine with multiple tapes, each with its own head, on a single-tape single-head machine incurs a quadratic time penalty J. Hartmanis and R. E. Stearns, "On the computational complexity of algorithms," Transactions of the American Mathematical Society 117 (1965): 285-306.. Hopcroft and Ullman formalize this relationship in their text John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation (Reading: Addison Wesley, 1979), 292.. This explains why in this example of a string reverse machine, when the second head was added to eliminate the head shuttling, the quadratic term disappeared. Not all quadratic terms are due to shuttling, but this one happens to be such a case.

+

This machine has a single tape with two heads marking two separate context areas. Because the areas do not overlap, this situation is indistinguishable from the case of the machine having two separate tapes, each with its own head. Hartmanis and Stearns established the original proof that simulating a Turing Machine with multiple tapes, each with its own head, on a single-tape, single-head machine incurs a quadratic time penalty J. Hartmanis and R. E. Stearns, "On the computational complexity of algorithms," Transactions of the American Mathematical Society 117 (1965): 285-306.. Hopcroft and Ullman formalize this relationship in their text John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation (Reading: Addison Wesley, 1979), 292.. This explains why in this example of a string reverse machine, when the second head was added to eliminate the head shuttling, the quadratic term disappeared. Not all quadratic terms in step count formulas are due to shuttling, but this one happens to be such a case.

The time complexity of the longest compute time input of length n dropping from O(n^2) to O(n) is computation theoretic consequential, so we should make a choice as to which machine to use as a reference. Given that real computers have multiple pointers into different memory contexts, the multi-head Turing Machine is the more suitable reference model.

-

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

Adding heads functions as a specialized optimization rather than a universal method for improving performance complexity. Quadratic performance improvements manifest only under specific conditions. Even when they occur, the improvement remains insufficiently strong to alter the asymptotic performance if higher-order terms exist in the step-count polynomial. Furthermore, eliminating shuttling is structurally incapable of reducing a linear step count to a constant-time step count; the reason is that n is unbounded, while adding k heads only divides 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
+
Figure 1: A Turing Machine
-

The prior chapter on the computation theoretic TTCA machine serves as the architectural template, with only a few modifications. The architecture has no 'unspecified' symbol. Rather, an actual value is transacted. Now that data and control have been separated, the controller is practical to implement, and even more so because it was defined in terms of tables that can be built in hardware. As the status command returns the cell type, it will in its current form be able to return 'rightmost', so the right end of the tape can be detected. In order to extend the tape, the machine will stop and ask the operator to mount a new reel. This could be signaled when the user attempts to step right of rightmost, either by a panel light that illuminates upon the machine finding a rightmost status, or by the program printing a message on the console teletype. 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 modifications. The architecture requires explicit data rather than accepting meta-symbols like 'unspecified' as presumed initial values 'by definition'. Actual values are transacted. Now that data and control have been separated, the controller is practical to implement, and even more so because it was defined in terms of tables that can be built in hardware. As the status command returns the cell type, it will in its current form be able to return 'rightmost', so the right end of the tape can be detected. In order to extend the tape, the machine will stop and ask the operator to mount a new reel. This could be signaled when the user attempts to step right of rightmost, either by a panel light that illuminates upon the machine finding a rightmost status, or by the program printing a message on the console teletype. 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 space, precisely two cells. As another example, 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 executed at the speed of a human operator, the operator would likely abandon the process before it finished. This highlights a necessary attribute of good software: utility. It also exposes a limitation of pure computation theory, which abstracts away physical time. Nevertheless, formal analysis remains a necessity. Consider an exponential-time program processing worst-case operands: its execution time explodes relative to input length, rapidly exceeding the age of the universe. In such extremes, empirical wall-clock measurement becomes superfluous. Computation theory does not calculate wall-clock durations; rather, it classifies a program's behavior, which has implications for wall-clock time.

+

If a program executed at the speed of a human operator, the operator would likely abandon the process before it finished. This highlights a necessary attribute of good software: utility. It also exposes a limitation of pure computation theory, which abstracts away physical time. Nevertheless, formal analysis remains a necessity. Consider an exponential-time program processing worst-case operands: its execution time explodes relative to input length, rapidly exceeding the age of the universe. In such extremes, empirical wall-clock measurement becomes superfluous. Computation theory classifies a program's behavior, which establishes structural implications for wall-clock time, rather than calculating absolute durations.

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.

-

This book provides the transformational steps needed to go from the Turing Machine to real machines, and one objective is to recover some correspondence between the machine steps of the model and the wall-clock time the machine takes to run. Given this, the system operator changing tapes creates a step that is disproportionately longer than the other steps, a factor that requires architectural mediation, but will always remain. For example, this structural penalty resurfaces in the form of cache misses causing a machine to reach into system memory, or worse, page faults, requiring a machine to go back to disk. -

+

This book provides the transformational steps needed to go from the Turing Machine to real machines, and one objective is to recover some correspondence between the machine steps of the model and the wall-clock time the machine takes to run. Given this, the system operator changing tapes creates a step that is disproportionately longer than the other steps, a factor that requires architectural mediation, but will always remain. For example, this structural penalty resurfaces in the form of cache misses causing a machine to reach into system memory, or worse, page faults, requiring a machine to go back to disk.

-

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, so it only needs to run once.

+

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, and thus only needs to be run once.

-

Another practical solution, one that also applies to the first run of the program, is to analyze the logic to compute the time per step and extrapolate the total execution time. This is not universally possible; for some programs, tracing a path through the execution logic is as computationally complex as running the program itself, taking us back to the analysis in the prior paragraph. However, this phenomena does not apply to all programs. Consider the previously mentioned examples of the ten step machine, the machine bouncing between two cells, and the Arabic counting machine.

+

Another practical solution, one that also applies to the first run of the program, is to analyze the logic to compute the time per step and extrapolate the total execution time. This is structurally viable only for specific programs; for others, tracing a path through the execution logic is as computationally complex as running the program itself, taking us back to the analysis in the prior paragraph. However, this phenomenon restricts itself to specific programmatic classes. Consider the previously mentioned examples of the ten step machine, the machine bouncing between two cells, and the Arabic counting machine. All of those programs can be, indeed were, analyzed before they were run.

-

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. Consider 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 from an erroneous program 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.

+

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. Consider the Pentium divider. It did not matter how many millions of times the result was accurate; the fact remains that customers later found inputs that yielded wildly inaccurate results. Only by elevating the analysis to the structural logic of the code can such an eventuality from an erroneous program 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:

    -
  1. read → σ
    2. -
  2. write σ
    3. -
  3. status → γ
    4. +
  4. read() → σ
    5. +
  5. write(σ)
    6. +
  6. status() → s

On this model of machine, the HU status is identical to the indicated cell's type. The cell type is not read from the tape; rather, it is derived from the head's physical relationship to the ends of the tape. Consequently, the HU works in conjunction with the TTU to derive the status. (The tape transport unit, the TTU, is discussed in the next section.) As established in the section discussing cells, cell types are:

@@ -1284,10 +1307,10 @@

A computation theoretic Turing Machine would never encounter a status of rightmost or island. This is where a finite extendable tape structurally differs from a single-ended theoretical tape.

- +

For a realized TTU, data can only be read or written when there is relative motion between the head and the tape. Consequently, in an HU implementation, data and status registers are updated from an internal buffer that acquires data during head motion. Conversely, a write value is buffered until subsequent head motion provides the opportunity to write it to the tape.

- -

Because values can only be read or written to a tape when the tape is in motion, it is advantageous to exaggerate the motion of step commands and to cache a small number of values. In addition, most architectures that make use of a tape drive will attempt to leverage high throughput in an effort to hide high latency by reading or writing blocks of symbols per tape access. Note though, the basic TTCA machine organization lacks the core memory required for buffering blocks.

+ +

Because values can only be read or written to a tape when the tape is in motion, it is advantageous to exaggerate the motion of step commands and to cache a small number of values. In addition, most architectures that make use of a tape drive will attempt to leverage high throughput in an effort to hide high latency by reading or writing blocks of symbols per tape access. Note, however, that the basic TTCA Machine organization lacks the core memory required for buffering blocks.

Tape transport unit, TTU

@@ -1298,25 +1321,24 @@
  • one or more HUs
  • a data buffer holding a single symbol
  • a status buffer
    • -
  • a single symbol FIFO command buffer, written by the programmed controller, acted upon immediately by the TTU
    • +
  • a command buffer, written by the programmed controller, acted upon immediately by the TTU

    • The TTU interfaces with the executor, which in turn gates the flow of data through the machine. The executor controls the clock and reset lines, and through this supervises the customer programmed control unit, the CPCU. This two-layer control system is single-threaded and issues the following commands to each selected TTU:

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

    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 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 selected head moves left or right by one cell.

    -

    The customer programmed control unit, CPCU

    +

    The customer programmed control unit, CPCU

    -

    The controller is programmed via patch panels. The panels would look something like what is shown in the following ASCII art blocks. Note that ● indicates an illuminated indicator light, whereas ○ is not illuminated. [/] represents an open toggle switch, while [—] is a closed one. {*} is a pushed button, while { } is a button that is not pushed. ( ) represents a hole for a banana plug. Each patch cord has a banana plug on each end. Plugging a patch cord between separate panels will void the warranty.

    +

    The controller is programmed via patch panels. The panels would look something like what is shown in the following ASCII art blocks. Note that ● indicates an illuminated indicator light, whereas ○ is not illuminated. [/] represents an open toggle switch, while [—] is a closed one. {*} is a pushed button, while { } is a button that is not pushed. ( ) represents a hole for a banana plug. Each patch cord has a banana plug on each end. Plugging a patch cord between separate panels will void the warranty ;-).

                               [ CONTROL PANEL ]
@@ -1329,68 +1351,65 @@
       
    -                              [ State Transition Table ]
-                         +-----------------------------------+
-           current state | S0    S1    S2    S3    S4    S5  |
-        indicator lights |  ●     ○     ○     ○     ○     ○  |
-         halting toggles | [/]   [/]   [/]   [/]   [/]   [/] |
-                         +-----------------------------------+
-            ● g0 (Sym 0) | ( )   ( )   ( )   ( )   ( )   ( ) |
-            ○ g1 (Sym 1) | ( )   ( )   ( )   ( )   ( )   ( ) |
-            ○ g2 (Sym 2) | ( )   ( )   ( )   ( )   ( )   ( ) |
-            ○ g3 (Sym 3) | ( )   ( )   ( )   ( )   ( )   ( ) |
-            ○ g4 (Sym 4) | ( )   ( )   ( )   ( )   ( )   ( ) |
-                         |                                   |
-       destination state | ( )   ( )   ( )   ( )   ( )   ( ) |
-                         | ( )   ( )   ( )   ( )   ( )   ( ) |
-                         | ( )   ( )   ( )   ( )   ( )   ( ) |
-                         |                                   |
-       default transition| ( )   ( )   ( )   ( )   ( )   ( ) |
-       global transition |               ( )                 |
-                         +-----------------------------------+
+                                 [ State Transition Table ]
+                         +-------------------------------------------+
+           current state |  def   q0    q1    q2    q3    q4    q5   |
+                         |         ●     ○     ○     ○     ○     ○   |
+                    halt |        [/]   [/]   [/]   [/]   [/]   [/]  |
+                         +-------------------------------------------+
+                     def |  ( )   ( )   ( )   ( )   ( )   ( )   ( )  |
+                  ● s0   |  ( )   ( )   ( )   ( )   ( )   ( )   ( )  |
+                  ○ s1   |  ( )   ( )   ( )   ( )   ( )   ( )   ( )  |
+                  ○ s2   |  ( )   ( )   ( )   ( )   ( )   ( )   ( )  |
+                  ○ s3   |  ( )   ( )   ( )   ( )   ( )   ( )   ( )  |
+                  ○ s4   |  ( )   ( )   ( )   ( )   ( )   ( )   ( )  |
+                         |                                           |
+       destination state |        ( )   ( )   ( )   ( )   ( )   ( )  |
+                         +-------------------------------------------+
       
                                     [ Action ]
-                   +-----------------------------------+
-                   | S0    S1    S2    S3    S4    S5  |
-               Src | ( )   ( )   ( )   ( )   ( )   ( ) |
-                   +-----------------------------------+
-          right    | ( )   ( )   ( )   ( )   ( )   ( ) |
-          left     | ( )   ( )   ( )   ( )   ( )   ( ) |
-          read_g   | ( )   ( )   ( )   ( )   ( )   ( ) |
-          read_d   | ( )   ( )   ( )   ( )   ( )   ( ) |
-          write_g  | ( )   ( )   ( )   ( )   ( )   ( ) |
-          write_d  | ( )   ( )   ( )   ( )   ( )   ( ) |
-          write_σ  | ( )   ( )   ( )   ( )   ( )   ( ) |
-                   +-----------------------------------+
+                    +-----------------------------------+
+                    | q0    q1    q2    q3    q4    q5  |
+                Src | ( )   ( )   ( )   ( )   ( )   ( ) |
+                    +-----------------------------------+
+          right     | ( )   ( )   ( )   ( )   ( )   ( ) |
+          left      | ( )   ( )   ( )   ( )   ( )   ( ) |
+          read('s') | ( )   ( )   ( )   ( )   ( )   ( ) |
+          read('d') | ( )   ( )   ( )   ( )   ( )   ( ) |
+          write('s')| ( )   ( )   ( )   ( )   ( )   ( ) |
+          write('d')| ( )   ( )   ( )   ( )   ( )   ( ) |
+          write('σ')| ( )   ( )   ( )   ( )   ( )   ( ) |
+                    +-----------------------------------+
       
    -                        [ Sigma Select for write_σ ]
-                   +-----------------------------------+
-                   | S0    S1    S2    S3    S4    S5  |
-               Src | ( )   ( )   ( )   ( )   ( )   ( ) |
-                   +-----------------------------------+
-        g0 (Sym 0) | ( )   ( )   ( )   ( )   ( )   ( ) |
-        g1 (Sym 1) | ( )   ( )   ( )   ( )   ( )   ( ) |
-        g2 (Sym 2) | ( )   ( )   ( )   ( )   ( )   ( ) |
-        g3 (Sym 3) | ( )   ( )   ( )   ( )   ( )   ( ) |
-        g4 (Sym 4) | ( )   ( )   ( )   ( )   ( )   ( ) |
-                   +-----------------------------------+
+                        [ Sigma Select for write('σ') ]
+                    +-----------------------------------+
+                    | q0    q1    q2    q3    q4    q5  |
+                Src | ( )   ( )   ( )   ( )   ( )   ( ) |
+                    +-----------------------------------+
+                s0  | ( )   ( )   ( )   ( )   ( )   ( ) |
+                s1  | ( )   ( )   ( )   ( )   ( )   ( ) |
+                s2  | ( )   ( )   ( )   ( )   ( )   ( ) |
+                s3  | ( )   ( )   ( )   ( )   ( )   ( ) |
+                s4  | ( )   ( )   ( )   ( )   ( )   ( ) |
+                    +-----------------------------------+
    -

    The top section 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 S_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 section 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 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 gate symbol.

    +

    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.

    -

    Below the transition condition matrix 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.

    +

    The transition condition matrix integrates the default fallback logic structurally. The def column on the left handles the status default transitions, providing a physical mechanism for routing a specific status symbol to a destination state when no active conditional patch cord is present. The def row above the status symbols handles the state default transitions. The single hole at the intersection of this default row and default column represents the global default transition.

    -

    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 transition condition matrix is the destination state row. If the fan-in for a state requires multiple patch cords, a special banana plug adapter can be used, or the patch cords themselves can feature stackable sockets on the back of the plugs, allowing multiple incoming transitions to bridge into a single destination hole.

    -

    To program the controller, the programmer connects the patch cords. For example, routing a patch cord from the (S_2, g_2) intersection to S_3 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 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. 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 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.

    The machine block diagram

    @@ -1399,6 +1418,8 @@
    Figure TTCA block diagram
    +

    This section describes the TTCA machine organization. The diagram above shows the major components and their channels of communications. This instructs designers who will later draft schematics that will specify all of the connections.

    +

    Components

    1. Control Panel @@ -1428,8 +1449,6 @@
    2. Data bus
    -

    This section describes the TTCA machine organization. The diagram above shows the major components and their channels of communications. This instructs designers who will later draft schematics that will specify all of the connections.

    -

    As described in the computation theoretic section that is being used as the architectural template, "Computation theoretic TTCA Machine executor", the executor guides the machine through initialization, programmed control, and halting stages of execution. When in the programmed control stage, the CPCU most of the active control comes from the the CPCU. The Executor contains the power, reset, and clock logic. It has two modes of execution, the run mode in which the clock runs free. Secondly, the single step mode, in which clock pulses are sent with the push of a button.

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

    @@ -1441,9 +1460,9 @@

    The symbols of the alphabet are enumerated such that each symbol corresponds to a specific row index on the control panel. The value on of the g register is decoded, resulting in a one hot encoding of the gate 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 next state bank below, then the next state selected in the next state bank 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.

    - -

    Upon reset, the current state register initializes to a one-hot configuration with the bit for state S_0 asserted, while all other machine registers clear to zero. To prevent power-on initialization hazards—where unlatched logic could trap the machine in an illegal configuration, ignore subsequent reset commands, or induce physical hardware damage—the power switch incorporates a capacitor timer that maintains an active reset signal until supply voltages fully stabilize.

    + +

    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. To prevent power-on initialization hazards—where unlatched logic could trap the machine in an illegal configuration, ignore subsequent reset commands, or induce physical hardware damage—the power switch incorporates a capacitor timer that maintains an active reset signal until supply voltages fully stabilize.

    This design assumes that releasing the reset line causes the machine to begin execution immediately. While adequate for our baseline model, a deluxe variant would integrate a dedicated 'go' button and associated transition logic. @@ -1727,7 +1746,7 @@

    - 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 S_i or in state S_{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.

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

    @@ -2035,7 +2054,7 @@

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

    Evaluating and Extending

    @@ -2770,7 +2789,7 @@ 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 \cdot 2^{n-k} = 2^{n+2} - 2n - 4 + \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: @@ -2957,7 +2976,7 @@

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

    @@ -2972,10 +2991,10 @@ 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 band and out-of-band control

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

    @@ -2983,7 +3002,7 @@

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

    @@ -4244,6 +4263,6 @@ Now suppose defining a Turing Machine that initially has the head on the leftmos --> --> diff --git a/document/book/TTCA_machine.svg b/document/book/TTCA_machine.svg index ade5ebc..1016e6b 100644 --- a/document/book/TTCA_machine.svg +++ b/document/book/TTCA_machine.svg @@ -200,7 +200,7 @@ y="448.72119" id="text4777" transform="rotate(-90)" - style="stroke-width:0.829769">gs