Charles Petzold

For quite awhile I assumed that my forthcoming book The Annotated Turing: A Guided Tour through Alan Turing's Historic Paper on Computability and the Turing Machine would not even mention Dutch mathematician Luitzen Egbertus Jan Brouwer (1881 – 1966). I was seriously mistaken.

Brouwer played a major role in the debates in the early decades of the last century involving the foundations of mathematics. Three distinct approaches emerged, called logicism, formalism, and intuitionism.

Logicism is mostly closely associated with Alfred North Whitehead and Bertrand Russell's three-volume Principia Mathematica, which carried on the work of Gottlob Frege in attempting to derive all of mathematics from basic principles of logic. Formalism is mostly closely associated with David Hilbert, who tried to treat mathematics in a strictly formal manner as the manipulation of symbols. Most important to Hilbert were the establishment of certain metamathematical characteristics of axiomatic systems, such as consistency, completeness, and decidability. Although logicism and formalism took different approaches to mathematics, it might have been possible for Russell and Hilbert to have combined them into a single coherent mathematical strategy had not the Great War intervened at precisely the crucial time.

In opposition to both logicism and formalism — and much less likely to be reconciled — was the philosophy of mathematics called intuitionism by L.E.J. Brouwer to describe his idea of how mathematical entities are formulated by the mind. Using symbols on paper to communicate mathematics is to the formalist the whole point, but to the intuitionist a necessary evil.

Both logicism and formalism relied a great deal on Georg Cantor's set theory and, to a certain extent, his theory of transfinite numbers, and this is one area where Brouwer parted company. Brouwer certainly accepted the difference between the enumerable integers and the non-enumerable real numbers, but because of that very difference he refused to accept sets of non-enumerable objects. The set of all real numbers must be prohibited specifically because there is no way to enumerate or generate the members of that set. Much of Cantor’s theory of transfinite numbers is therefore simply ‘‘without meaning to the intuitionist.’’ (‘‘Intuitionism and Formalism,’’ Bulletin of the American Mathematical Society, Vol. 20 (1913))

Brouwer also felt that certain concepts that had validity in the realm of finite sets had been foolishly and dangerously extended to infinite sets. One concept is particular is the law of the excluded middle — either something does or does not have a particular property. This is not so for infinite sets, and Brouwer used as an example a series whose convergence depends on a certain unknown pattern appearing in the infinite digits of π.

Although I certainly knew about Brouwer when working on the early chapters of my book, he didn't seem quite relevant. The early chapters provide the background necessary for reading Turing's paper "On Computable Numbers, with an Application to the Entscheidungsproblem." This background included a major discussion of Georg Cantor's work in Chapter 2, appearances of Gottlob Frege and Bertrand Russell in Chapter 3, and of course David Hilbert, also in Chapter 3.

Turing obviously knew about Cantor's two proofs of the non-enumerability of real numbers, for he alludes to those in Section 8 of his paper. (I don't think Turing had access to Cantor's papers because he references E. W. Hobson's book The Theory of Functions of a Real Variable and the Theory of Fourier's Series for the first of the two proofs.) Turing also refers to David Hilbert and Wilhelm Ackermann's Grundzüge der Theoretischen Logik — this is the book that introduced the Entschiedungsproblem for first-order logic and which also posed the completeness problem that Gödel tackled — and the first volume of David Hilbert and Paul Bernays' Grundlagen der Mathematik.

Despite Brouwer's important historical role in the mathematical movements of the early twentieth century, he didn't seem to play a significant part in the background to Turing's paper. I felt that a discussion of Brouwer in Chapter 3 would have been more of a distraction than anything else. Besides, other popular histories of the period — for example Martin Davis's wonderful The Universal Computer: The Road from Leibniz to Turing (W. W. Norton, 2000), published in paperback under the title Engines of Logic: Mathematicians and the Origin of the Computer — discussed Brouwer and his role in the mathematical controversies of the 1920's.

I suspect I was also partly influenced by the rather dismissive tone towards Brouwer taken by I. Gratten-Guinness in The Search for Mathematical Roots, 1870-1940: Logics, Set Theories and the Foundations of Mathematics from Cantor through Russell to Gödel (Princeton University Press, 2000), page 480: "The origins of Brouwer's philosophy lie partly in poor understanding of certain mystical texts, and partly on a naive reading of Kant's views on the place of intuition."

I deliberately excluded Brouwer from my book, and in the draft that I circulated to about a dozen friends in the summer of 2005, the Introduction read "I have also been selective in the historical background I’ve provided. I discuss Cantor but not Kronecker, Hilbert but not Brouwer. Although I’ve streamlined the history, I have tried my best not to distort it." I was freely admitting that I was presenting in the book what Herbert Butterfield famously called a "Whig interpretation of history" — a description of the past that always seems to be leading inexorably towards the glorious present.

I felt entirely justified in doing this because in Chapters 2 and 3 I tried to present the mathematical background that would have been familiar to Turing when he wrote his paper. I believed then — and I still believe — that Turing had at most a negligible knowledge of Brouwer's work at the time he wrote the draft of his paper that he submitted to the London Mathematical Society in May 1936.

However, Turing's paper was not actually quite finished at that time.

Shortly after Turing submitted his paper, he found out that he had been scooped by Alonzo Church at Princeton, who had just published a paper that proved the Entscheidungsproblem had no solution. Normally that would have meant that Turing's paper would not be published, but everyone agreed that the publication of Turing's paper was justified by his unique approach involving the imaginary computing machine soon called (by Church himself) the "Turing machine."

Because Church's paper had already been published, Turing needed to add an Appendix to his own paper showing how his approach and Church's approach were equivalent. Church had used a mathematical tool he had developed called the lambda calculus, which subsequently had an important influence on computing, particularly functional programming languages and lambda expressions. I went back to Church's original papers, and those of his students Stephen Kleene and J. Barkley Rosser — the same papers that Turing must have studied during the summer of 1936 to write his Appendix. Turing's Appendix (with my background on the lambda calculus and helpful explanations) appears in Chapter 15 of my book.

About a year after Turing's original paper was published in 1936, Turing published a three-page paper entitled "On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction," hereafter referred to as Correction. For at least the sake of completeness, I wanted the Correction to be part of my book, but I didn't see a big role for it. Most of the stuff in the first half of the Correction paper indicated formal errors — including a shockingly inadequate formalization of the natural numbers in first-order logic — that I had already incorporated into my earlier chapters.

I thought I'd be able to deal with the Correction paper in the same chapter as the Appendix. Somehow I had neglected dealing with the full implications of the second half of the Correction paper, or perhaps it didn't seem all that significant at the time, or maybe I was in serious denial. When I finally focused on this material, I was quite surprised. The section begins by indicating a problem with the way Turing originally described computable numbers way back in the beginning of the paper. Under Turing's definitions, a "computable sequence" is a string of 0's and 1's generated by a machine. A "computable number" is the binary number you get when you put a period in front of this computable sequence, or when you add or subtract any integer from this binary number.

That sounds very simple and straightforward, and yet in the Correction paper Turing indicates this definition is problematic, for one reason because a machine cannot be defined to compute the Euler constant. I quickly figured out that the particular Euler constant that Turing is referring to is not the famous e, the base of natural logarithms, but the slightly less famous γ, equal to approximately 0.57721..., often called the Euler-Mascheroni constant, and the subject of recent book by Julian Havil, Gamma: Exploring Euler's Constant (Princeton University Press, 2003).

But why was Turing asserting that one of his machines can't calculate γ? I knew people had written computer programs to calculate the digits of γ, so why couldn't a Turing Machine also calculate it? This question bounced around in my head for weeks — fortunately I was able to do other work at the same time! — before I grasped the special problem that γ presented to Turing Machines.

The remainder of the second half of Turing's Correction paper was equally mysterious, but is clarified by a tiny footnote on the last page:

This use of overlapping intervals for the definition real numbers is due originally to Brouwer.

There it is: The explicit Brouwer connection. I mentioned earlier that I didn't think Turing had much familiarity with Brouwer's work at the time he wrote the draft of his paper that he submitted to the London Mathematical Society in May 1936, so what changed in the year that passed before Turing wrote the three-page Correction?

What changed is that Turing went to Princeton and got his doctorate under Alonzo Church, and there he met people who were familiar with Brouwer's work. Church himself had visited Brouwer in Amsterdam several years earlier, and was sympathetic to intuitionist mathematics. So too was Stephen Kleene, who later co-authored a book about intuitionism and whose article ‘‘Origins of Recursive Function Theory,’’ in the Annals of the History of Computing, Vol. 3, No. 1 (Jan. 1981) contains a photograph of Brouwer visiting Kleene in Madison, Wisconsin. So too was Hermann Weyl who was at the Institute for Advanced Studies at the time Turing was in Princeton. These were some of the possible influences that caused Turing to question and rethink this particular aspect of his paper.

I was curious to read what others had written about the connections between Brower's mathematics and Turing's computable numbers, but I couldn't find much of anything.

The more I read about Brouwer — an overview by Walter P. van Stigt included in Paolo Mancosu's From Brouwer to Hilbert: The Debate on the Foundations of Mathematics in the 1920s (Oxford University Press, 1998), Mark van Atten's short but illuminating text On Brouwer (Wadsworth, 2004), the paper ‘‘Brouwer and Weyl: The Phenomenology and Mathematics of the Intuitive Continuum’’ by Mark van Atten, Dirk van Dalen, and Richard Tieszen in Philosophia Mathematica, Vol. 10, No. 2 (2002) — and the more I read of Brouwer's own papers — about ten in From Brouwer to Hilbert, and a few more in those indispensable anthologies Jean van Heijenoort's From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931 (Harvard University Press, 1967) and William Ewald's From Kant to Hilbert: A Source Book in the Foundations of Mathematics (Oxford University Press, 1996) — the more interested I got. I found Brouwer to be a fascinating personality, and I began wishing I had some excuse to plunge into the two-volume biography by Dirk van Dalen and explore the Collected Works. (My own book would have been much delayed as a result!)

Although I'm sure that Brouwer's concepts of real numbers didn't influence Turing's description of machines that generate real numbers, the connections are quite startling.

To Brouwer, the digits of π do not exist until they are computed, and a real number is not something that is ever completely calculated. It is always an uncompleted process that occurs over time. (In constrast, to a mathematical Platonist, π is an actual complete number.) This is precisely the way Turing Machines compute real numbers. The machines never finish, and each step requires a finite period of time in that process.

Brouwer also developed a completely original approach to the definition of the real-number continuum, always problematic because of its schizophrenic nature: seemingly smooth and continuous, but at the same time a collection of discrete (but non-enumerable) points. Brouwer's solution involved something he called "choice sequences" that never converge but always maintain a type of finite "halo" around a particular real. The choice sequences seemed to me quite similar to the progressive digits computed by a Turing Machine.

The primary purpose of Turing's paper — to show that can be no general decision procedure for first-order logic, i.e., that there is no general way to determine whether a specific statement in logic is provable or not — was, along with Gödel Incompleteness Theorem, one of the death knells for Hilbert's formalist program. Yet, Turing's paper also strengthened Brouwer's arguments about the real numbers.

When we set a Turing Machine going to compute the digits of some real number, it is not possible to predict what will happen, or to determine if the machine ever prints a particular digit. By extension, it is also impossible to determine if a the machine will ever print a particular pattern of digits.

Suppose the opposite of what Turing proved turned out to be true. Suppose we really could develop finite algorithms that analyze Turing Machines and determine what they might or might not do. Suppose we had a Turing Machine that computed the digits of π, and we really were able to analyze this machine with finite algorithms to determine if it will ever print particular patterns of digits. We would then be justified in saying that all the digits of π really do exist in a Platonic sense, because we'd be able to extract information about those infinite digits in a finite period of time.

But no such algorithms exist. We still need to calculate the digits to know what they are. Because of the finite resources of the universe, only a finite number of digits of π will ever be computed.

This last section of Turing's three-page Correction was for me initially the most mysterious passage of his entire paper. As I battled my way through my initial confusion (always a fun process because that's how I learn new stuff) I was forced to confront my own ideas about infinity and the nature of numbers. I soon saw that this exploration into the connections between Turing Machines and Brouwer's philosophy of mathematics had to become its own chapter that I called "Conceiving the Continuum." It was a tough chapter to write, but very rewarding as well.

I like all the chapters in my book, of course, but I have a very special fondness for this one.

	Coming June 16, 2008! Available for Pre-Ordering
	Wiley	Amazon US	Barnes & Noble
	Amazon Canada	Amazon UK	Amazon Deutsch
	Amazon Français	Amazon Japan	Blackwell