From b7c0e51ecf2ff9a6f7c045bb80efaa1c7574ede2 Mon Sep 17 00:00:00 2001 From: Thomas Walker Lynch Date: Sat, 8 Aug 2026 13:32:59 +0000 Subject: [PATCH] chapter 5 revision --- document/book/TM-2026.html | 165 +++++++++++++++++++++++++++++++++---- 1 file changed, 148 insertions(+), 17 deletions(-) diff --git a/document/book/TM-2026.html b/document/book/TM-2026.html index cc476f1..d893755 100644 --- a/document/book/TM-2026.html +++ b/document/book/TM-2026.html @@ -90,17 +90,17 @@

One afternoon I was fortunate to have lunch in Berkeley with Bill Kahan, a pioneer in applied number theory, and our conversation turned to errors in numeric computation. I observed that an error is merely an opportunity to do more computing. Bill seemed to like the remark; he repeated it in a Dr. Dobb's interview, where it was credited to him. When we met again, I asked him about it. He apologized, explaining that the interviewer had created something rather than reporting it, and that he was surprised himself by what he read. The apology was unnecessary. I had intended to summarize Kahan's own work. He was instrumental in creating IEEE Std. 754, where an exceptional condition, more informally an "error", need not end computation but can serve as a gateway to a higher symbolic algebra. I found that architecture inspiring, and my comment had been intended to acknowledge his inspiration.

-

In practical computing the symbol algebra of the IEEE Std. 754 quickly devolves into the catch all indeterminate value, the so called NaN, which tends to leave programmers wishing to extend the system. Kulisch and Miranker attempted to formalize computer arithmetic, and started by reasoning about a screen that laid out over the real number space. Boehm and Cartwright introduced a concept of Constructive Real Numbers, where precision of computation was extended upon demand. And through Stephen Wolfram's vision, Mathematica provides a complete symbolic math manipulation package, where a symbolic expression can be reduced before being evaluated. For evaluation they then track loss of precision through significance arithmetic. In my own work, I have suggested an analysis step first, where required precision is derived, followed by computation. However, among these there is still missing a formalism of passing through the gateway upon an error, so to speak. Mathematica comes the closest.

+

In practical computing the symbol algebra of the IEEE Std. 754 quickly devolves into the catch-all indeterminate value, the so-called NaN, which tends to leave programmers wishing to extend the system. Kulisch and Miranker attempted to formalize computer arithmetic, and started by reasoning about a screen that laid out over the real number space. Boehm and Cartwright introduced a concept of Constructive Real Numbers, where precision of computation was extended upon demand. And through Stephen Wolfram's vision, Mathematica provides a complete symbolic math manipulation package, where a symbolic expression can be reduced before being evaluated. For evaluation they then track loss of precision through significance arithmetic. In my own work, I have suggested an analysis step first, where required precision is derived, followed by computation. However, among these there is still missing a formalism of passing through the gateway upon an error, so to speak. Mathematica comes the closest.

-

John Gustafson also brought up the topic of the nature of error shortly before publishing "The End of Error". He now has another proposal based on variable precision arithmetic known as "posits". There was so much I wanted to say when we spoke, but I could not formulate the thoughts. I had learned a great deal while doing formal analysis of the algorithms I had put on the Am29050, Am486, and K5 processors at AMD, but when I tried to articulate this, I only stammered. I feel that I fell short, as all I could do is point at my already published work at that time on high radix online arithmetic. So this volume is my answer to John's question. Albeit it is a little late, well years late, but I hope it will still have some value.

+

John Gustafson also brought up the topic of the nature of error shortly before publishing "The End of Error". He now has another proposal based on variable precision arithmetic known as "posits". There was so much I wanted to say when we spoke, but I could not formulate the thoughts. I had learned a great deal while doing formal analysis of the algorithms I had put on the Am29050, Am486, and K5 processors at AMD, but when I tried to articulate this, I only stammered. I feel that I fell short, as all I could do was point at my already published work at that time on high radix online arithmetic. So this volume is my answer to John's question. Albeit it is a little late, well years late, but I hope it will still have some value.

-

There is a first edition of this book. The same concepts are described in those pages, but the story is not as well told, and no one has come full circle to say it made any sense to them. Well, one colleague, after reviewing the first edition, admitted he was bewildered by it and asked if I was proposing that we build Turing Machines. After all we are the music makers, in the music business, so to speak; only instead of being written in notes, our music is written in transistors and layout. So then, he rightfully asks, what is the proposal here? I could only point him at Mitch Alsup's book, and ponder how I could tell this story differently.

+

There is a first edition of this book. The same concepts are described in those pages, but the story is not as well told, and no one has come full circle to say it made any sense to them. Well, one colleague, after reviewing the first edition, admitted he was bewildered by it and asked if I was proposing that we build Turing Machines. After all we are the music makers, in the music business, so to speak; only instead of being written in notes, our music is written in transistors and layout. So then, he rightfully asks, what is the proposal here? I can only point him at Mitch Alsup's book, and ponder how I can tell this story differently.

There is not a hardware specification for a new proposed machine in this book. This book is not proposing to build in hardware a Turing Machine. This is an absolute. Building a TTCA machine might be interesting, and the organization for it is described in this book, but that is certainly not the proposal here. Rather this book lays the foundation for a proposal for another machine. It explains and justifies that other machine's features. But the details, the architecture, of this other machine are not found in these pages.

There is a practical aspect to this work. A software library that is of general usefulness can be found in these pages, and downloaded from GitHub. The library was first articulated in the Lisp language in the first edition of the book and released on Quicklisp. Lisp is in a sense pure, and formal statements can be made with it. Using it for the library made the library a natural small step away from the formal discussion that came before it was presented. Since that time I have written parts of the library in other languages and found it very useful. This volume presents the Python API.

-

While reaching to say something of value, I reach into foundational mathematics, a bit of number theory, and computation theory. Familiarity with those subjects will help readers read this volume, though it might not be absolutely necessary. In a sense computation theory is post Turing-Church et al. number theory. Number theory is conventionally thought of as the analysis of structures related to Natural Numbers. However, those structures are themselves entities, and a person must ask what a number is, if a number itself is not merely the structure described by Peano. It follows that when computer scientists or engineers focus their attention on numeric algorithms and circuits, they are practicing applied number theory. This in turn is a specialization of the study of algorithms in general, one where the structures are said to be numbers, and thus is part of computation theory, completing the circle.

+

A natural number is a computational structure, as described by Peano. It starts with emptiness, a zero, and is then built up by repeated application of the successor function. Because a number is a computational structure, number theory was already computation theory before Church, Turing, and their contemporaries gave the subject its name. It is a computation theory whose discussion is confined to the relationships among Peano structures, which is to say, to natural numbers. Then the activity of writing algorithms and designing circuits that relate those structures to one another, in the service of solving real problems, is applied number theory.

@@ -122,11 +122,11 @@

It is commonly thought that Turing Machines, and thus observations of nature, are limited to discrete computation, and thus there is a large domain of continuous mathematics that they can not speak about. However, the very concept of the continuous is described in discrete terms. Consider the simple function x^2 over a real field. It is considered to be a continuous function, yet it consists of discrete symbols. To take its derivative is to follow the steps of an algorithm, i.e. a program, which brings the 2 down as a multiplier and replaces the exponent with a 1, or leaves it out altogether. These are discrete steps resulting in another discrete formula, 2 x. In that the word continuous is given meaning, it becomes discrete.

-

Analysis is the bridge that leads from the natural world to the world of forms. Here analysis is the activity of asking about the properties of a program instead of running it. The program being analyzed then becomes the input data for the program doing the analysis. Turing's original paper introduced the naturalist interpretation of mathematics via the clerk at the desk, described a machine for automating the clerk's work, introduced the idea of a stored program, described analysis, and pointed out that it was possible to analyze an analyzer. And as though that was not enough, he provided a general analysis applicable to halting analyzers that proved that no universal halting analyzer can exist. (A halting analyzer is an analyzer, i.e. a program, that analyzes a given program to decide if that given program halts or not.) This does not mean that a halting analyzer can not ever be practical. For a large class of programs a halting analyzer can give an answer, and do so before a deadline. However, the proof result means that for any halting analyzer, there will be programs for which it will not be able to decide whether they halt or not, even when there is no deadline apart from 'finite number of steps'.

+

Analysis is the bridge that leads from the natural world to the world of forms. Here analysis is the activity of asking about the properties of a program instead of running it. The program being analyzed then becomes the input data for the program doing the analysis. Turing's original paper introduced the naturalist interpretation of mathematics via the clerk at the desk, described a machine for automating the clerk's work, introduced the idea of a stored program, described analysis, and pointed out that it was possible to analyze an analyzer. And as though that was not enough, he provided a general analysis applicable to halting analyzers that proved that no universal halting analyzer can exist. (A halting analyzer is an analyzer, i.e. a program, that analyzes a given program to decide if that given program halts or not.) This does not mean that a halting analyzer can not ever be practical. For a large class of programs a halting analyzer can give an answer, and do so before a deadline. However, the proof result means that for any halting analyzer, there will be programs for which it will not be able to decide whether they halt or not, even when there is no deadline apart from 'finite number of steps'.

Here then, is an interesting thing about some Turing Machine programs that do not halt. Though they can not be run to completion, they can be analyzed. Say a program prints the 's' character, then loops back, and thus prints the 's' character again and again. Such a program can not be run to completion as it never halts. However, the program can be analyzed and talked about, as of course we already know, as we are doing this very thing right now. Thus the holes in the lower level language kick the problem up to a higher level where questions are asked as to how the program behaves and what an exceptional condition means.

-

Accordingly the world of forms is not a separate realm. It is the tower of languages standing above the machine, each layer of it there to speak of the holes in the layer beneath. Those languages become separated from the machine that gave rise to them, so the base machine never need be run. At each moment, we reach the limit of what can happen in that moment, then a new moment arrives, both in stepping through programs, and in layers of abstraction.

+

Accordingly the world of forms is not a separate realm. It is the tower of languages standing above the machine, each layer of it there to speak of the holes in the layer beneath. Those languages become separated from the machine that gave rise to them, so the base machine never need be run. At each moment, we reach the limit of what can happen in that moment, then a new moment arrives, both in stepping through programs, or in layers of abstraction.

@@ -182,7 +182,7 @@

- Alan Turing used an abstraction of a computing machine, also described as a clerk working at a desk with pen and squares on paper while following a procedure, to prove that no primary 'analyzer' program can universally decide whether a second 'studied' program will halt when it is run Ibid.. An answer to this halting problem (specifically asserting "The studied machine halts" or "The studied machine does not halt") would indeed be a statement in first order logic. Thus, by showing no analyzer can universally make such a determination, Turing proved that no decider could exist for the Entscheidungsproblem. + Alan Turing used an abstraction of a computing machine, also described as a clerk working at a desk with pen and squares on paper while following a procedure, to prove that no primary analyzer program can universally decide whether a second analyzed program will halt when it is run Ibid.. An answer to this halting problem (specifically asserting "The analyzed machine halts" or "The analyzed machine does not halt") would indeed be a statement in first order logic. Thus, by showing no analyzer can universally make such a determination, Turing proved that no decider could exist for the Entscheidungsproblem.

@@ -220,7 +220,7 @@ The Turing Machine transforms mathematics into computing

- To apply his proof to the Entscheidungsproblem, Turing carried the additional burden of establishing that Hilbert and Ackermann's intuitive concept of an effective procedure was functionally equivalent to a Turing Machine program. Turing addressed this issue directly in his 1936 paper. Over the following decades, the academic community evaluated and accepted his argument, cementing what is now known as the Church Turing Thesis. This consensus supplied the necessary bridge between mathematics and modern computer science by formally equating the vague, historical notion of a human procedure with the rigorous, mechanical definition of an algorithm. + To apply his proof to the Entscheidungsproblem, Turing carried the additional burden of establishing that Hilbert and Ackermann's intuitive concept of an effective procedure was functionally equivalent to a Turing Machine program. Turing addressed this issue directly in his 1936 paper. Over the following decades, the academic community evaluated and accepted his argument, cementing what is now known as the Church-Turing Thesis. This consensus supplied the necessary bridge between mathematics and modern computer science by formally equating the vague, historical notion of a human procedure with the rigorous, mechanical definition of an algorithm.

@@ -232,7 +232,7 @@

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

@@ -245,14 +245,145 @@

- In 1967, Marvin Minsky addressed this very topic in saying: "We need not think of the machine's tape as infinite. We imagine instead that the machine begins with a finite tape, but that, whenever an end is encountered, another unit of tape is attached." Marvin L. Minsky, Computation: Finite and Infinite Machines (Englewood Cliffs: Prentice Hall, 1967), 167. In 1967, this was a perfectly natural thing to suggest, as computers utilized magnetic tape memory on manually mounted reels, and it was entirely possible for a computation to stop and request a new reel of tape to be mounted. Contemporary computer architectures do, in fact, achieve a similar effect through virtual memory. When physical RAM is depleted, the operating system pauses the active process and autonomously provisions apparent capacity by swapping memory pages out to auxiliary storage. However, this illusion of infinite tape remains bound by the physical limits of the secondary storage and the boundaries of the processor's address space. Once the available swap space is exhausted or the address space is saturated, the operating system abruptly terminates the process. + In 1967, Marvin Minsky addressed this very topic in saying: "We need not think of the machine's tape as infinite. We imagine instead that the machine begins with a finite tape, but that, whenever an end is encountered, another unit of tape is attached." Marvin L. Minsky, Computation: Finite and Infinite Machines (Englewood Cliffs: Prentice-Hall, 1967), 167. In 1967, this was a perfectly natural thing to suggest, as computers utilized magnetic tape memory on manually mounted reels, and it was entirely possible for a computation to stop and request a new reel of tape to be mounted. Contemporary computer architectures do, in fact, achieve a similar effect through virtual memory. When physical RAM is depleted, the operating system pauses the active process and autonomously provisions apparent capacity by swapping memory pages out to auxiliary storage. However, this illusion of infinite tape remains bound by the physical limits of the secondary storage and the boundaries of the processor's address space. Once the available swap space is exhausted or the address space is saturated, the operating system abruptly terminates the process.

- Like a Turing Machine, a computer architecture is an abstraction. The box sitting on a person's desk is a realization of some computer architecture. To say a Turing Machine does something is to say that the Turing Machine was analyzed and the result of the analysis is that 'something'. A computer architecture can also be analyzed. A computer architecture is said to be Turing Complete when through analysis it is determined that it can do anything that a Turing Machine can do. The practical implications for a realization of a computer architecture are that running a program will only throw an error because a) the program logic told it to, b) the program has a flaw, or c) there is a mathematical fact standing in the way of execution. It is tolerable to call a computer architecture Turing Complete if it has the built in ability to pause a program until a 'more memory' request is fulfilled. If there can be any other errors from a realization running a program, such as running out of address space or integer overflow, then the architecture is not Turing Complete. + Like a Turing Machine, a computer architecture is an abstraction. The box sitting on a person's desk is a realization of some computer architecture. To say a Turing Machine does something is to say that the Turing Machine was analyzed and the result of the analysis is that 'something'. A computer architecture can also be analyzed. A computer architecture is said to be Turing Complete when through analysis it is determined that it can do anything that a Turing Machine can do. The practical implications for a realization of a computer architecture are that running a program will only throw an error because a) the program logic told it to, b) the program has a flaw, or c) there is a mathematical fact standing in the way of execution. It is tolerable to call a computer architecture Turing Complete if it has the built-in ability to pause a program until a 'more memory' request is fulfilled. If there can be any other errors from a realization running a program, such as running out of address space or integer overflow, then the architecture is not Turing Complete.

+ + + + + The search that led to the Turing Machine + +

+ In 1893 Gottlob Frege published an axiomatic construction of mathematics from set theory. Frege's grand objective was something he called Logicism, the philosophical thesis that all of mathematics can be derived entirely from pure logic. To bridge set theory and logic, Frege defined sets using a method known as set comprehension. Under this approach, a mathematician states a logical rule or property, and any object satisfying that logical statement automatically becomes a member of the set. Because the membership of a set is determined entirely by logical rules, the resulting sets, and the mathematics built upon them, are derived directly from logic. To implement this, his specific machinery relied upon unrestricted set comprehension, formalized as Basic Law V Gottlob Frege, Grundgesetze der Arithmetik, Vol. 1 (Jena: Hermann Pohle, 1893), §20.. +

+ +

+ At a conference in Paris in 1900, David Hilbert presented a list of pressing unsolved problems in mathematics. + Second on his list was "The Compatibility of the Arithmetical Axioms." Hilbert challenged mathematicians to find a means to demonstrate that "a finite number of logical steps based upon them [axioms] can never lead to contradictory results" David Hilbert, "Mathematical Problems," trans. Mary Winston Newson, Bulletin of the American Mathematical Society 8 (1902): 437–479. This can be found at https://www.gutenberg.org/cache/epub/71655/pg71655-images.html. The MathWorld article on this subject, https://mathworld.wolfram.com/HilbertsProblems.html, explains that Hilbert presented 10 problems at the conference, though the publication shows 23 problems, and a 24th problem was later discovered among Hilbert's unpublished notes. Based on the notes of this citation, it appears the second problem is the same on all of these lists. Also note, Hilbert discusses completeness specifically as an axiom for bounding on the sets, which appears to be distinct from the question of logical completeness for an axiomatic system.. +

+ +

+ 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 fails 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 Frege's 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 1903 Russell proposed a hierarchy of types to repair this foundational vulnerability. At the base were sets of individuals, then sets based on individuals or sets of individuals, etc. This looks a lot like how types work in modern software Bertrand Russell, The Principles of Mathematics (Cambridge: Cambridge University Press, 1903), Appendix B: The Doctrine of Types.. In this manner, it is not possible to write a paradoxical set definition. Russell and Alfred North Whitehead then engineered an entirely new, massive scaffolding utilizing this type system to pursue Frege's original objective of deriving mathematics from logic, publishing their results in three volumes between 1910 and 1913 Alfred North Whitehead and Bertrand Russell, Principia Mathematica (Cambridge: Cambridge University Press, 1910–1913).. Russell's system can be cumbersome due to requiring a large construction to be assembled in place of what otherwise might have been a simple rule. +

+ +

+ In 1908 Ernst Zermelo published an alternative system designed to avoid the known paradoxical statements of the time, even though absolute consistency remained unproven. In Zermelo's set theory, a mathematician first starts with an existing set, and then applies the Axiom of Separation using definite properties to partition out subsets Ernst Zermelo, "Untersuchungen über die Grundlagen der Mengenlehre I," Mathematische Annalen 65 (1908): 261–281.. To see how this works, consider the expression \{x \mid P(x)\}. Under unrestricted comprehension, a logician is permitted to define the predicate P(x) as x ∉ x. This produces Russell's Paradox, so the set fails to be defined. In contrast, consider the same predicate, though restricted by Zermelo's Axiom of Separation over a predefined set S, written as \dot{R} = \{x \mid x ∈ S ∧ x ∉ x\}. The only thing a person needs to know about S here is that it has already been successfully defined. So let us ask, is \dot{R} in \dot{R}? If we assume \dot{R} is a member of S, evaluating the second term forces the familiar fatal loop: if \dot{R} is in \dot{R}, it shouldn't be, and if it isn't, it should be. Thus if we assume that \dot{R} is in S, then \dot{R} can not be defined, but by definition, S is defined, and thus its members are defined. As we arrived at a contradiction, the original assumption must be false, i.e. it is wrong to assume that \dot{R} is in S. As \dot{R} is definitively not a member of S, the first term of the set comprehension rule, x ∈ S, is false, and the paradox vanishes. +

+ +

+ A person might suggest defining S as the set of all definable mathematical objects, forming a universal set. However, if such a universal set S existed, the Axiom of Separation could be applied as per the proof in the prior paragraph to show \dot{R} is not in S. However, as \dot{R} is a valid, definable set, it must reside within S by the very definition of a universal set. This contradicts the premise that S contains everything. Therefore, within any system governed by the Axiom of Separation, a universal set cannot exist. +

+ +

+ The authority to remove Russell's Paradox set formulation comes from the set S. If we know its definition, then the authority comes through that definition. However, if we merely stipulate that S must be defined, then we are expressing our authority through S by declaring, "Undefined sets are not allowed." In the explanation above, it is only after discovering a set is undefined that we conclude it is not a member of S. I sometimes wonder how mathematics might have evolved had Frege simply taken that approach. We take this question up again in chapter , Computational Naturalism, and discover there is a deeper issue. +

+ +

+ Stepping back from the mechanics of set definition, a person can observe two competing approaches to establishing mathematical foundations. The first approach is constructive, building complex systems by assembling them upward from fundamental primitives. The second approach relies on islands of meaning, carving out valid spaces from the abstract void using precise rules and axioms, exactly as Zermelo did. Because both methodologies rely entirely upon a rigorous framework of deduction, logic itself serves as the essential substrate. Consequently, a complete study of the foundation of mathematics requires the examination of three distinct subjects: the primitives used for construction, the rules that bound the theoretical islands, and the underlying logic that evaluates them both. +

+ +

+ In 1928 David Hilbert and Wilhelm Ackermann published a textbook on mathematical logic, Grundzüge der theoretischen Logik David Hilbert and Wilhelm Ackermann, Grundzüge der theoretischen Logik (Berlin: Springer, 1928). This first edition has not been translated into English.. A feature of this book is its attention to procedures to follow for mechanically determining truth of statements. They called the problem solved by such a procedure the Entscheidungsproblem. In the first chapter they review the procedure for solving the Entscheidungsproblem in the propositional logic. For the first order predicate calculus they define the problem as, "Universal validity concerns the following question: How can one determine, for any given logical expression that contains no individual signs [constants], whether the expression represents a true assertion for arbitrary substitutions for the occurring variables, or not?" Ibid., 72–73.. They review some special cases with solutions, including one published earlier by Ackermann, but then throw down the gauntlet by saying, + "A general solution to the Entscheidungsproblem, regardless of whether a person considers the first or the second formulation, is not yet available." Ibid., 81. "Eine allgemeine Lösung des Entscheidungsproblems, mag man nun die erste oder die zweite Fassung nehmen, liegt bis jetzt noch nicht vor." The term Entscheidungsproblem literally translates to 'decision problem'. However, there are many types of decision problems, and later we will meet a class of Turing Machine programs called deciders, so it appears to be best to keep the original German. As we will see later Alan Turing also did this.. +

+ +

+ 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 F, 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 F that proves G." If system F 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 F 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 F 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 1936-03, Alonzo Church leveraged Gödel's foundational papers to directly answer the Entscheidungsproblem Alonzo Church, "A Note on the Entscheidungsproblem," The Journal of Symbolic Logic 1, no. 1 (March 1936): 40–41; correction, The Journal of Symbolic Logic 1, no. 3 (September 1936): 101–102., resting that argument on the unsolvability result he published the following month 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 work, Turing rushed to submit his manuscript, which was received on 1936-05-28 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, read November 12, 1936.. On 1936-08-28 he appended a proof that his mechanical architecture was mathematically equivalent to Church's lambda calculus. +

+ +

+ Alan Turing used an abstraction of a computing machine, also described as a clerk working at a desk with pen and squares on paper while following a procedure, to prove that no primary 'analyzer' program can universally decide whether a second analyzed program will halt when it is run Ibid.. An answer to this halting problem (specifically asserting "The studied machine halts" or "The studied machine does not halt") would indeed be a statement in first order logic. Thus, by showing no analyzer can universally make such a determination, Turing proved that no decider could exist for the Entscheidungsproblem. +

+ + +

+ Turing employed an enumerative diagonal argument to establish this result. A simpler proof by contradiction that is commonly used today was first published by Christopher Strachey in 1965 Christopher Strachey, "An Impossible Program," The Computer Journal 7, no. 4 (January 1965): 313. In his letter, Strachey explicitly attributed the distilled logic to an existing "well known piece of folklore among programmers.". To begin the proof, assume a person builds a perfect decider program, H(p, i), that evaluates any given program p executing with input i, then outputs 'Y' if p(i) halts, and 'N' if it does not halt. Next, a person writes a malicious program, M(x), that incorporates H as a subroutine. When M receives an input program x, it evaluates H(x, x) to determine how program x behaves when given itself as input. If H(x, x) outputs 'Y', M enters an infinite loop; if H(x, x) outputs 'N', M immediately halts. +

+ + + + + M( x ){ + if( H(x ,x) == 'Y' ) while( true ); + else if( H(x ,x) == 'N' ) return; + } + + Code . The diagonal machine that defeats a supposed halting decider + + +

+ The evil part occurs when we give program M(x) itself as input, M(M). Program M calls its subroutine and asks H(M, M) what M will do. If H outputs 'Y', it is wrong, because M loops infinitely. If H outputs 'N', then it is wrong, because M halts. The decider H is forced into an inescapable failure, proving that no universal decider can exist. +

+ +

+ 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 and Herbrand-Gödel recursive functions Stephen C. Kleene, "General Recursive Functions of Natural Numbers," Mathematische Annalen 112 (1936): 727–742.. Turing supplied the remaining leg himself, showing his machines equivalent to the lambda calculus Alan M. Turing, "Computability and λ-definability," The Journal of Symbolic Logic 2, no. 4 (December 1937): 153–163.. +

+ +

+ The academic community was thus equipped with three mathematically equivalent foundations for computation theory: recursive functions, the lambda calculus, and the Turing Machine. While all three frameworks remain active subjects of study, Turing's model is unique in providing practical intuition through the abstraction of physical machines and programs. This made it the foundation of choice for computation theory textbooks by Stephen Kleene Stephen C. Kleene, Introduction to Metamathematics (Amsterdam: North-Holland, 1952)., Martin Davis Martin Davis, Computability and Unsolvability (New York: McGraw-Hill, 1958)., and Marvin Minsky Marvin L. Minsky, Computation: Finite and Infinite Machines (Englewood Cliffs: Prentice-Hall, 1967)., leading to the modern standard presentations by authors such as John Hopcroft and Jeffrey Ullman John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation (Reading: Addison-Wesley, 1979)., as well as Harry Lewis and Christos Papadimitriou Harry R. Lewis and Christos H. Papadimitriou, Elements of the Theory of Computation (Englewood Cliffs: Prentice-Hall, 1981).. +

+ + + + + + The Turing Machine transforms mathematics into computing + +

+ To apply his proof to the Entscheidungsproblem, Turing carried the additional burden of establishing that Hilbert and Ackermann's intuitive concept of an effective procedure was functionally equivalent to a Turing Machine program. Alonzo Church had already made an identification of this kind, some months earlier, defining effective calculability by identifying it with general recursiveness, or equivalently with λ-definability in his own lambda calculus Alonzo Church, "An Unsolvable Problem of Elementary Number Theory," American Journal of Mathematics 58, no. 2 (April 1936): 356. A preliminary statement was presented to the American Mathematical Society in April 1935. The name 'Church's thesis' is due to Kleene.. What Church gave was a definition, an identification of one formal notion with another. What Turing gave was an argument: he analyzed what a person does when he computes with pencil and paper, and then built a machine to match. Church acknowledged the difference in his 1937 review of Turing's paper, the review in which he also coined the phrase 'Turing machine', granting that computability by such a machine had the advantage of "making the identification with effectiveness in the ordinary (not explicitly defined) sense evident immediately", without preliminary theorems Alonzo Church, review of A. M. Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem," The Journal of Symbolic Logic 2, no. 1 (March 1937): 42–43.. Gödel, who had found Church's proposal unsatisfactory, accepted the identification only upon seeing Turing's. +

+ +

+ Over the following decades, the academic community evaluated and accepted the argument, cementing what is now known as the Church-Turing Thesis. This consensus supplied the necessary bridge between mathematics and modern computer science by formally equating the vague, historical notion of a human procedure with the rigorous, mechanical definition of an algorithm. +

+ +

+ For Turing's purposes working on the Entscheidungsproblem, establishing functional equivalence between algorithms and Turing Machine programs was sufficient. However, when the Turing Machine serves as a foundational model for computation theory, we are led to ask another question: whether the Turing Machine is representative of modern architectures, and to the extent it differs, how this would affect the applicability of computation theoretic results. +

+ +

+ In reading Alan Turing's 1936 paper, it is striking how modern the text feels, specifically because he discusses algorithms, stored programs, and the mechanical limits of computation. While his contemporaries largely built purely mathematical and logical frameworks, Turing uniquely tied computation theory directly to the abstraction of machines executing stored programs. Because physical hardware capable of executing stored programs had not yet been invented, this explicit architectural grounding makes Turing's work remarkably prescient. Still, Turing could not formally connect the Turing Machine to modern architectures, simply because those architectures did not yet exist. Here, by modern, I refer to architectures utilizing random-access system memory, dedicated instruction fetch streams with dynamic branching, and discrete processing units. Though Charles Babbage's Analytical Engine, first described in 1837, touched on these concepts, they would wait until the 1940s to reemerge. The practical engineering context of 1936 was limited to calculating machines programmed via patch panels. Hence, for example, there is no explanation in his paper as to why a von Neumann architecture machine (1945) running a program would exhibit the computation theoretic results derived from a computation theory based on the Turing Machine (1936). +

+ +

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

+ + +

+ To complete the Turing Machine story, then, we will transform the Turing Machine into a modern architecture in a stepwise fashion, while ensuring that at each step the modifications are inconsequential to computation theoretic existence proofs and complexity class results. We do run into some problems, so the architecture we derive will be a little different from those we currently build. Though the point here is that we could build it. +

+ +

+ The infinite tape is not as large a hurdle as it might seem at first. For computational problems, the Turing Machine halts in a finite number of steps. Because the Turing Machine is limited to stepping the read/write head over one cell per machine execution step, only a finite amount of tape is ever used. But for a given computation, how much tape is that? Resolving this by assuming more tape is simply attached when needed is analogous to cheating in a 'guess the bigger number' game by declaring, "My number is always one bigger than the given number, so I will tell you my guess after you state your number." Some mathematicians suggest that what is meant by infinity is precisely a rule of this sort. For engineers building physical hardware, however, to state that a resource starts finite and expands incrementally over time is a very different proposition from being asked to install infinite memory on a machine in the first place. +

+ +

+ In 1967, Marvin Minsky addressed this very topic, saying: "We need not think of the machine's tape as infinite. We imagine instead that the machine begins with a finite tape, but that, whenever an end is encountered, another unit of tape is attached." Marvin L. Minsky, Computation: Finite and Infinite Machines (Englewood Cliffs: Prentice-Hall, 1967), 167. In 1967, this was a perfectly natural thing to suggest, as computers utilized magnetic tape memory on manually mounted reels, and it was entirely possible for a computation to stop and request a new reel of tape to be mounted. Contemporary computer architectures do, in fact, achieve a similar effect through virtual memory. When physical RAM is depleted, the operating system pauses the active process and autonomously provisions apparent capacity by swapping memory pages out to auxiliary storage. However, this illusion of infinite tape remains bound by the physical limits of the secondary storage and the boundaries of the processor's address space. Once the available swap space is exhausted or the address space is saturated, the operating system abruptly terminates the process. +

+ +

+ Like a Turing Machine, a computer architecture is an abstraction. The box sitting on a person's desk is a realization of some computer architecture. To say a Turing Machine does something is to say that the Turing Machine was analyzed and the result of the analysis is that 'something'. A computer architecture can also be analyzed. A computer architecture is said to be Turing Complete when, through analysis, it is determined that it can do anything that a Turing Machine can do. The practical implication for a realization of such an architecture is that running a program will fault only because a) the program logic told it to, b) the program has a flaw, or c) there is a mathematical fact standing in the way of execution. It is tolerable to call a computer architecture Turing Complete if it has the built-in ability to pause a program until a 'more memory' request is fulfilled, as that is a limit of the realization rather than of the architecture. However, if the architecture itself stipulates a bound that a program can reach, such as a fixed address width or a fixed integer width, then every realization of it must fail on some program that a Turing Machine would carry to completion, and the architecture is not Turing Complete. +

+ + + + + @@ -370,7 +501,7 @@

- We call a program that examines another program so as to deduce properties of its results an analyzer. The program or machine definition being subjected to this evaluation is called the studied program or studied machine. + We call a program that examines another program so as to deduce properties of its results an analyzer. The program or machine definition being subjected to this evaluation is called the analyzed program or analyzed machine.

@@ -907,9 +1038,9 @@

We therefore keep both words, and give each one job. Emptiness is a property, and a property belongs to a container: a cell of machine A either holds a symbol or it does not. SP is a symbol, and a symbol belongs to an alphabet: a cell of machine B always holds one, and SP is what it holds where a cell of machine A would have been empty. Machine B has no empty cells at all, only cells holding SP. Where this book speaks of emptiness it means the property, and where it writes SP it means the symbol standing in for it.

-

There is more to consider about the former blank, former empty, now SP symbol. Computational theorists often describe a two-step process. First, a Turing Machine writes a string to be studied onto a tape initially filled with all SP symbols; second, the tape is moved to another Turing Machine whose purpose is to recognize a property of the string being studied. In this process, a tape is used as a communication medium, so it follows that communication theory can be applied to this messaging scenario. Messages sent on a channel must be formatted so they can be placed on the channel and later recovered. The specification for such structuring is called a communication protocol. The protocol implies a higher authority, as both the sender and the receiver must have knowledge of the same designed-in protocol. In a sense, a protocol is the meta-message sent before the message itself.

+

There is more to consider about the former blank, former empty, now SP symbol. Computational theorists often describe a two-step process. First, a Turing Machine writes a string to be analyzed onto a tape initially filled with all SP symbols; second, the tape is moved to another Turing Machine whose purpose is to recognize a property of the string being analyzed. In this process, a tape is used as a communication medium, so it follows that communication theory can be applied to this messaging scenario. Messages sent on a channel must be formatted so they can be placed on the channel and later recovered. The specification for such structuring is called a communication protocol. The protocol implies a higher authority, as both the sender and the receiver must have knowledge of the same designed-in protocol. In a sense, a protocol is the meta-message sent before the message itself.

-

The intention of the later innovation of placing the SP symbol in Γ but not in Σ appears to be that of making the SP symbol serve additional duty: firstly as a default value for a cell that has never been written to, secondly to effect erasure, and now thirdly as a control component of a communications protocol. Accordingly then, this protocol was designed by mathematicians with a specific goal. They intended to make it impossible for programmers to send 'to be studied' string messages that cannot always be recovered by a receiving recognizer Turing Machine. In short, the SP symbol also serves as an in-band EOM (end of message) symbol.

+

The intention of the later innovation of placing the SP symbol in Γ but not in Σ appears to be that of making the SP symbol serve additional duty: firstly as a default value for a cell that has never been written to, secondly to effect erasure, and now thirdly as a control component of a communications protocol. Accordingly then, this protocol was designed by mathematicians with a specific goal. They intended to make it impossible for programmers to send 'to be analyzed' string messages that cannot always be recovered by a receiving recognizer Turing Machine. In short, the SP symbol also serves as an in-band EOM (end of message) symbol.

Firstly note that excluding SP from Σ does not prevent a Turing machine from writing SP to a tape to be used as a message. If a message writing machine wants to write an SP to the tape, it merely writes a different symbol then erases it.

@@ -942,7 +1073,7 @@

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.

+

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

@@ -959,7 +1090,7 @@

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.

+

Recall the suggestion earlier in this section that "perhaps an algorithm could be analyzed 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.

@@ -3466,7 +3597,7 @@ Now suppose defining a Turing Machine that initially has the head on the leftmos

- As an analyzer does not run the machine being studied, it is not required to be a machine that halts. Suppose we have a machine that produces an infinite sequence of digits to a tape without halting. A limit analyzer could examine that machine and, in some cases, determine if it has asymptotic behavior. For example, recognizing that appending a binary fractional sequence of 0.1111... indefinitely evaluates in the limit to 1.0. In this manner, the use of analyzers facilitates using computation theory for deriving higher order mathematics. + As an analyzer does not run the machine being analyzed, it is not required to be a machine that halts. Suppose we have a machine that produces an infinite sequence of digits to a tape without halting. A limit analyzer could examine that machine and, in some cases, determine if it has asymptotic behavior. For example, recognizing that appending a binary fractional sequence of 0.1111... indefinitely evaluates in the limit to 1.0. In this manner, the use of analyzers facilitates using computation theory for deriving higher order mathematics.

-- 2.20.1