“Surveyability” in Hilbert, Wittgenstein and Turing

Abstract

An investigation of the concept of “surveyability” as traced through the thought of Hilbert, Wittgenstein, and Turing. The communicability and reproducibility of proof, with certainty, are seen as earmarked by the “surveyability” of symbols, sequences, and structures of proof in all these thinkers. Hilbert initiated the idea within his metamathematics, Wittgenstein took up a kind of game formalism in the 1920s and early 1930s in response. Turing carried Hilbert’s conception of the “surveyability” of proof in metamathematics through into his analysis of what a formal system (what a step in a computation) is in “On computable numbers, with an application to the Entscheidungsproblem” (1936). Wittgenstein’s 1939 investigations of the significance of surveyability to the concept of “proof “in Principia Mathematica were influenced, both by Turing’s remarkable everyday analysis of the Hilbertian idea, and by conversations with Turing. Although Turing does not use the word “surveyability” explicitly, it is clear that the Hilbertian idea plays a recurrent role in his work, refracted through his engagement with Wittgenstein’s idea of a “language-game”. This is evinced in some of his later writings, where the “reform” of mathematical notation for the sake of human surveyability (1944/45) may be seen to draw out the Hilbertian idea. For Turing, as for Wittgenstein, the need for “surveyability” earmarks the evolving culture of humans located in an evolving social and scientific world, just as it had for Hilbert.

1. Introduction

Turing visited Göttingen in the late spring of 1934, after his graduation from King’s College and before beginning to write his dissertation. According to Hodges (1983/2012, 82), the purpose of this trip was to consult with someone, “presumably” on the subject of his Fellowship dissertation, which proved the Central Limit Theorem in probability theory (Turing spoke German). As Hodges explains, Göttingen was the mathematical and scientific center of the world at that time. Might Turing have also discussed logic and the foundations of mathematics with students and/or professors at Göttingen in 1934? After all, Hilbert and Bernays had been lecturing on foundations of logic there since 2017 [1].

Turing had developed his focused interest in logic in spring 1933, drawn in—as Gödel and Kleene also were—by reading Russell’s Introduction to Mathematical Philosophy [2]1. Transcriptions of Hilbert’s lecture notes on the foundations of mathematics were available in the Göttingen mathematics library and used by students regularly, had Turing stopped by2. Although Bernays had been fired in April 1933 with the Nazi takeover of the University, leaving Göttingen by February 1934, memories of his work as Hilbert’s Assistant would have remained among the students and instructors in the early summer of 1934. Newman’s course at Cambridge on mathematical logic, which Turing attended in 1935, had already in 1934 presented developments in the field via Hilbert and Bernays’s textbook [5]3. Within two years Turing would correspond with Bernays about the corrections to “On computable numbers” [7]4. So, as Hodges makes clear, and as, e.g., Copeland explains [9], Turing was, historically speaking, in the orbit of Göttingen’s tradition in logic and proof theory at the time he wrote “On computable numbers”. After all, his paper resolved the Entscheidungsproblem, which Hilbert himself had posed in his textbook with Ackermann [10].

Whether or not the young Turing, already interested in logic and philosophy, profited from discussions of philosophical and foundational issues with students or professors in Göttingen in 1934, as philosophical readers of history we can ask about the relation of Turing’s work to Hilbert’s views on proof theory and the foundations of mathematics. The aim of this essay is to investigate an important logico-philosophical, Hilbertian strand in Turing’s work: the idea of the “surveyability” of proof. This idea makes itself felt also in Post’s work [11], which bears important affinities, logico-philosophically, to Turing’s5. But we shall restrict ourselves to the Hilbert-Turing-Wittgenstein philosophical orbit around surveyability in what follows.

“Surveyability” will stand in here for a number of closely related terms to be found in original German writings of Hilbert and Wittgenstein: Überblickbarkeit, Übersehbarkeit, and Übersichtlichkeit—and this requires clarification6. Mühlhölzer ([21,23]) has discussed the Hilbert-Wittgenstein relation in light of Wittgenstein’s manuscripts, offering what I think of as a very useful, minimalist reading of what Wittgenstein meant in using these Hilbertian terms to characterize something characteristic of proof. According to Mühlhölzer’s reading, the “surveyability” of a proof means that it can be reproduced easily, like a picture, and we must be able to decide with certainty whether or not a reproduction reproduces or pictures that proof. By extension, the “surveyability” of a character or sign would exhibit just the same features of easy reproducibility, culminating in the ability of a human being to be able to decide with certainty whether or not one instance of a symbol in a notation is the same as another, and whether or not one symbol immediately precedes or follows another. (Wittgenstein already raised this latter issue as fundamental to our concept of the logical in his Tractatus ([24], hereafter “TLP”, 3.203).) Mühlhölzer emphasizes that in Wittgenstein’s manuscripts from 1937 onward “surveyability” is used in “a purely formal sense that has nothing to do with understanding, at least not in the sense of ‘mathematical understanding’”7, but rather is characteristic of certain everyday mathematical and other rule-following human activities. We shall probe the extent and limits of this minimalist reading in what follows, gauging its relation to Hilbert, to Turing, and to the human drive for intelligibility. While the term “surveyable” does not so far as I know occur in Turing’s writings explicitly, I take this concept to have nevertheless been an important one for him, philosophically speaking8. Our investigation of the idea of “surveyability” in Turing will serve, not only to expand on Mühlhölzer’s analyses of Wittgenstein and Hilbert’s uses of the concept, but also shed light on an important affinity linking Turing with Hilbert and Wittgenstein. “Surveyability” emerges as a kind of norm, not simply something descriptive, an earmark of what human beings in fact do.

An idea of the “surveyability” of proof makes itself felt in a number of Turing’s writings, and at crucial points, always interpreted in terms of the communicability and intelligibility of proof, its pragmatic and characteristic employment for and by human beings. The need for some version of the idea remains with us today, in an age of formal proofs, internet crowdsourcing of mathematician’s activities, and debates over the extent to which these should be considered driving marks of achievement in mathematics9. I shall argue that in his remarks touching on surveyability, Turing was self-consciously addressing himself to, and philosophically reinterpreting and generalizing, Hilbert’s account of the “finitistic” foundations of proof theory at several crucial junctures. While this is not a surprising or controversial thing to conclude, what is interesting is how Turing’s reinterpretation of Hilbert’s idea highlights the features of communicability, reproducibility and intelligibility that lie at the heart, not only of Hilbert’s foundational enterprise, but of the wider logico-philosophical tradition stemming from Frege, Russell and Wittgenstein. In this tradition, as Sieg has put it, the “normative demand for intersubjectivity between humans motivated the step from axiomatic to formal systems” ([31], p. 200). It was, I shall add, in Turing’s and Wittgenstein’s work that the step from formal systems to the fundamental idea of embodied human beings operating with signs in “forms of life” was made. In our world, faced with the growth of social media and the world wide web, the normative demand for radical intersubjectivity has shown its dangers and limits, as well as its uses, and this is something that Turing presciently foresaw, and worried about, as we shall see: the effect on human culture of mathematics, and vice versa.

It will thus be important to characterize in what follows the precise philosophical points at which Turing’s highlighting of surveyability entered into his work. I shall make much of Turing’s relation to Hilbert and Wittgenstein here, without impugning Hodges’s account of other important philosophical influences on Turing during his undergraduate and early graduate years10. While most of the direct mathematical connections between Turing’s work and Hilbert’s are already clearly explained in the literature11, the philosophical relations with Wittgenstein, as well as those involving “surveyability”, are obscurer12. By drawing these out, Turing may be affiliated with an important series of steps in this philosophical tradition in the foundations of logic.

Further, Turing may be seen to have contributed to and elaborated that tradition. For he sent Wittgenstein an offprint of “On computable numbers” by early 193713. Clearly the interplay between Turing’s analysis of computatability and Hilbert’s ideas about the surveyability of proof, so vivid in Turing’s paper, caught Wittgenstein’s eye. Wittgenstein’s subsequent fascination with the concept of “surveyability”, especially evident in his writings 1937–1939, reflected, as I have argued elsewhere, his ongoing responses to Turing’s and Hilbert’s work14.

In his 1939 Lectures on the Foundations of Mathematics at Cambridge ([37], hereafter “LFM”), attended by Turing, the two continued discussions begun in 1937, particularly focusing on the notion of a mathematical “technique” (the term occurs 117 times in the notes of the lectures and enters firmly into Wittgenstein’s repertoire as a concept only at this point). Wittgenstein’s manuscripts from 1937–39, later selectively published as Remarks on the Foundations of Mathematics ([19], hereafter “RFM”), show an ongoing fascination with the topics of “surveyability” and mathematical “techniques”. In turn, Turing explicitly wrote that his paper on types and the “reform” of mathematical notation was stimulated by attending Wittgenstein’s lectures (see Turing’s 1944/45 unpublished paper [38], quoted below). Turing would address as well the related issues of evolving forms of cultural life and the human drive toward nonsense, as we shall see.

What emerges from all this is a larger question: how does the to and fro of metaphor and philosophy shape mathematical practice, especially at the foundations? From the perspective of philosophy of logic and mathematical practice it is crucial to explore the roles that metaphors play. For while in mathematical proving the aim is to eliminate appeals to unpacked metaphors, at the same time, within the practice itself, metaphors crop up everywhere to aid understanding15.

With regard to the notion of “surveyability” it will be argued that although it is partly metaphorical, the notion has foundational, philosophical significance of a very particular cast. In this regard I shall argue that the concept’s significance does not reduce itself to the fact that Turing dogmatically assumed certain empirical facts of human psychology, as has often been alleged16. It is of course true that for purposes of modeling cognition Turing’s “machines” have proved their power17. But this is very different from supposing, as Post and Gödel did, that Turing’s foundational work necessarily forwards a particular mechanistic conception of mind in general18. Rather, I take Turing to have forwarded a language-game—a snapshot of a portion of characteristic human linguistic activity—to philosophically and mathematically unlock as homespun or home-baked (to use Wittgenstein’s phrase) the relevant features of our very concept of “computing” or “calculating according to a fixed rule”19.

While Turing certainly did emphasize ([7], §9) that experientially evidenced facts about human beings shape our sense of what is fundamental in logic—namely, symbolic configurations must, generally speaking, at some point be able to be “taken in at a glance”, independent of any particular piece of mathematical knowledge or theory—this was not primarily a theory of mind, but rather one that concerned, first and foremost, the foundations of logic and mathematics. And here there lie residues that remain, for better or for worse, “raw”, right alongside and part and parcel of what is “cooked”20.

2. Surveyability at Work in the Grammar of “Computable”

What Turing writes in his [7] is that, if his “machines” are going to be able to represent all operations that human beings could possibly carry out by “computing”—i.e., reckoning according to a fixed rule—he must rely on what he calls (using quotes) “‘simple operations’ which are so elementary that it is not easy to imagine them further divided…[and that] … …in a simple operation not more than one symbol is altered” ([7], §9). The generality of the characterization is key here, but the notion of simplicity is complex, and merely saying that he is describing a practice with language vastly underestimates the character of this move21.

What Turing stresses is that in his model of human computing the number of symbols that may be written down is finite—as in our alphabet or the decimal notation—and that each symbol must be such that a glance at it leaves no doubt for the ordinary human perceiver that it has been fully “taken in” and individuated. This is because the human/machine scanning a symbol is, if calculating or computing, to be immediately clear, confident, and correct about which symbol it is that is being scanned and what the human/machine is to do next, and this is ensured partly by requiring that the symbol must be a discrete, immediately intelligible component of the system of operating with signs for the humans concerned. This is what allows for the clear communicability of the procedure, as well as the human capacity for public, shared certainty—the lack of endless disputes and doubts—about what the correct results are and should be.

This, one might say, with Wittgenstein, is in a sense a grammatical point about the relevant concept of calculating: not a matter of necessary and sufficient examples for anything that we call a “computation”, but rather an observation about our human forms of life, considered both biologically (evolutionarily) and culturally. That is to say, the phenomena characteristic of human calculators is shown across the varying kinds of human life forms that there are. As Wittgenstein later writes ([51], hereafter “[PI]”, PPF xi):

§341. A dispute may arise over the correct result of a calculation (say, of a rather long addition). But such disputes are rare and of short duration. They can be decided, as we say, ‘with certainty’.

Mathematicians don’t in general quarrel over the result of a calculation. (This is an important fact.)—Were it otherwise: if, for instance, one mathematician was convinced that a figure had altered unperceived, or that his or someone else’s memory had been deceptive, and so on—then our concept of ‘mathematical certainty’ would not exist.

And also

§240. Disputes do not break out (among mathematicians, say) over the question of whether or not a rule has been followed. People don’t come to blows over it, for example. This belongs to the scaffolding from which our language operates (for example, yields descriptions).

These quasi-anthropological remarks express Wittgenstein’s mature philosophical stance—one he devised, as I believe, partly through reading Turing’s [7]22.

In these remarks he is not merely pointing to our forms of life, but also highlighting the actual contingencies in our world—in our modes of speaking and proceeding in language—that form a needed, evolving backdrop to the necessities exhibited in calculations. Once they are pointed out, of course, forms of life may be used as tools of criticism: though Wittgenstein does not explicitly mention Marx, surely the point that human beings are, as a matter of fact, used as machines and are trained to act mechanically is of fundamental philosophical importance to questions about what, in the end, we are really doing, not only when we do mathematics but when we use mathematics in the course of life, doing other things.

With respect to the “certainty” that characteristically earmarks what we call “calculation”, Mühlhölzer [54] quotes from Wittgenstein’s On Certainty ([55], hereafter “OC”) labelling the following “Wittgenstein’s multiplication problem”:

Perhaps I shall do a multiplication twice to make sure, or perhaps get someone else to work it over. But shall I work it over again twenty times, or get twenty people to go over it? And is that some sort of negligence? Would the certainty really be greater for being checked twenty times? (OC, §77)

This quandry is, as Mühlhölzer emphasizes, not merely a recapitulation of the “problem” of characterizing what it is in general to follow a rule. Rather it is that although generally speaking checking helps better the evidence for our claims, thereby increasing their epistemological value, in cases like this this at some point unmotivated, repetitive re-checking, by means of the same or differing techniques and the same or differing people, must terminate, and if it does not, these activities would lose the (relevant) character of “calculation”. The whole idea of doing epistemic justice to the concept of calculation requires that we take into account this characteristic manifestation of trust and certainty easily and confidently exhibited and secured in everyday life, by hook or by crook, and always building upon vast cultural resources put in to training human beings to act “unthinkingly” when operating rules to calculate. It should not matter who makes the calculation: all should be impersonal. In this way Wittgenstein raises a potentially skeptical juncture of thought to elucidate the grammar of our concept of “calculation”.

In raising this question, we are asked not to assimilate cases where a simple calculation (e.g., “2 × 2 = 4”) is made by a competent speaker, in an everyday, “normal” context to a large formalized proof or calculation which requires many people or perhaps even machines to check it. For in the latter case there seems to be a principled difference in the role repetitive checking would play. Nevertheless, the basic idea that the simplest language-game elucidates a crucial, generally ubiquitous feature of any method or system or collection of techniques of calculating remains in place. For if many people and/or machines are used to check the proofs, then there could be a need for further people to check the machines and their programs, or further machines to check the results of other machines. The important point would be that at some point, if what we have is “calculating” in an everyday sense, this process ends. And it is important to the application of our very concept of calculating that it end repeatedly, communicably, and with certainty, at the same result, or, in the case of a vast or vastly complicated calculation, perhaps very close, allowing for a specific margin of error given things we know about human beings and their physical, emotional, technological, perceptual and calculational capacities.

3. Surveyability vs. Subitizing

In the Hilbertian context, like Wittgenstein, Turing [7] treated the issue of “simple” operations with signs as a matter of unfolding our intuitive, ordinary notion of the activity of a human being “calculating” according to a fixed rule. He took as his paradigm the calculating out of digits of a real number in its decimal expansion, taking this to exemplify, at least for his mathematician readers, the “least cumbrous technique” ([7], Introduction). Turing made clear that “if we were to allow an infinity of symbols, then there would be symbols differing to an arbitrarily small extent” ([7], §9 I)—but then, clearly, the uncontroversial, repeatable, impersonal, terminating and communicable immediacy of our computational certainty would give way.

Allowing the use of sequences of simple symbols allows for the construction of a potential infinity of “command” strings, allowing far greater expressive power and scope for “computation” routines. However, certain sequences that are too lengthy “cannot be observed at one glance”, something “in accord with experience”, as Turing says ([7], §9 I). Ordinarily, a command that a human being cannot possibly take in or understand does not count as a “command”.

As a matter of fact, this ability of humans to take in sequences of symbols at a glance had been emphasized by Hilbert on more than one occasion when he presented his finitistic perspective on metamathematics (e.g., [56], §25). As Newman put the point in his 1934 lectures on logic at Cambridge ([6], Lecture 13, 5/19/1934): “metamathematics requires the possibility of recognizing symbols, and of scanning rows of symbols”.

It is obviously, uncontroversially, and ordinarily too difficult for humans to tell at a glance the difference between

||||||||||   and      |||||||||||

or to take in the number of more than a few strokes or numerals at a glance, quickly and confidently, without counting23. When we can utilize our visual powers to discriminate differences of number at a glance, without bringing to bear a concept, theory or counting procedure, this is a matter of subitizing, a phenomenon currently studied by psychologists with increasing interest24. It seems that for visible objects, confidently and quickly determining the number of certain kinds of objects before one at a glance, without counting, is something human beings (and other animals) can do fairly easily up to the number four—though it is a difficult methodological question for psychologists to determine whether what is being discriminated here is number, or simply the notions of “same” vs. “different”.

The important point, for purposes of the foundations of mathematics in the Hilbert-Turing-Wittgenstein context, is that subitizing is more difficult for more complex collections, and it gives out at some point or other. This is why notational and technological systems—from the finger to the token to the abacus to the Arabic notation to the digital computer—have been devised throughout human history. The point is a logical one, because it applies to notations themselves: the stroke notation used above becomes very quickly unsubitizable for us. The Arabic notation outstrips human subitization a bit later. Kripke, whose Harvard Whitehead lectures explored a possible foundational view of number based on this representational fact, called the subitizable portions of a notation “buckstoppers”, connecting the idea with Wittgenstein’s discussion of “surveyability” in RFM III (from 1939)25.

Given the evolution of symbolic prostheses in the development of programming languages today, what is important for our purposes is however not what the ultimate buckstoppers there are, but that there must be some buckstoppers in any system deserving the name of “mathematics”26.

Subitizing, in other words, highlights an interesting fact highly relevant to foundations of mathematics: we need to develop mathematical techniques to take on what we cannot subitize, and these techniques must exhibit clearly communicable, procedural termination. The “beginnings” of mathematics, as Wittgenstein called them27, are entangled with human practical needs for procedures, for the development of useable, communicable, repeatable, explainable and terminating-in-agreement techniques for the application of numbers in life, ordinarily using symbolic prostheses. It is to our understanding of the latter issue, rather than the straight psychology of subitizing, that Turing contributed in his paper of 1936 [7].

This may be lost sight of if we exclusively emphasize, as so much of the philosophical literature has, the relation of Turing’s work to computational psychology and philosophy of mind taken at the level of the individual. It is true that the computational perspective Turing opened up is crucial for psychology and neurology, and also true, as Hodges emphasizes, that the nature of mind, free will and spirit were crucial philosophical issues for Turing [3,33]). The facts of subitization in the animal world are fascinating in themselves. But it is also true, as Mühlhölzer has rightly emphasized ([21,23]), that we should avoid psychologistic readings of Wittgenstein’s notion of “surveyability”, for example those that take Wittgenstein to have been exploring strictly visual criteria of sameness of number28.

The same is true, I think, of Turing, who stimulated Wittgenstein to investigate the concept in 1939. By bringing Turing and Wittgenstein together back into the orbit of Hilbert, we are able to explore the “beginnings” of mathematics and logic without the intrusion of psychologism.

Turing’s analysis of what it is for a human being to take a “step” in a formal system, or “compute”—his human–machine analogy, and Turing explicitly calls this a “comparison” ([7], §1)—is, from our present point of view, to be regarded as an elaboration of Hilbert’s finitistic approach to proof theory, and therefore part of an amentalistic foundations of mathematics. As Georg Kreisel, a student of Wittgenstein’s, once said, when it comes to the foundations of logic and mathematics, “no matter, never mind”29.

Neither Hilbert nor Wittgenstein nor Turing had a general theory, either of metaphor or of matter or of mind. Instead, their analyses turned on invoking and taking seriously the friction of ordinary, everyday concepts such as “surveyability” and “mathematical technique”. We can see this by revisiting Turing’s analysis of the very notion of a formal system of logic and emphasizing how he rooted this ultimately in a kind of anti-psychologism about logical foundations inherited from Hilbert and Wittgenstein. Turing reworks this anti-psychologism, self-consciously hewing, throughout his work, to certain foundational ideals of simplicity, intersubjectivity and objectivity that he inherited from them. In turn, he stimulated Wittgenstein to revisit the role of “surveyability” in our conception of mathematics, and then, in response, saw the future of the ways in which human beings would develop, in a social and evolving cultural setting (forms of life) languages and typed symbolic systems to interact with the aids given by stored program computers.

4. Hilbert on Überblickbarkeit: What Is a Metamathematical “Foundation”?

Hilbert’s finitistic metamathematics urged the importance of taking up a particular stance toward the foundations of mathematics, at least for the purposes of proof theory: metamathematics. Hilbert emphatically did not think that all of mathematics should proceed by taking up this stance. Rather his idea, as later articulated by Bernays, was to subject the concept of the logical to mathematical articulation, contrasting Kant’s traditional idea of logic as analytic knowledge given through a “pure consciousness of meaning” with mathematical knowledge, which rests, according to the Hilbertian view, on basic, “concrete” intuitive evidence. By this Hilbert meant, not that the evidential objects of mathematical knowledge are located in space and time, but rather that they are simple and self-evident, not reliant on abstract concepts30.

Bernays defines mathematical knowledge as something resting on formal (structural) consideration of objects, the numbers being, not logical objects (as the logicists had held), but rather “the simplest formal determinations” ([65], §3, p. 243). Hilbert encapsulated the attitude with the slogan, riffing on Goethe’s Faust, that in the beginning was the sign ([16], §25)—Wittgenstein would later make a riposte by resuscitating Goethe’s actual saying, “In the beginning was the deed”31—that is, uses of signs by human beings and, ultimately the evolving embedding of these signs in modes of use in everyday life (Lebensformen).

In an essay that Wittgenstein certainly read, Hilbert gives an example. We may consider “concrete” signs, i.e., simple numerals in an alphabet, “extra-logical discrete objects, which exist intuitively as immediate experience before all thought” ([16], §25). Hilbert wrote,

If logical inference is to be certain, then these objects must be capable of being completely surveyed in all their parts [überblicken lassen], and their presentation, their difference, their succession (like the objects themselves) must exist for us immediately, intuitively, as something that cannot be reduced to something else. Because I take this standpoint, the objects [Gegenstände] of number theory are for me—in direct contrast to Dedekind and Frege—the signs themselves, whose shape [Gestalt] can be generally and certainly recognized by us—independently of space and time, of the special conditions of the production of the sign, and of insignificant differences in the finished product. [Note: In this sense, I call signs of the same shape ‘the same sign’ for short.] ([16], §25).

Hilbert proceeds to give the example of (a) the sign 1 is a number, and (b) a sign that begins with 1 and ends with 1 and 1 always follows +, is a number, so that the number signs are

1
   1+1
      1+1+1,
        and so on,

…and these number-signs, which are numbers and which completely make up the numbers, are themselves the object of our consideration, but otherwise they have no meaning [Bedeutung] of any sort” ([16] §§29). Thus “2”, “100” and so on are really abbreviations, “3 > 2” serving “to communicate the fact that the sign 3 (that is, 1+1+1) extends beyond the sign 2 (that is, 1 + 1), or that the latter sign is a part of the former” ([16], §29).

Hilbert should not really be called a philosophical “formalist” in general32. Rather, he was advocating the use of a particular mathematical technique, formalization, in furthering the rigorous axiomatization of theories, viz., the technique of metamathematical reasoning about a theory through the construction of a formal system whose formulae are finitistically constructed. By this means could be marked the substantial mathematical assumptions Hilbert called “contentual” [inhaltliche] ([16], §§73, §§80-81, §83; [68], §36).

Hilbert thus draws out and clarifies mathematically the finitistic aspect of mathematical reasoning. Poincaré ([69,70]) had argued against Hilbert ([71]) that the metamathematician needs to presuppose the truth of mathematical induction in order to set out the class of well-formed formulae of any formal system. Wittgenstein, who took our capacity to iterate “formal series” step-by-step indefinitely far to be a fundamental logical capacity embedded in our grasp of language, was sympathetic to Poincaré, while turning his argument into a logical one (see TLP 4.1252, 5.501, and [72]). However, mathematically speaking Hilbert’s stance allowed him to distinguish between strong principles of induction expressed in the formal system itself, and weaker principles used in the metalanguage, where we reason “contentually” about possible configurations of signs ([16], §31).

Many have opposed “formalism”, taking mathematical experience and conceptually contentful meaning to be fundamental to mathematics at each and every point. But the Hilbertian metamathematical moment in which one touches down in a reduction to humanly operable sequences of signs, if only a moment, is a necessary one, conceptually speaking. Frege and Russell, who had formalized the foundations of mathematics, had no general way of proving that one sentence does not follow from another, or a set of axioms. Of course, Frege and Russell could in any particular case maintain that if one has a derivation of a proposition Q from another proposition P, then this shows that -Q is not a consequence of P. They had circumscribed rules, they could analyze purely logical steps down to the point of utter precision, providing a gap-free analysis of any specific sequence of logical inferences33. But a general method for negative results was lacking. This related brings out the importance of their assumption that pure logic must be consistent, i.e., never generate contradictory results, an assumption applied in each particular case of “negative” results about logical implication.

This created an apparently fundamental disanalogy with the axiomatic approach in geometry. There alternative axiom systems may be tested for consistency via the construction of models, and their logical structure articulated using the axiomatic approach Hilbert perfected in his Foundations of Geometry [79]). However, laws of logic cannot, Frege and Russell held, be meaningfully denied, as axioms of geometry may be. Frege held, for example, that affirming a false thought is not really to put together a judgement. For to count as a judgement—an acknowledgement of the True—the True must be the object judged, and if one attempts to acknowledge the True, but in fact acknowledges something else, then one’s judging is no real judgement. This point concerning truth must, Frege [80] argued, be generally assumed at each step, something Hilbert did not pretend to do. Russell reiterated the point about methods of geometry not applying generally in logic ([81], chap. 2, §17), and in Principia Mathematica made the base-step for his quasi-recursive definition of truth-levels a collection of “judgments of perception”, which are assumed to be true, “perception” being treated here as a success verb34.

Hilbert’s sharp distinction between remarks about the logical system and statements within it was “foreign” to this point of view (Sieg, in [1], Introduction, p. 9). Later on, in a quite different, conventionalist vein, the middle Wittgenstein flatly denied that there is such a thing as the “game”, or system, of mathematics, furthering the idea that “metamathematics is just more mathematics”35 This hard pluralism yields the consequence that there is no generally applicable notion of consistency, so that Hilbert’s foundational project of metamathematics is not applicable to logic or mathematics in general, but only to formalisms one by one. This vague hunch was on the right path, as Turing later showed, even if at the time it was based on an unsatisfying, dogmatically conventionalistic and purely philosophical point of view. Having been the first to conjecture a decision procedure for logic—in a letter to Russell of 191336—in 1929–1931 Wittgenstein was repudiating his earlier conception of the unity of logic as a single, absolute system. By responding to Hilbert’s metamathematics, he was incorporating the formalist point of view, attempting to give it its due in a kind of game-formalism37.

Wittgenstein thus rejected Hilbert’s idea that consistency proofs were foundational for all of mathematics, on the basis of a re-interpreted, relativistic Hilbertian ground. He raised explicitly the question whether the search for models conducted by Hilbert really constituted a general logical method, something universally applicable in one way38. On his view metamathematics cannot yield “absolute” certainty through consistency proofs applicable across all of science, as Hilbert had hoped ([56], §33). Ultimately such proofs can at best titrate comparisons between particular differing game-formalisms: some systems would be classically inconsistent (and so “tautologous”) and some not, but discriminating between and comparing systems would have to be done on a case-by-case basis, experimentally, so to speak, as opposed to calculationally. And then there could be no way to require, as Hilbert had, that

The chief requirement of the theory of axioms must … show that within every field of knowledge contradictions based on the underlying axiom-system are absolutely impossible ([56], §33).

In his [7] Turing shows that although the notion of “computable” has a certain absoluteness, as Gödel termed it—i.e., Turing-computability is a robust concept, a fixed parameter remaining constant, independent of the particular formalism or language used39.

• —there can be no general algorithm (or formalism) used to determine, for any arbitrary formalism, not only whether or not it is consistent (Gödel’s [87]) but even whether it will output this or that configuration of signs on a given input (Turing’s [7]). Hence, there are fundamental philosophical, mathematical and logical limitations to the Hilbert program.

Turing was clearly aware of the interplay between his [7] and Hilbert’s views. Far from thinking he had refuted Hilbert, in his PhD dissertation ([88]) he developed mathematics designed to adapt the Hilbert program to the situation his work and Gödel’s had exposed. His ordinal logics were designed to transcend Gödelian incompleteness through the use of what, in an anthropological twist of terminology, Turing called “oracles”40. He thus emphasized that human “intuition” and “ingenuity”, which cannot be analyzed in terms of step-by-step rules, could enter into the development of mathematics in a controlled way, circumscribed through steps made explicit in adding assumptions41.

In a letter to Newman (c. 1940, [89]) Turing referred to this work explicitly in the context of Hilbert’s point of view—one of the few places, as Copeland notes ([9], p. 206), where he writes explicitly about the foundations of mathematics:

Ingenuity and Intuition. I think you [Newman] take a much more radically Hilbertian attitude about mathematics than I do. You say ‘If all this whole formal outfit is not about finding proofs which can be checked on a machine it’s difficult to know what it is about.’ When you say ‘on a machine’ do you have in mind that there is (or should be or could be, but has not been actually described anywhere) some fixed machine on which proofs are to be checked, and that the formal outfit is, as it were, about this machine. If you take this attitude (and it is this one that seems to me so extreme Hilbertian) there is little more to be said: we simply have to get used to the technique of this machine and resign ourselves to the fact that there are some problems to which we can never get the answer. On these lines my ordinal logics [88] would make no sense. However, I don’t think you really hold quite this attitude because you admit that in the case of the Gödel example one can decide that the formula is true, i.e., you admit that there is a fairly definite idea of a true formula which is quite different from the idea of a provable one. Throughout my paper on ordinal logics I have been assuming this too ([9], p. 215).

• Note the Hilbertian tone of “optimism” in Turing’s remarks on “extreme” Hilbertianism: although we must resign ourselves, in the use of any one machine (formal system), to admitting that “there are some problems to which we can never get the answer”—i.e., we must face what Hilbert called the ignorabimus42 —this does not mean that, with “ingenuity”, i.e., the human use of informal steps, we may not come close enough to knowing answers. Moreover, Turing continues, if we think opportunistically about the potentialities of a variety of systems (“machines” now refers to literal machines, as well as routines calculated with by humans), we may well be able to circumscribe the very idea of “provability” more and more closely:

… If you think of various machines I don’t see your difficulty. One imagines different machines allowing different sets of proofs, and by choosing a suitable machine one can approximate ‘truth’ by ‘provability’ better than with a less suitable machine, and can in a sense approximate it as well as you please. The choice of a proof checking machine involves intuition, which is interchangeable with the intuition required for finding an Ω if one has an ordinal logic Λ, or as a third alternative one may go straight for the proof and this again requires intuition: or one may go for a proof finding machine ([9], p. 215).

Having invoked the need for human “intuition”—i.e., choices and guesses that are not necessarily formalizeable—Turing then argues that a “proof finding machine” still falls within the scope of the Hilbertian ideal of metamathematics and proof theory as an approach:

I am rather puzzled why you draw this distinction between proof finders and proof checkers. It seems to me rather unimportant as one can always get a proof finder from a proof checker, and the converse is almost true: the converse fails if for instance one allows the proof finder to go through a proof in the ordinary way, and then, rejecting the steps, to write down the final formula as a ‘proof’ of itself.

• The suggestion here is that one might still use “proof finder” systems of deductive logic to generate proof checking systems, so long as one realized this would not resolve all problems. Alluding to his own diagonal argument showing that there is no general decision procedure for logic ([7], §8) Turing notes, as he had shown, that a proof checking system cannot be assumed to be able to check any system, on pain of one being able to define a tautological machine in connection with its own behavior. The latter proof—as Wittgenstein later noted explicitly43—shows that if we imagine a single machine that could determine, Yes or No, the behavior of any arbitrary machine, it would collapse into tautological circularity when it ran into its own commands. Turing’s proof, and his suggestion to Newman, circles back to the Wittgensteinian idea that the limits of logic lie in tautological constructions of rules that cannot be followed as commands: in general, for logic human embedding in a particular context or form of life is needed “friction” (Wittgenstein [51], [PI] §107).

All this, let us emphasize again, grants something very important to Hilbert. Hilbert’s metamathematical analysis in terms of “effectively” surveyable modes of proof is essential for making clear sense of the idea of comparing different formal systems with one another. Hilbert’s metamathematical perspective is just what was required to make what general sense can be made of the idea of one sentence’s following or failing to follow in a particular system44.

Hilbert had written that with his metamathematics, “proof procedures become completely surveyable [Überblickbar]”45. This is because the finitistic aspect of our very concept of proof or argument emerged clearly in his analysis, grounded on these purely formal determinations. As Hilbert also wrote, a “formalized proof, like a numeral, is a concrete and surveyable object. It can be communicated from beginning to end” ([17], p. 383). What a formalized proof yields is something “immediately intuitive and directly intelligible” ([17], p. 380). The intersubjective communicability and impersonal, repeatable nature of proof, as well as an ideal of “direct intelligibility”, lie at the heart of Hilbert’s foundational stance.

This is less an aspiration to psychological theorizing for its own sake than an emphasis on the kind of intelligibility and communicability mathematics is capable of affording us with proofs. As for Frege, so for Hilbert: ultimately the social, communicable, logical character of thought is something depsychologized.

As part of his ideal of intersubjectivity, Hilbert aimed to overcome controversy in the foundations of mathematics through the application of mathematics to pure logic:

If we use contentual [non-finitistically regarded] axioms as starting points and foundations for the proofs, then mathematics thereby loses the character of absolute certainty. With the acceptance of assumptions we enter the sphere of what is problematic. Indeed, the disagreements among people are mostly due to the fact that they proceed from different assumptions ([16], p. 233).

However,

Now the theorems at issue can in part be proved, in an absolutely certain and purely mathematical fashion, with the help of the present results, and they have therefore been removed from the dispute. Whoever wants to confute me must show me, as has always been customary in mathematics and will continue to be so, exactly where my supposed error lies ([16], p. 228).

The main Hilbertian points for our purposes are these:

• Certain symbols are a precondition of the application of logic. (They serve as parameters.)
• These symbols are extra-logical, discrete, and intuitively immediate before all thought.
• Logic’s certainty depends upon the surveyability [Überblickbarkeit] of these symbols in all their parts (simplicity).
• These symbols are irreducible and objects of direct intelligibility.

5. Turing 1936 and “Surveyability”

Turing’s “On computable numbers, with an application to the Entscheidungsproblem” [7] extended Gödel’s work, making clear that the finististic aspects of proof emphasized by Hilbert have their limits. Gödel [87] showed, first, that first-order logic, though complete, does not always have a finitistically terminating formal procedure for finding a counter-model in cases where one sentence fails to follow from a set of axioms. Second, Gödel [78] showed that first-order arithmetical truth cannot be completely axiomatized in the Hilbertian manner: there will always exist unprovable sentences for any given axiomatization incorporating arithmetical truth in this way. Turing then showed that there can be no one machine (no one algorithm or proof system) for determining Yes or No as an answer to the question of whether or not a sentence of a formal system of logic does or does not follow from the axioms of a theory. There can be no general way of deciding, no “definite method” of the kind that Hilbert’s Entscheidungsproblem had sought.

The interplay between Turing and Hilbert is thus subtle and fascinating. For the meaning of Turing [7] depends upon assumptions of Hilbert himself. Perhaps following Newman, perhaps following Wittgenstein, and perhaps following both or neither, Turing took more seriously and literally than Hilbert and Gödel did the idea of a formalism as a machine, in this case a mechanical procedure carried out by a human being reckoning according to a rule46. “Turing’s ‘machines’. These are humans who calculate”, as Wittgenstein later remarked47.

Whereas the Hilbert school and Herbrand, Church and Kleene worked as mathematicians with systems of equations and the lambda calculus (as Turing would do as well), Turing began his “beginnings” of an analysis of what a formal system is in his [7] with a more informal idea. This informality, this logic-free character to his analysis of what a logic (in the relevant sense) is, is what lent weight to his analysis of the very notion of what a “step” in a formal system of logic is. Turing analyzed Hilbert’s idea of a “definite method” in terms of the existence of what Church soon called a “Turing Machine” ([92], p. 43), couched in Turing’s [7] in terms of command tables utilizing a finite set of symbols and finite, discrete states of a machine, i.e., a human calculator.

Why does Turing need to insist in his 1936 that his human–machines can “take in at a glance” the command structures ([7], §9)? What he says is that he needs to argue, informally, that he has found a mathematical representation that plausibly answers the question, “What are the possible processes which can be carried out in computing a number”, i.e., by a human. And he has already said ([7], §1) that the fundamental “justification lies in the fact that the human memory is necessarily limited”. We have seen that this marks out the “beginnings” of mathematics, rather than advocating any particular psychological theory: it marks off the phenomenon of calculation, in an everyday, mundane way. There is a phenomenon generally characteristic of human forms of life: calculation that terminates in agreement, impersonally and without dispute. As Hilbert (and as we have seen, later Wittgenstein) noted, mathematicians do not “come to blows” over whether a particular written sign is or is not an instance of a symbol-type (Wittgenstein [51] §240). “Surveyability” of proof captures this phenomenon, which is partly normative.

Turing rightly stresses in spelling out his characterization that “all arguments which can be given [in characterizing “computable”] are bound to be, fundamentally, appeals to intuition, and for this reason rather unsatisfactory mathematically” ([7], §9). However, his intuitive, partly informal approach is necessitated by the foundational context. For to analyze what a formal system is—in Hilbert’s terminology, a “definite method” for deciding questions about implication in formal systems—it will not do to simply concoct a new formalism (such as the λ-calculus). Instead one must do something, philosophically speaking, find a way of marking out the concept sufficiently plausibly, and informally. What Kennedy [49] calls “formalism freeness” is a mathematical desideratum in this context, not a defect.

Turing says he will offer what he calls three different kinds of arguments ([7], §9):

(1)

A direct appeal to “intuition”, i.e., something not mathematical.

(2)

A proof of the equivalence of two definitions (Turing’s with the λ-definable functions) “in case the new definition has greater intuitive appeal”.

(3)

Giving examples of large classes of numbers which are computable.

The first two appeal to the relatively “intuitive” quality of Turing’s characterization of computation, the third to vivid exemplifications. Neither is capable of offering anything more than a sufficient condition for “computability”: a surveyable snapshot, language-game style, of what we are inclined to call “computable”.

It is not Turing, but Church and Gödel who later held, in light of Turing’s proof of the equivalence of his machine-characterization of computable function with that of a function definable in Church’s λ-calculus, that Turing had successfully analyzed in general the notion of “computable”, i.e., given necessary and sufficient conditions for the application of the concept of “calculable in a logic” or “step in a formal system of logic”. “Church’s Thesis”, as it came to be called—sometimes even called the “Church-Turing Thesis”—was however not quite Turing’s. This Thesis requires more refinement, and there are open questions remaining about whether or not the “thesis”, or perhaps part of it, is provable at all. By contrast, a language-game can only do so much, and it is not intended to offer necessary and sufficient conditions.

It therefore seems to me to have been ever so slightly unfair for Sieg—an otherwise brilliant reader of Turing in historical context, and in relation to the Hilbert program specifically—to have accused Turing, alongside Church, of “dogmatism” in analyzing computability [41]. Sieg himself provided an axiomatization of the Turing-Computable functions using axioms for a set of dynamical systems which include a crucial constraint, the “locality” condition: there is a finite bound on human computation through there being some finite bound on human attention48.

This mathematico-philosophical move brings Hilbert’s method back to bear on Turing, illustrating a beautiful harmony in the spirit of their works, and giving the lie to the idea that Gödel and Turing “destroyed the Hilbert program”. Sieg is right to hold that the method of axiomatics is, in general, a way to avoid “dogma” about concepts. However, when the question must address—as in Turing’s original context—what it is to axiomatize in Hilbert’s sense, then offering another axiomatization would not have achieved what needed doing.

Turing was clearly fully aware that his characterization has an “intuitive” plausibility that differs from the two extensionally equivalent characterizations yielded by Church’s λ-calculus and the Herbrand-Gödel-Kleene equational characterization of general recursiveness49. In Kleene’s words, Turing’s had the advantage of “aiming directly at the goal” (Kleene [94], p. 61). As Kleene also wrote ([95], p. 49),

Turing’s computability is intrinsically persuasive in the sense that the ideas embodied in it directly support the thesis that the functions encompassed are all for which there are algorithms; λ-definability is not intrinsically persuasive (the thesis using it was supported not by the concept itself but rather by results established about it) and general recursiveness scarcely so (its author Goödel being at the time not at all persuaded)50.

• Turing alone, we could say, gave a surveyable characterization of surveyability, i.e., his characterization of “computable” incorporates our sense of human action into the model and gives us “direct intelligibility” in something like Hilbert’s sense. A Turing Machine has a double face: it is, from one point of view, nothing more than a little formal system, a set of equations. But from another point of view, it lives within a human form of life, and it is we who bring the dynamism and movement into the model of its “step-by-step” “actions”.

Turing explicitly draws out two central aspects of the notion of “surveyability” that are salient here, both closely related, and both at work in Hilbert, Turing and Wittgenstein. First, there is the communicability and repeatability of a Turing computable process (recall Hilbert’s remark that a proof “may be communicated from beginning to end”, comparing it to Wittgenstein [19] [RFM] III §§1ff.). A calculation is impersonal. As Turing says explicitly ([7], §9, II), de-psychologizing his analysis:

We suppose … that the computation is carried out on a tape; but we avoid introducing the “state of mind” by considering a more physical and definite counterpart of it. It is always possible for the computer to break off from his work, to go away and forget all about it. and later to come back and go on with it. If he does this he must leave a note of instructions (written in some standard form) explaining how the work is to be continued. This note is the counterpart of the “state of mind”.

Second, and relatedly, there is the way in which calculation, involving humanly devised symbolic technologies, realizes the human capacity not to “come to blows”, to resolve disputes with certainty. Everything is above board: to quote Wittgenstein, in logic (calculation) nothing is hidden Wittgenstein [51] [PI], §435).

The origin of the term “machine” is, according to one authority, Doric: “that which enables”, a “contrivance”, a “trick”51. Turing captured what calculation-in-a-logic is by characterizing what it is for. He has broken the elements of the technology down into visible parts, holding in mind the point of computability.

To reiterate. According to Mühlhölzer’s careful analysis of the concept of “surveyability” in Wittgenstein’s manuscripts from 1939 ([21], pp. 58-9), there are four elements to the notion:

(1)

Reproducibility: a proof must not be a one-off event, it must be able to be reproduced.

(2)

The reproduction must be an easy task. –We might add, following Turing, that the task must be able to be broken down into “easy”, “surveyable” steps.

(3)

We must be able to decide with certainty whether something is or is not the reproduction of a proof.

(4)

The kind of reproduction resembles the reproduction of a picture, or model.

• And so it is with Turing’s characterization of “computation”. Turing provided a surveyable picture of surveyability itself in just this sense. And it was this computational aspect of formal proof at which Hilbert had been aiming. Turing shows that even though there is one parameter for computation—the Universal Machine can do the work of all Turing machines, including itself—there are mechanical limits to our ability to construct mechanical procedures to resolve disputes in this particular way.

6. Phraseology, Types,“Logicism”: Turing 1948–1954

I am reading Turing in a Wittgensteinian, “ordinary phraseology” spirit, supposing that, as a likely reader of Wittgenstein’s Blue and Brown Books ([61], “[BlB]” and “[BrB]”), or perhaps a hearer of Wittgenstein (Floyd [4]) Turing would have taken in

(a)

the anthropological stance of language-games as logic, pieces of human technology and procedure ([BrB]),

(b)

the extrusion of inner mental states from the analysis of logic as characteristically an embodied action of human beings operating according to fixed procedures with signs ([BlB]), and

(c)

the idea of using humans as machines by giving them short tables of symbols expressing step-by-step commands, i.e., “mechanical” procedures ([BrB])52.

• We need to ask, not whether Turing has actually given us necessary and sufficient conditions for computations—with quantum computing who really knows?—but instead whether his earmarks of “computation” make vivid a concept that has characterized human forms of life for thousands of years.

His argument as I have so far described it has the form: suppose that what a human computation is like, in general, is just this. Then, how could it be that the procedures it could follow were not surveyable? How could it be that such “calculations” would not be reproducible, would not terminate in a certain and unique outcome, would not be impersonal and always verifiable by checking, yielding certain outcomes, resolving human disputes? If you can think of why not, fine. If not, we are done for now with discussion.

On this reading, there may well be a family-resemblance between differing concepts of computability (Wittgenstein [51] [PI], §§65ff): “computable” would be, to use Waismann’s phrase “open-textured”53.

Bringing us back to today, AI may bring us all kinds of results we are not able to easily survey, if we use unsupervised leaning algorithms. But there would still remain a certain conception of human activity at which Hilbert, Turing and later Wittgenstein were aiming. We could work over our procedures with the results of such results, and agree to handle the situation in a variety of differing ways, some of which would involve “explanation”, i.e., making results intelligible, and some of which would simply rely on the spare notion of surveyability defended by Mühlhölzer: the key to the techniques would then be reproducibility, copying in the manner of a picture or model, with confidence, an impersonal and terminating kind of communication.

Turing’s characterization of “computable” has the great advantage that it situates the technology of computation in a dynamic world containing humans and machines, as well as human activities, some conceived of as mechanical, some not. As Wittgenstein emphasized in his mature philosophy, in a kind of anthropological vein, the “techniques” constituted by Turing-computable routines would be applied in settings of human life. This means that the mathematical model has its usefulness only insofar as the physical and social worlds retain certain features they have long exhibited: that signs do not suddenly disappear for no reason, that human beings do not come to blows over whether a surveyable step has been taken, and so on. What Turing shows, and Wittgenstein later emphasizes, is that our concept of computation depends upon features of the surrounding world. The necessities of mathematics ride on the back of numerous contingencies, our forms of life, and these may and will evolve as we embed routines and words in the stream of life in a variety of ways.

The notion of a mathematical “technique” is an important thread throughout Turing’s writings. As we have said, it enters into Wittgenstein’s repertoire only after 193754.

• A beautiful turn toward the notion occurs in the following remark, one of the earliest where Wittgenstein uses it:

The propositions of logic are “laws of thought” “because they express the essence of human thought”—but more correctly: because they express or show the essence, technique (Watson), of thinking. They show what thinking is and also ways of thinking ([19] [RFM] I §133; in original manuscript Wittgenstein [77], p. 396, FF §332).

• This swink ties together Frege, Hilbert and Turing in the following way. With Frege Wittgenstein acknowledges his willingness to conceive of the logical as connected with general features that are constitutive of certain aspects of human thinking, “forms” or “essences” of thought that run through it everywhere, but not in a psychological sense. With Hilbert he will “correct” Frege: Hilbert held that in metamathematics “the formula game is carried out according to certain definite rules, in which the technique of our thinking is expressed” ([97], p. 475). But with Turing—alluding to Alister Watson, whose discussions with Wittgenstein and Turing in the summer of 1937 had so impressed him55—Wittgenstein will correct Hilbert: logic shows us not merely what thinking is, but, now through a plurality of techniques, ways of thinking. And in his anthropological explorations of language-games in Remarks on the Foundations of Mathematics (Wittgenstein [19]) the point is pursued at length.

In particular, in 1939, while Turing was attending his seminar, Wittgenstein deploys the notion of surveyability to recast the light in which we ought to view proofs in Principia Mathematica (Wittgenstein [19] [RFM] III). It is uncontroversial that proofs in Principia quickly become unsurveyable: proofs of relatively simple arithmetical results contain thousands of symbols, making them unusable as calculations. What is the import of this with respect to the very idea of Principia as a “foundation” for mathematics56?

Re-deploying an anthropologically logicized version of Poincaré’s argument against logicism as a reductive foundation of mathematics [see Floyd’s [72]], Wittgenstein picks up again on the Hilbertian idea of surveyability, now adapting it to the point, made in Turing’s work, that there must be many machines, not only one. Strikingly he relies on the notion of a mathematical “technique”, on which he and Turing focused. The Poincaré form of argumentation maintained that in the very setting forth of a formal system, mathematical knowledge is already used in the applications of recursive inference to set forth the formalism, i.e., the language, itself. The reply of Frege, Russell and Hilbert would be that they are not giving an account of how mathematicians think and proceed, psychologically speaking, but are instead spelling out the logical articulation of the content of the theorems, i.e., their ultimate justifications. The use of any particular symbolic system is not part of this. The point is anti-psychologism at the foundations, and, for Hilbert, the metamathematical stance achieves this, as we have seen57.

However, the situation changes once one realizes, after Turing (and Gödel), that although one can define the Universal Turing Machine, one cannot deploy it in a general way, applying it as a single technique for solving problems or computing answers, even if the class of computable functions is “absolute”, and impervious to the choice of particular signature58.

The consequence is that there will never be the kind of “absolute” certainty of which Hilbert wrote, there will only be human certainty, and variegated forms of it at that. Turing is able to give an analysis of the calculational, step-by-step aspect of proof that surmounts reliance on any particular language (the “absoluteness” of the notion of computability, in Gödel’s phrase), but at the price of pluralism about techniques.

Wittgenstein then stressed, in light of Turing, that one must admit what one does. What we do is to employ a variety of techniques with the language of mathematics and logic to explore long, unsurveyable Principia proofs mathematically. This is not, contrary to what is often held, an attempt to refute logicism, but rather to explore what it ultimately comes to59.

In the most quickly appearing cases of unsurveyable proofs in Principia, we would simply count the variables involved, and apply arithmetic. In more complex cases, we would develop further techniques of representation and apply these. The point—just as Mühlhölzer’s minimalist construal of surveyability states—is not necessarily immediate intelligibility (such may well emerge, of course), but the preservation of the kind of certainty and termination at which proof aims, in practice. The price, as Wittgenstein wrote, is that now mathematics must be admitted to comprise a “colorful mix of techniques of proof” (Wittgenstein [19] [RFM] I §§46-48)60. And this means that the sense in which mathematics is “applied” varies with the evolution of human notations and purposes61.

In 1944/45 Turing [38] presented a theory of “types” with an eye on developing layers of such techniques. His idea was to look toward ordinary scientific and mathematical “phraseology” in developing higher-level programming languages and “types” (as we would call them today)62.

We should not be surprised to learn that he was inspired in this by discussions with Wittgenstein. He wrote,

The statement of the type principle given below was suggested by lectures of Wittgenstein, but its shortcomings should not be laid at his door ([38], p. 247).

What we see here is Turing’s development of the Hilbertian ideal of surveyability in light of the programming languages that, as he insisted, would do as much for the use of computing in mathematics as the development of hardware63.

Turing was clear right at the outset that he was not quarreling with logicism, but exploring what it could give rise to:

  It has long been recognised that mathematics and logic are virtually the same and that they may be expected to merge imperceptibly into one another. Actually this merging process has not gone at all far, and mathematics has profited very little from researches in symbolic logic. The chief reasons for this seem to be a lack of liaison between the logician and the mathematician-in-the-street. Symbolic logic is a very alarming mouthful for most mathematicians, and the logicians are not very much interested in making it more palatable. It seems however that symbolic logic has a number of small lessons for the mathematician which may be taught without it being necessary for him to learn very much of symbolic logic.

  In particular it seems that symbolic logic will help the mathematicians to improve their notation and phraseology, which are at present exceedingly unsystematic, and constitute a definite handicap both to the would-be-learner and to the writer who is unable to express ideas because the necessary notation for expressing them is not widely known. By notation I do not of course refer to such trivial questions as whether pressure should be denoted by p or P, but deeper ones such as whether we should say ‘the function f (z) of z’ or ‘the function f ’ ([38], p. 245).

• Philosophically Turing is realizing the Hilbert ideal of metamathematics, but in a newly dynamical way. The key would be to reflect on how notations could be developed that would provide surveyability. Here, a form of intelligibility does enter, but it is procedural: the point is to help the human being dealing with computational proofs formulate and discuss, so to speak “metamathematically”, the situations that arise, a kind of “programme”.

Turing’s suggestion for this was drawn out of the kind of ordinary language philosophy Wittgenstein had presented in his lectures. We should conduct, Turing wrote,

(i) an extensive examination of current mathematical, physical and engineering books and papers with a view toward listing all commonly used forms of notation.

(ii) Examine them to see what they really mean. This will usually involve statements of various implicit understandings as between writer and reader. But the laying down of a code of minimum requirements for possible notations should be exceedingly mild, avoiding the straightjacket of a logical notation.

(iii) Laying down a code of minimum requirements for desirable notations. The requirements should be exceedingly mild… ([38], p. 245).

• He also emphasized the need to make the deduction theorem central and to make “very clear statements of the fundamental nature of the symbols” ([38], p. 245). He adds, echoing Wittgenstein’s idea about the colorful mix of techniques, that

It would not be advisable to let the reform [of notation] take the form of a cast-iron logical system into which all the mathematics of the future are to be expressed. No democratic mathematical community would stand for such an idea, nor would it be desirable( [38], p. 245).

• Here we see a kind of dynamic, evolutionary attitude toward the role of notations and languages in human being’s implementation of Hilbert’s idea of metamathematics. This leads to the pluralism of techniques on which Turing’s 1939 discussions with Wittgenstein focused. It also points toward what Turing called the inevitable need for “common sense” (i.e., non-algorithmic uses of human “intuitions”, or hunches) in addition to “reason” (i.e., formal routines) in mathematics64.

This evolutionary attitude toward the development of notations and language was of great philosophical importance to Turing. First, we note his insistence on the importance of surveyability for the very possibility of proceeding with proof and computation at all. In his address to the London Mathematical Society [106], he put the point humorously:

The Masters [i.e., mathematicians] are liable to get replaced because as soon as any technique becomes at all stereotyped it becomes possible to devise a system of instruction tables which will enable the electronic computer to do it for itself. It may happen however that the masters will refuse to do this. They may be unwilling to let their jobs be stolen from them in this way. In that case they would surround the whole of their work with mystery and make excuses, couched in well-chosen gibberish, whenever any dangerous suggestions were made. I think that a reaction of this kind is a very real danger ([106], 496).

• Resonating with Wittgenstein’s remarks on certainty and surveyability, Turing’s point is that nonsense, the mucking up of surveyability in the use of language, would undercut the very possibility, not only of using computations to further mathematical research, but of mathematics itself. The point was of course wholly prescient, as we look at the problems of nonsense and disinformation at work in the world wide web.

A final Hilbertian echo in Turing concerns Hilbert’s more global concerns with culture as a whole, and the role of mathematics in it. In his 1930 address in Königsberg, a philosophical meditation on the possibility of a harmony between thought and nature, Hilbert had written that

The instrument which mediates between theory and practice, between thought and observation, is mathematics; it builds the connecting bridges, and makes them ever sounder. Thus it happens that our entire modern culture, in so far as it rests on the penetration and utilization of nature, has its foundation in mathematics ([68], §22, p. 1162)65.

Hilbert’s entire lecture should be compared with Turing’s bold and far-thinking suggestions about the future of computation in his report to the National Physical Laboratory of 1948, the founding document of artificial intelligence [107]. Turing speculates there about the future of “intelligent machinery”, hypothesizing that the very idea of “intelligence” involves appreciating the differences among different kinds of search. First, he rightly predicts that what he calls “intellectual searches” for algorithms will preoccupy scientists increasingly in the future ([107], p. 516). Next, in light of Watson and Crick, he predicts the development of computational biology:

There is the genetical or evolutionary search by which a combination of genes is looked for, the criterion being survival value. The remarkable success of this search confirms to some extent the idea that intellectual activity consists mainly of various kinds of search ([107], p. 516).

• This should be compared with Hilbert’s synthesis of all the sciences in his 1930, which also included biology ([68], §8, p. 1159).

Finally, Turing emphasizes the human evolutionary aspect of the development of mathematics. Here, we see the echoes with Hilbert’s general remarks on culture, as well as Wittgenstein’s anthropologized remarks about human forms of life and the place of calculations within them. Turing writes ([107], p. 516),

The remaining form of search is what I should like to call the “Cultural Search‘… [T]he isolated man does not develop any intellectual power. It is necessary for him to be immersed in an environment of other men, whose techniques he absorbs during the first 20 years of his life. He may then perhaps do a little research of his own and make a very few discoveries which are passed on to other men. From this point of view the search for new techniques must be regarded as carried out by the human community as a whole, rather than by individuals.

We see how important the “cultural” aspects of surveyability become for Turing, as he gazes into the future. The whole is an adaptation of Hilbert’s and Wittgenstein’s work in the direction of our present world.