From be0652881ecaed7f97c766786af16e82975c4e41 Mon Sep 17 00:00:00 2001 From: Thomas Walker Lynch Date: Mon, 10 Aug 2026 14:18:24 +0000 Subject: [PATCH] descent presentation of first few chapters --- document/book/TM-2026.html | 47 +++++++++++++++++++++----------------- 1 file changed, 26 insertions(+), 21 deletions(-) diff --git a/document/book/TM-2026.html b/document/book/TM-2026.html index 447ff2a..991eed8 100644 --- a/document/book/TM-2026.html +++ b/document/book/TM-2026.html @@ -32,17 +32,18 @@ + Exordium -

Experiencing the "Computer Arithmetic" community was indeed a Movable Feast.

+

My colleagues in computer arithmetic work tirelessly to confirm Schopenhauer's thesis, so I am left with only the easy problems no one else wants.

-

This book operates at the intersection of number theory, numerical analysis, and computation theory.

+

This book would not exist without the encouragement of my wife. While cousins brought their husbands to family events, she sat by herself as I remained home in the company of computation theory. She is a beautiful, charming woman. I count myself fortunate not to be wearing horns.

-

The RT Iterator Library work was sponsored by Reasoning Technology Inc. This was a first step in the creation of a computer language for increased computer security and behavioral introspection.

+

So perhaps we can discuss this one. Turing began with a Naturalist model, a clerk at a desk, yet the machine he described cannot be built. What follows completes the foundation he began. The subject of Computational Naturalism lies at the intersection of number theory, numerical analysis, computation theory, and computer architecture.

-

This book would not exist without the encouragement of my wife. While cousins brought their husbands to family events, she sat by herself as I remained home cavorting with Computation Theory. She is a beautiful, charming young woman. I am fortunate not to have grown horns on my head.

+

The RT Iterator Library was developed at Reasoning Technology Inc. It is a first step toward a computer language for increased security and behavioral introspection.

 @@ -126,13 +127,13 @@

The IEEE Std 754 floating-point standard equips the numerical analyst with the tools to design platform independent algorithms with predictable numerical behavior. Though the principal founder of the standard did commit one sin. He allowed for the expanded precision of the intermediate calculations on the Intel 8087 as a matter of backwards compatibility. He apparently succumbed to that final temptation because he had been part of that project. Consequently, the standard does not provide universal platform independence.

-

One of the features of the standard is its support for a limiting arithmetic. If a computation divides by zero, an infinity flag can be substituted as a result. Then if the reciprocal is taken, zero returns. Zero and infinity can be signed, indicating the directions of the overflow and underflow. The substitution flags allow the program doing the computation to continue after what otherwise would be an interrupt exception. However, the intention is to give the numeric analyst tools, not to allow for programs that experience exception conditions to give right answers anyway. In fact, the error, i.e. the distance to the ideal result, most commonly increases rapidly after an exception indicating substitution enters the computation.

+

One of the features of the standard is its support for a limiting arithmetic. If a computation divides by zero, an infinity flag can be substituted as a result. Then if the reciprocal is taken, zero returns. Zero and infinity can be signed, indicating the directions of the overflow and underflow. The substitution flags allow the program doing the computation to continue after what otherwise would be an interrupt exception. However, the intention is to give the numeric analyst tools, not to allow for programs that experience exception conditions to give right answers anyway. In fact, the error, i.e. the distance to the exact result, most commonly increases rapidly after an exception indicating substitution enters the computation.

-

Bill Kahan was said principal founder, and the standard happened because he is a staunch, sometimes overbearing, advocate of predictable numerical operations. In my experience in using the standard as a numerical analyst I was struck by how difficult it was to design accurate computations even when given predictable operations. It seems that another layer was needed for helping out the compiler, and I worked on this, and created an manual/automated process for the development of the transcendental functions by my numerics team at AMD. Then I arranged to meet Bill to discuss it.

+

Bill Kahan was said principal founder, and the standard happened because he is a staunch, sometimes overbearing, advocate of predictable numerical operations. In my experience in using the standard as a numerical analyst I was struck by how difficult it was to design accurate computations even when given predictable operations. It seems that another layer was needed for helping out the compiler, and I worked on this, and created a manual/automated process for the development of the transcendental functions by my numerics team at AMD. Then I arranged to meet Bill to discuss it.

We had lunch in Berkeley, and I stressed the point that rather than stopping with operations and limiting arithmetic, that an exception during an operation was merely an excuse to do more computation. Clearly the concept resonated with Bill, as he stopped short after I said it. Also, not long after, Bill gave an interview to Dr. Dobb'sJack Woehr, "A Conversation with William Kahan," Dr. Dobb's Journal, November 1997, archived at https://jacobfilipp.com/DrDobbs/articles/DDJ/1997/9711/9711a/9711a.htm. A related interview, "An Interview with the Old Man of Floating-Point," February 20, 1998, is sometimes cited alongside it. and there at the top he was quoted repeating my words, "Exceptions are opportunities for extra computation."

-

Occasionally a student will come to me to share a great new discovery, that isn't so great, and isn't so new. Almost always the idea is not yet mature. Understandably a student's ideas are sometimes those of a person making observations while not realizing he is on a well trodden path. It is human nature to come to the conclusion that the unknown does not exist. This is not to say that professors do not harvest new ideas from students. My advice to such a student with such a discovery, is to first publish it, perhaps file a provisional patent, or at least write up and send it in an email rather than walking up and telling me about it, and then watch as the concept evolves over time and think what caused that evolution. Hence, the Lynch-Swartlander adder patent was filed in my name and that names of AMD design team. Also the original publication of High Radix Online Arithmetic at a small conference is in my name.

+

Occasionally a student will come to me to share a great new discovery, that isn't so great, and isn't so new. Almost always the idea is not yet mature. Understandably a student's ideas are sometimes those of a person making observations while not realizing he is on a well trodden path. It is human nature to come to the conclusion that the unknown does not exist. This is not to say that professors do not harvest new ideas from students. My advice to such a student with such a discovery, is to first publish it, perhaps file a provisional patent, or at least write up and send it in an email rather than walking up and telling me about it, and then watch as the concept evolves over time and think what caused that evolution. Of course I was also a student. Hence, the Lynch-Swartlander adder patent was filed in my name (and the names of AMD design team, after all there was a cash reward for those). Also the original publication of High Radix Online Arithmetic at a small conference is in my name.

Credit and showing proper respect to both students and the hard work that got professors tenure is not as easy of a thing to do as it might seem. I was once asked to present a student's work at a conference in France, and was so anxious to talk about my own work so as to attract funding, that I nearly left the summary of hers out. I remain embarrassed over this to this day. Though I am sure her colleagues properly appreciate her work. Worse mistakes than this have been made. And what could I possibly have been thinking, a small conference on applied number theory in France is more than a world apart from a Silicon Valley tech meeting.

@@ -191,8 +192,7 @@ - - + The search that led to the Turing Machine @@ -271,7 +271,17 @@

- 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 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 became 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 as a Natural object + +

+ The computational naturalism thesis is that mathematics is a catalog of Turing Machine observations. For the Turing Machine to serve in that account, three conditions must hold. Although the Turing Machine is not realizable, the RT Machine variation defined in chapter is. The second is that Turing Machine programs encompass algorithms, so that an observation of the machine is an observation of mathematics. That condition holds, and how it came to be established is the subject of the two paragraphs that follow. The third is that a modern computer can do whatever a Turing Machine can do, so that it too is a Natural object embodying mathematics. Formally, the differences between a modern architecture and the Turing Machine must be computation theoretic inconsequential, a property defined in chapter , Computation theoretic consequentiality. The first and third conditions are where the difficulty lies, and the rest of this chapter lays it out.

@@ -285,21 +295,16 @@ 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.

- - - - - The Turing Machine measured against modern architecture -

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

+ So the second condition holds. Algorithms and Turing Machine programs are the same thing, and an observation of the machine is therefore an observation of mathematics. The third condition is harder, and it was not a question Turing was in a position to ask. +

- 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. Charles Babbage had reached several of these ideas a century earlier with the Analytical Engine, and the accounts of it were in print and on library shelves in 1936, though Turing's paper does not mention themThe question is raised by Robin Gandy in his preface to the paper in Turing's collected works. Gandy argues that Turing cannot have read Babbage, on the ground that he would have said so had he done so. He allows that Turing might have seen the article on calculating machines in the eleventh edition of the Encyclopaedia Britannica, a copy of which Turing inherited from his father and consulted in later years, but observes that its treatment of the Analytical Engine is brief and dismissive, and would not have suggested to a reader that Babbage had conceived a universal machine. R. O. Gandy, preface to "On Computable Numbers, with an Application to the Entscheidungsproblem," in R. O. Gandy and C. E. M. Yates, eds., Mathematical Logic, The Collected Works of A. M. Turing (Amsterdam: North-Holland, 2001). Gandy directs the reader to his own study of the period for the background of ideas and for the contributions of Hilbert's school, of Church and his students, and of Post: R. O. Gandy, "The Confluence of Ideas in 1936," in Rolf Herken, ed., The Universal Turing Machine: A Half-Century Survey (Oxford: Oxford University Press, 1988), 55–111. The reasoning is an argument from silence. It moves from an absence in the text to an absence in the reading, and nothing short of a borrowing record or a letter could tell against it. What can be said is that the material was available. Menabrea's account, in the Countess of Lovelace's translation and with her notes, had been in print since 1843 in Taylor's Scientific Memoirs, and Babbage's own chapter on the engine had been in print since 1864. Babbage had held the Lucasian chair at Cambridge, where Turing was a Fellow of King's. Turing did not read these things, if he did not, by choice or by accident, and not for want of access. There is something peculiar in the shape of the defence. It secures Turing's independence by crediting him with a gap in his reading, which is an odd currency to pay originality in, and the transaction is made on Turing's behalf rather than by him. Gandy was Turing's student, his friend, and his literary executor, which is worth knowing when weighing the argument, though it is not an answer to it. It is also worth noting what he said once the question was live. By 1950 Turing discusses the Analytical Engine at some length, knows that Babbage held the Lucasian chair from 1828 to 1839, and is willing to call the engine a universal digital computer. Yet he reaches Lovelace's memoir there by way of Douglas Hartree's 1949 book, citing Hartree's page for the quotation rather than the memoir itself. That is consistent with his never having gone to the primary source, though it settles nothing about 1936. Alan M. Turing, "Computing Machinery and Intelligence," Mind 59, no. 236 (October 1950): 433–460, the Analytical Engine at 439 and Lovelace's objection at 450; Douglas R. Hartree, Calculating Instruments and Machines (Urbana: University of Illinois Press, 1949), 70; L. F. Menabrea, "Sketch of the Analytical Engine Invented by Charles Babbage," trans. Ada Augusta, Countess of Lovelace, with translator's notes, in Richard Taylor, ed., Scientific Memoirs, vol. 3 (London: Richard and John E. Taylor, 1843), 666–731; Charles Babbage, Passages from the Life of a Philosopher (London: Longman, Green, 1864), chap. VIII. The last consideration is the one that matters here, and it cuts the question down. Babbage would have been of no use to Turing. The Entscheidungsproblem needed a machine whose entire repertoire of behaviour could be catalogued and then diagonalized over. The Analytical Engine has far too much architecture for that. Reading it would have been a distraction rather than a shortcut, and a historian who establishes that Turing did read it will not thereby have taken anything away from him.. Whether he had read them is a question that deserves some care, and it is taken up in the note. The answer changes less than one might expect, because Babbage was designing a machine to compute with, whereas Turing needed a machine plain enough that everything it could ever do could be catalogued and reasoned over. The poverty of the Turing Machine is deliberate. Later in this chapter that same poverty returns as the machine's central defect when it is asked to serve as an architecture. The practical engineering context of 1936 was in any case 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). + 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.

- 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. That question is addressed over the chapters that follow, and the answer arrived at is that neither side is quite fit to be compared to the other as it stands. + 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. Charles Babbage had reached several of these ideas a century earlier with the Analytical Engine, but no line runs forward from it to 1936; the engine was never built, and the ideas waited until the 1940s to reemergeAccounts of the Analytical Engine were in print and on library shelves in 1936, and Turing's paper does not mention them. The question of whether he had read them is raised by Robin Gandy in his preface to the paper in Turing's collected works. Gandy argues that Turing cannot have read Babbage, on the ground that he would have said so had he done so. He allows that Turing might have seen the article on calculating machines in the eleventh edition of the Encyclopaedia Britannica, a copy of which Turing inherited from his father and consulted in later years, but observes that its treatment of the Analytical Engine is brief and dismissive, and would not have suggested to a reader that Babbage had conceived a universal machine. R. O. Gandy, preface to "On Computable Numbers, with an Application to the Entscheidungsproblem," in R. O. Gandy and C. E. M. Yates, eds., Mathematical Logic, The Collected Works of A. M. Turing (Amsterdam: North-Holland, 2001). Gandy directs the reader to his own study of the period for the background of ideas and for the contributions of Hilbert's school, of Church and his students, and of Post: R. O. Gandy, "The Confluence of Ideas in 1936," in Rolf Herken, ed., The Universal Turing Machine: A Half-Century Survey (Oxford: Oxford University Press, 1988), 55–111. The reasoning is an argument from silence. It moves from an absence in the text to an absence in the reading, and nothing short of a borrowing record or a letter could tell against it. What can be said is that the material was available. Menabrea's account, in the Countess of Lovelace's translation and with her notes, had been in print since 1843 in Taylor's Scientific Memoirs, and Babbage's own chapter on the engine had been in print since 1864. Babbage had held the Lucasian chair at Cambridge, where Turing was a Fellow of King's. Turing did not read these things, if he did not, by choice or by accident, and not for want of access. There is something peculiar in the shape of the defence. It secures Turing's independence by crediting him with a gap in his reading, which is an odd currency to pay originality in, and the transaction is made on Turing's behalf rather than by him. Gandy was Turing's student, his friend, and his literary executor, which is worth knowing when weighing the argument, though it is not an answer to it. It is also worth noting what he said once the question was live. By 1950 Turing discusses the Analytical Engine at some length, knows that Babbage held the Lucasian chair from 1828 to 1839, and is willing to call the engine a universal digital computer. Yet he reaches Lovelace's memoir there by way of Douglas Hartree's 1949 book, citing Hartree's page for the quotation rather than the memoir itself. That is consistent with his never having gone to the primary source, though it settles nothing about 1936. Alan M. Turing, "Computing Machinery and Intelligence," Mind 59, no. 236 (October 1950): 433–460, the Analytical Engine at 439 and Lovelace's objection at 450; Douglas R. Hartree, Calculating Instruments and Machines (Urbana: University of Illinois Press, 1949), 70; L. F. Menabrea, "Sketch of the Analytical Engine Invented by Charles Babbage," trans. Ada Augusta, Countess of Lovelace, with translator's notes, in Richard Taylor, ed., Scientific Memoirs, vol. 3 (London: Richard and John E. Taylor, 1843), 666–731; Charles Babbage, Passages from the Life of a Philosopher (London: Longman, Green, 1864), chap. VIII. The last consideration is the one that matters here, and it cuts the question down. Babbage would have been of no use to Turing. The Entscheidungsproblem needed a machine whose entire repertoire of behaviour could be catalogued and then diagonalized over. The Analytical Engine has far too much architecture for that. Reading it would have been a distraction rather than a shortcut, and a historian who establishes that Turing did read it will not thereby have taken anything away from him.. 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).

@@ -323,7 +328,7 @@

- 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. The transformation does not run in one direction only. On the Turing Machine side, the controller has to stop being used as memory. On the modern side, the fixed widths an architecture stipulates, those of an address and of an Integer, are what have to give way. The two meet in the middle, and the machine we arrive at is less strange than that might suggest. It separates the control path from the data path; it holds an instruction table; and it has a small register file. It looks modern. The differences from what we currently build are real but few, and the point of the exercise is that we could build it. + 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. The transformation does not run in one direction only. On the Turing Machine side, the controller has to stop being used as memory. On the modern side, the fixed widths an architecture stipulates, those of an address and of an Integer, are what have to give way. The two meet in the middle, and the machine we arrive at is less strange than that might suggest. It separates the control path from the data path; it holds an instruction table; and it has a small register file. It looks modern. The differences from what we currently build are real but few, and the point of the exercise is that we could build it. Building it satisfies the first condition. Holding every modification to one that is computation theoretic inconsequential satisfies the third. The two are met together, and they are met by the same machine.

@@ -434,7 +439,7 @@ - + Computation theoretic consequentiality

-- 2.20.1