2 Turing’s Computability

Many philosophical accounts of computing subscribe, in one way or another, to the notion that “to compute” is to follow or to execute an effective procedure or an algorithm. I use the terms effective computation, effective calculation, and algorithmic computation interchangeably in reference to any computation (calculation) performed by means of an effective procedure or an algorithm of this sort (in Chapter 3, however, I consider drawing a distinction between effective procedures and algorithms). Similarly, a function (of positive numbers) is deemed effectively computable (calculable) if, as Church puts it, “there exists an algorithm for the calculation of its values” (1936a: 102). In the following chapters, my aim is to cut through the tight relationship between algorithms and physical computation. The first step, made in this chapter, is to separate the notions of algorithmic computation, as studied by Church, Turing, and the other founders of computability, and that of machine computation (at this point I will use the more general term machine; however, I will gradually disambiguate it to distinguish between physical systems and other kinds of machines).

This chapter focuses on Turing’s analysis, which reduces effective computability to Turing machine computability (Turing 1936: sec. 9). Turing’s analysis is of interest for several reasons. First, Turing provided a precise characterization of what is effectively computable (in terms of Turing machine computability). Second, while there were others who offered a precise characterization of effective computability around the same time, Turing’s characterization stands out in that it involves an analysis of the process of computing. Third, Turing introduced the notion of an automatic machine (now known as a Turing machine).¹ This notion lies at the heart of computability theory and automata theory even today. Turing also introduced the notion of a universal Turing machine: a Turing machine that can simulate the operations of any particular Turing machine, and can thereby compute any function that is computable by any Turing machine. This notion has inspired the development of general-purpose digital electronic computers that now dominate virtually every activity in daily life.²

Turing’s ingenious work richly deserves the appreciation it has garnered. However, I wish to draw attention to a major limitation of his analysis. As others have already noted, Turing analyzed a restrictive class of computations—namely, the calculations that can be carried out by a human computer, an idealized human who calculates the values of a function by using (perhaps) a pencil and paper (e.g., Kleene 1952; Gandy 1988; Sieg 1994; Copeland 1997). While this analysis is of immense theoretical and practical importance, it cannot be taken to be the basis of machine computation.

This chapter proceeds as follows. First, I place Turing’s 1936 paper in its historical context (Section 2.1), then give an outline of his analysis (Section 2.2). Next, I digress to engage in a discussion of the nature of human computation (Section 2.3). Finally, I discuss the scope of Turing’s analysis with respect to machine computation (Section 2.4), arguing that the constraints Turing imposes on effective computation are too restrictive to be applied to computation more generally.

Some guidance for the reader: The material in Sections 2.1 and 2.2 certainly deserves a more fully developed review. I use the notes to expand on certain pertinent points and to suggest further reading. I recommend Sieg (2009), who provides an extensive discussion of much of the material presented in Sections 2.1 and 2.2, and Copeland (2004b), who provides a detailed guide to the material on Turing presented in Section 2.2. Much of what I say in these sections relies on their work. Those who are less interested in the historical and technical background of computability can skip these sections, reading only the summarizing paragraphs of each section. Readers who are less interested in the discussion pertaining to the nature of human computation are advised to skip Sections 2.3.1–2.3.3.

Four pioneering papers were published in 1936, each of which provides a precise mathematical characterization of effective computability. Alonzo Church (1936a) characterized the effectively computable functions (over the positives) in terms of lambda-definability—an undertaking he began in the early 1930s (Church 1933), and which was carried on by Stephen Kleene and Barkley Rosser. Kleene (1936) characterized the general recursive functions, based on the expansion of primitive recursiveness by Herbrand (1931) and Gödel (1934).³ Emil Post (1936) in New York described “finite combinatory processes” carried out by a “problem solver or worker” (p. 289). Meanwhile, young Alan Turing in Cambridge provided a somewhat similar characterization, but offered the precise characterization in terms of Turing machines. Although Turing was referring to the computability of real numbers, he remarked that “it is almost equally easy to define and investigate computable functions” (p. 58) of countable domains.⁴ All these precise characterizations were quickly proven to be extensionally equivalent, as they all define the same class of functions.⁵

Church and Turing—and to some degree Post—formulated versions of what is now known as the Church-Turing thesis (CTT). Church’s classic formulation was as follows:

We now define the notion, already discussed, of an effectively calculable function of positive integers by identifying it with the notion of a recursive function of positive integers (or of a λ-definable function of positive integers). (Church 1936a: 100)

Kleene coined the term thesis and formulated the thesis as follows:

Thesis I. Every effectively calculable function (effectively decidable predicate) is general recursive. (Kleene 1943: 60)⁶

In this book, we will adhere to Kleene’s formulation. The statement is called a “thesis” because it links a pre-theoretical notion—that of effective (algorithmic) calculability—with the precise notion of general recursiveness, or Turing machine computability.⁷ Arguably, due to the pre-theoretical notion, such a statement is not subject to mathematical proof.⁸ But we will leave aside questions of provability and focus on what is meant by “effective computation.” To address this, we should first explicate the motives that prompted the attempts to characterize computability, which culminated in the so-called 1936 Affair.

The use of algorithms in solving mathematical problems goes back at least as far as Euclid. Its use as a method of proof is found in Descartes, and its association with formal proof is noted by Leibniz. But algorithms came to the fore of modern mathematics only toward the end of the nineteenth century and the early twentieth. This development had two related sources. The first was the publication of various foundational works in mathematics that explored the concept of the algorithm, starting with Frege and culminating in Hilbert’s finitistic program in the 1920s. Although there are substantive differences between these enterprises, they share one core idea, which is to provide mathematics with epistemological foundations by means of logical calculus.⁹ The term calculus refers to a system of logical axioms and inference rules whose constructions are “effective”—namely, that there is an algorithm (effective procedure) that one can use to decide whether or not a string of symbols is a (formal) proof or derivation. In the 1920s, Hilbert also required that there be a meta-theoretic consistency proof of the axiomatic system, notably of the one (supposedly) embedding number theory.¹⁰ The demand was that the meta-theoretic proofs exploit only finitistic means, of which effective procedures were considered to be a major, if not the only, resource. As is well known, the prospects of Hilbert’s program were dashed with the publication of Gödel’s incompleteness results in 1931.¹¹

The other source was the growing number of decision problems that attracted mathematicians.¹² The most pertinent problem was the Entscheidungsproblem (“decision problem”), which concerned the decidability of logical systems. It was raised by Hilbert and his students during the 1920s; Hilbert and Ackermann (1928) specifically introduced the Entscheidungsproblem with respect to the restricted functional calculus (first-order predicate logic), describing it as the “most fundamental problem of mathematical logic.”¹³ The problem asked whether there was an algorithm for deciding whether or not a formula in the calculus is derivable;¹⁴ such an algorithm, it was hoped, would provide a decision procedure for the provability of any mathematical sentence.¹⁵  Turing (1936) and Church (1936a, 1936b) aimed at this problem in 1936, and both proved, independently of each other, that there was no such algorithm for the derivability (or validity) of any formula in first-order predicate logic.

Before Church and Turing, however, there was no agreement on the precise definition of effective computability, and therefore of decidability. Indeed, there was not even a unified terminology. In formulating his famous 10th problem—of deciding any Diophantine equation with rational coefficients—Hilbert refers to “a process according to which it can be determined by a finite number of operations whether the equation is solvable in rational integers” (1902: 458). Church, as we have seen, used the term effective calculation, as well as effectively calculable function (1933, 1936a). Gödel, who used the terms mechanical procedure and finite procedure, defined the procedure’s properties in the context of formal systems.¹⁶ The property of being mechanical was spelled out in Gödel’s 1933 address to the Mathematical Association of America, “The Present Situation in the Foundations of Mathematics.” Gödel opened the address with a rough characterization of formal systems:

The outstanding feature of the rules of inference being that they are purely formal, i.e., refer only to the outward structure of the formulas, not to their meaning, so that they could be applied by someone who knew nothing about mathematics, or by a machine (p. 45).

We discussed this property in Chapter 1. The property of being finite is stressed in Gödel’s Princeton 1934 address, where he characterized a “formal mathematical system” as follows:

We require that the rules of inference, and the definitions of meaningful formulas and axioms, be constructive; that is, for each rule of inference there shall be a finite procedure for determining whether a given formula B is an immediate consequence (by that rule) of given formulas A₁, . . . , A_n, and there shall be a finite procedure for determining whether a given formula A is a meaningful formula or an axiom. (p. 346)

At this point, in 1934, Gödel understood the finite procedures to be the (primitive) recursive ones but did not assert that the latter was a precise definition of the former.¹⁷

Given the centrality of effective computability in logic and mathematics, it is perhaps surprising that the attempts to characterize it were not as extensive prior to the 1930s. In any event, this situation changed with the publication of the incompleteness results (Gödel 1931), which shattered the collective optimism about certain decidability questions, and, consequently, called for a more accurate definition of the notion of effective computability. As Martin Davis explains, “A positive solution to a decision problem consists of giving an algorithm for solving it; a negative solution consists of showing that no algorithm for solving the problem exists” (1958: xvi). When the problem has a positive solution, we “simply” have to find a pertinent algorithm for it—namely, an algorithm that solves the problem (we then might have to explain, or even prove, why there is a match between the proposed algorithm and the problem). When the problem has a negative solution, however, we must show that no algorithm solves it, and this already calls for a precise characterization of the notion of algorithm.

Two issues about undecidability are often mentioned in the context of the search for the precise characterization. One is the generality of the incompleteness results. The results were proved with respect to the system P and its extensions. The system P is “essentially the system obtained when the logic of PM [Principia Mathematica] is superposed upon the Peano axioms” (Gödel 1931: 151). The extensions are the “ω-consistent systems that result from P when recursively definable classes of axioms are added” (p. 185 n. 53). At the time, it was still an open question whether the undecidability results apply to every formal system; the question, in other words, was whether the recursively definable classes encompassed the relevant, effectively definable classes. But to determine the answer to this question, one would need a precise definition of the latter. Gödel himself wrote the following on this point:

When I first published my paper about undecidable propositions the result could not be pronounced in this generality, because for the notions of mechanical procedure and of formal system no mathematically satisfactory definition had been given at that time. This gap has since been filled by Herbrand, Church and Turing. (193?: 166)¹⁸

Subsequently in that paper, and many times after, Gödel attributed the most convincing characterization of mechanical procedure to Turing. In a 1963 note added to the 1931 paper, Gödel wrote that Turing’s characterization established the generality of the incompleteness results:

In consequence of later advances, in particular of the fact that due to A. M. Turing’s work a precise and unquestionably adequate definition of the general notion of formal system can now be given, a completely general version of Theorems VI and XI [the incompleteness results] is now possible. That is, it can be proved rigorously that in every consistent formal system that contains a certain amount of finitary number theory there exist undecidable arithmetic propositions and that, moreover, the consistency of any such system cannot be proved in the system. (1963: 195)

In a paragraph in the 1964 postscript to his 1934 paper, Gödel adds that “Turing’s work gives an analysis of the concept of ‘mechanical procedure’ (alias ‘algorithm’ or ‘computation procedure’ or ‘finite combinatorial procedure’). This concept is shown to be equivalent with that of a ‘Turing machine’ ” (1964: 369–370).

The other problem is the Entscheidungsproblem. Given incompleteness, it was very likely to be undecidable.¹⁹ But, again: to demonstrate unsolvability, one must show that no effective (algorithmic) procedure, of which there are infinitely many, solves the problem. One must therefore come up with a precise definition of effective computability. As previously noted, Church and Turing aimed to do just that. Church eventually proved the unsolvability of the Entscheidungsproblem by means of the notions of lambda-definability and recursiveness. Turing came up with a different approach: he reduced the concept of an algorithmic procedure to that of a Turing machine, then proved that no Turing machine could solve the Entscheidungsproblem.

In summary: We have briefly reviewed the fascinating events within the world of logic and mathematics that led to the precise mathematical characterization of effective computability. In this historical context, the characterization of computability is tightly linked to the development of rigorous definitions for the notions of formal system and decision procedure. These were required in order to establish central undecidability results—in particular, the generality of Gödel’s incompleteness results and the insolvability of Hilbert and Ackermann’s Entscheidungsproblem.

The Church-Turing thesis asserts that every effectively computable function is a general recursive function (or Turing machine computable). But what are the grounds for this thesis? In his book, Kleene (1952) lists four kinds of justification. The first two are the arguments of confluence and of non-refutation, which are prevalent in current textbooks in computability, logic, and automata theory. The confluence argument states that many characterizations of computation that differ in their goals, approaches, and details nonetheless encompass the same class of computable functions. As we have seen, the confluence of four such characterizations appeared in 1936, and many more characterizations have followed.²⁰ The non-refutation argument states that the thesis, though refutable, has not been refuted despite the many efforts and attempts to find a counterexample.²¹ Both arguments are of an inductive nature: the more examples you have (either of yet another precise characterization of computability, or of yet another computable function that turns out to be recursive), the more the thesis is confirmed. Indeed, these arguments strengthen the impression that the thesis is not subject to mathematical proof.

The other two arguments are more direct, in that they deal, in one way or another, with the process of computing.²² One argument, put forward by Church (1936a: 100–102), is known as the step-by-step argument.²³ Using Gödel’s notion of representability (Gödel 1931; Kleene 1936), Church characterizes an effectively computable function as one that is calculable in logic. As he puts it:

Let us call a function F of one positive integer calculable within the logic if there exists an expression f in the logic such that {f}(μ) = ν is a theorem when and only when F(m) = n is true, μ and ν being the expressions which stand for the positive integers m and n. (1936a: 101)

The rationale behind this characterization is the tight relationship between effective computation and logical derivation. A function is (intentionally) effectively computable only if there is a derivation of the corresponding (“representing”) logical formula (“expression”), when we replace the number values m and n with the corresponding constants m and n. This characterization highlights the close kinship that existed between formal systems and effective computability at the time. On the one hand, a formal system is characterized in terms of effective computability; on the other, effective computability is defined in terms of formal derivability. A variant of this characterization appears in Turing (1936), Hilbert and Bernays (1939), Church (1941: 41), and Gödel (1946).²⁴ Given this characterization, Church proceeds to show that if each step of the derivation is general recursive, then the defined function is recursive as well. What is left open, however, is the assumption that these basic steps must be recursive.²⁵ As Sieg points out, this argument is “semicircular in the sense that he [Church] assumed without good reason that the necessarily elementary calculation steps have to be recursive” (2006: 193).

Our focus here, however, is Turing’s argument for the thesis, known as Turing’s analysis. The argument is explicated by Kleene (1952), who refers to the conclusion as Turing’s thesis (p. 376). For many years, this argument was not well known, so logic and computer science textbooks, even today, often ignore it.²⁶ One notable exception was Gödel (193?, 1951, 1964; Wang 1974), who said that Turing’s analysis produces a “correct and unique” definition of “the concept of mechanical” in terms of “the sharp concept of ‘performable by a Turing machine’ ”—and that it is “absolutely impossible that anybody who understands the question and knows Turing’s definition should decide for a different concept” (Wang 1974: 84).²⁷ But Gödel does not explain here, or elsewhere, why the analysis is so convincing.²⁸ Turing’s analysis has been fully appreciated more recently by Gandy (1988), Sieg (1994), and Copeland (2004b). Gandy (1988) and Soare (1996) even use it to prove the Church-Turing thesis.²⁹ Here, I will only provide an outline.³⁰

Turing begins his 1936 paper by stating that “the ‘computable’ numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means” (1936: 58). He proposes an explicit definition of computability with (Turing) machine computability, arguing that its “justification lies in the fact that the human memory is necessarily limited” (p. 59). Turing then compares “a man in the process of computing a real number to a machine which is only capable of a finite number of conditions [configurations]” (p. 59). After an informal exposition of the machine’s operations, Turing comments that it is his “contention that these operations include all those which are used in the computation of a number” (p. 60).

In section 9, Turing returns to justify the identification of (effective) computability with Turing machine computability. He provides three arguments, remarking that “all arguments which can be given are bound to be, fundamentally, appeals to intuition, and for this reason rather unsatisfactory mathematically” (p. 74). The first argument, discussed here, is a “direct appeal to intuition” and “is only an elaboration of the ideas of [section] 1” (p. 75). It is presented in part I of section 9, and then a modification is added in part III. The second argument, in part II, is a variant of the step-by-step argument noted previously. The third argument, in section 10, consists of “examples of large classes of numbers which are computable” (p. 75).

Turing’s analysis (i.e., the first argument) rests on two ingenious ideas. One is that in order to characterize the computable functions (or numbers, or relations) we should focus on the computational processes: “The real question at issue is ‘What are the possible processes which can be carried out in computing a number?’ ” (p. 74). This idea is supported by the fact that the computable functions are the products of certain computational (i.e., finite and mechanical) processes; thus, if we want to exhaust the set of computational functions, we must be clear about the set of processes that lead to those functions.

Turing puts forward three underlying assumptions about these processes. One is that they are symbolic processes, in the sense of writing and erasing symbols: “Computing is normally done by writing certain symbols on paper” (p. 75). He adds that we can assume that the paper is one-dimensional (that is, like a tape) and divided into squares, although this is not essential for the argument. A second assumption is that the process is step-wise, in that it consists of a sequence of steps; each such step involves a change in symbolic configurations. The number of steps in a single run is finite but unbounded when the function is defined for a certain input; otherwise, it consists of infinitely many steps (“not halting”). A third assumption is that there is an agent carrying out this computation; arguably, this agent is a human computer. Turing says that “we may compare a man in the process of computing a real number to a machine which is only capable of a finite number of conditions” (p. 59). For now, I will use the more neutral term the computer for the computing agent and discuss its relationship with human computers in Section 2.3.

The first idea, then, is to focus on processes. The problem with this direction, however, is that it is unclear how one might characterize all possible processes, given that there are an infinite number of them. Turing’s truly wonderful (second) idea is to formulate a finite set of restrictive constraints that apply to each step of each process. These constraints should have two properties. The first is that they must be general enough and thus their truth is almost self-evident. The second property is that a Turing machine can mimic the operations restricted by these constraints. We can think of these constraints as “axioms of computability.”³¹

Overall, the analysis can be described as a two-premise argument (Shagrir 2002):

Premise 1: “The computer” operates under the restrictive conditions 1–5 (to be specified in what follows).

Premise 2 (“Turing’s theorem”): Any function that can be computed by a(ny) computer that is restricted by conditions 1–5 is Turing machine computable.

Conclusion (“Turing’s thesis”): Any function that can be computed by “the computer” is Turing machine computable.

Turing (somewhat informally) enumerates several constraints that can be summed up by the following restrictive conditions:

He then formulates boundedness conditions on each of the two determining factors—namely, the observed symbols and states of mind:

There are certain “simple operations” (behavior) that the computer may perform at any given moment (computation step): a change in the symbols written on the tape, a change of the observed squares, and a change in state of mind. Turing then applies boundedness conditions on the first two kinds of operations (assuming that the number of states of mind is bounded):

Let us examine the rationale behind these constraints a little more closely. Turing does not give reasons for the first condition: he apparently takes it to be a sine qua non of the concept of effective computation. The reason for the second condition, he says, is that the computer can observe only a bounded region, and that there is a lower bound on the size of the symbols: “If we were to allow an infinity of symbols, then there would be symbols differing to an arbitrarily small extent” (p. 75). Hence, presumably, “the computer” cannot tell one from another. As for the third condition, Turing says that “the reasons for this are of the same character as those which restrict the number of symbols. If we admitted an infinity of states of mind, some of them will be ‘arbitrarily close’ and will be confused” (pp. 75–76). Following this somewhat obscure statement, Turing stresses that the restriction regarding states of mind “is not one which seriously affects computation,” and that we can always replace states of mind with “writing more symbols on the tape” (p. 76). In part III, Turing suggests avoiding states of mind altogether “by considering a more physical and definite counterpart” (p. 79) such as written symbolic configurations.

At first glance, the fourth condition might appear too restrictive, as we might be able to change more than one symbol at a time. But it is apparent that we can extend the condition as long as “one symbol” is replaced with another number that serves as a fixed limit on the number of symbols that can be altered at any one moment. Following Turing, we may assume, without loss of generality, “that the squares whose symbols are changed are always ‘observed’ squares” (p. 76). As for the fifth condition, Turing says that it is reasonable to suppose that the distance between current and previously observed squares “does not exceed a certain fixed amount” (p. 76).

It is often said that a Turing machine is a model of a computer, arguably a human computer.³² We can now see that this statement is imprecise. A Turing machine is a letter machine: at each point it “observes” only one square on the tape. “The computer” might observe more than that (Figure 2.1). Other properties of a Turing machine are also more restrictive. The machine can perform precisely three kinds of bounded operations at each step: it can change the observed symbol alone; it can change the observed square (and symbol) that is either immediately to the left or immediately to the right of the current square; and it can change the state of the finite program. “The computer,” however, might change something other than the observed symbol, shift eyes to non-adjacent squares, and so forth. A Turing machine is therefore more restrictive than “the computer”: its restrictive conditions are tighter than conditions 1–5.

The aim of the second premise in the analysis is to demonstrate that the restrictive conditions 1–5 are nonetheless bounded by the Turing limit—namely, that the operations performed by any computing agent that satisfies conditions 1–5 can be reduced to a finite series of successive operations performed by a Turing machine. A change in a bounded region of symbols can be reduced to a (possible) change in each of the single symbols that make up this region, and a bounded change of the observed square can be reduced to a sequence of shifts of one observed square. Turing provides an outline of the reduction, and Kleene (1952) and others provide more detailed demonstrations. Based on Gandy’s insights, Sieg (2002) formulates the conditions in formal terms as mathematical axioms (we will return to these points in Section 2.3.2).

To summarize the argument (of Turing’s analysis): the first premise encapsulates a novel characterization of effective computation—namely (to put it in Gödel’s terms), a characterization of computation as a mechanical and finite procedure. The mechanical part is described in terms of the operations on symbolic configurations; the operations refer to the form (“syntax”) of the symbols, while making no direct reference to semantic properties. The finite part is captured in the terms of the conditions 1–5, which are explications of the finite means. The second premise states that every function that is effectively computable is also Turing machine computable. The conclusion (“Turing’s thesis”) is that the effectively computable functions—that is, those functions computable by “the computer”—are Turing machine computable.

The claim that Turing’s analysis essentially applies to human computers was underscored by his student Robin Gandy.³³ In his 1980 paper on computability, Gandy wrote:

Both Church and Turing had in mind calculation by an abstract human being using some mechanical aids (such as paper and pencil). The word “abstract” indicates that the argument makes no appeal to the existence of practical limits on time and space. (1980: 123–124)

In his historical 1988 paper, Gandy once again emphasized that Turing’s “computability” relates to calculations by an ideal human, and that Turing “makes no reference whatsoever to calculating machines” (Gandy 1988: 83). In Gandy’s posthumously published introduction to the 1936 paper, he wrote that Turing “considers the actions of an abstract human being who is making a calculation” (2001: 11).

There are several reasons to support this human-oriented line of interpretation. One is the fact that the computers at the time of Turing’s statements were humans, not machines: “It is not surprising that Turing does not mention machines. Numerical calculation in 1936 was carried out by human beings” (Gandy 2001: 12).³⁴ The first programmable, general-purpose computers were only manufactured in the 1940s. A second reason is the highly anthropomorphic language that Turing uses to describe “the computer.” “Turing’s analysis is quite explicitly concerned with calculations performed by a human being; there is no reference to machines other than those which he introduces to imitate the actions of a human computor” (Gandy 2001: 12). Third, the analysis essentially exploits the limitations of human computers, not of machines in general: “Turing’s analysis of computation by a human being does not apply directly to mechanical devices” (Gandy 1980: 123), and “There are crucial steps in Turing’s analysis where he appeals to the fact that the calculation is being carried out by a human being” (p. 124).

A decisive point in favor of the human-oriented interpretation, in my view, is that it places Turing’s pioneering work on effective computability in its appropriate historical and philosophical context—namely, the role of effective computation in logic and mathematics (as discussed in Section 2.1). In this regard, the notion of effective procedure is tightly connected to us—the human computers. The notions of decidability, formal derivability, and formal systems are closely linked to what a human can or cannot do, at least in principle, when using an effective procedure. This does not mean that a machine cannot compute effectively, but rather that the benchmark of what counts as effectively computable is the human computer: something is effectively computable only if it can be computed by an idealized human being. To ignore the human connection is to miss a key and distinct aspect of the notion of effective computation in the context of logic and mathematics.

I would like to stress, however, that my main claim about Turing’s analysis does not depend on whether Turing, Church, and other pioneers of computability were essentially referring to human calculation or not. Following Gandy, my claim (to be elaborated in Section 2.4) is that Turing’s finiteness conditions are too restrictive with respect to machine computation. The human interpretation explains why Turing formulated finiteness conditions that do not apply to machine computation in general (the explanation being that Turing had human calculation rather than machine computation in mind). Nevertheless, the human interpretation itself invokes real issues about the nature of the human computer that have yet to be resolved. A full discussion of these issues is beyond the scope of the present work; for now, I will make a few pertinent comments that will later be expanded in the context of physical computation (the impatient reader can skip to Section 2.4).

There appears to be a disparity between algorithms (i.e., effective procedures), Turing machines, and computable functions—all of which are abstract, mathematical objects—and human computers, which are concrete or non-abstract.³⁵ This disparity is evident in the first premise of the analysis, where “the computer” equates the notion of algorithm with that of calculation. It also arises in the second premise, where the restrictions on computers are compared with those of Turing machines.

One way to reconcile this disparity was implicitly suggested by Gandy (1980), and more explicitly by Sieg (2008, 2009). They think about the restrictive conditions 1–5 as mathematical constraints or axioms that abstract from the limitations imposed on the human computer. The idea is that these mathematical axioms precisely capture the notion of algorithm (or effective procedure, or effective/algorithmic computation). This is because these conditions model a human computer. The human computer, one might say, is an implementation or concretization of the mathematical axioms (and by extension, human calculation is an implementation of a specific algorithm).³⁶

One advantage of this approach is that it does not limit effective computation to human computers, but rather allows it to be executed by non-humans as well—or even by machines. This is simply because the mathematical axioms can be applied to (or model or implemented by) a variety of different systems. The systems in question may be tangible (e.g., human computers) or abstract (e.g., Turing machines); they may be human or non-human. In other words, the axioms define a particular class of (computing) systems—namely, those that satisfy the restrictions, irrespective of whether or not they are human. They can be seen as defining a certain kind of mathematical scheme (or set of abstract computers) that is applied to different systems (which can be seen as “implementing” them)—one of which is the human computer. However, the notion of algorithm is essentially tied to human calculation, because this mathematical scheme is abstracted from a human computer. Once abstracted, it can be applied to many other kinds of computing agents that are also said to compute effectively.

Another advantage of this approach is that it treats the second premise in Turing’s analysis as a mathematical theorem. This premise links two different mathematical notions: the class of systems defined by the mathematical axioms 1–5, and that of the Turing machine. This is perhaps what Gandy meant when he said that Turing had proved a theorem (1980: 124) and called it “Turing’s theorem” (Gandy 1988: 83; Sieg 1994).

One may rightly argue that no real human can have unlimited time and space to complete the computation; in this sense, the restrictive conditions are perhaps too liberal.³⁷ But the human computer is an idealized entity.³⁸ The idealization can take one of two very different forms. One is an idealization in terms of the practical, real-world limitations of space, time, and material aids (e.g., pencils and paper). In principle, the human can use as much time and space as it takes to complete the computation. One might define this kind of idealization in terms of the competence/performance distinction (Chomsky 1965): performance is always limited by the amount of paper potentially available in the universe and by a given time span (e.g., the lifetime of a person, planet, or universe). Competence, however, goes beyond this: under ideal conditions, the human could, in principle, transcend these limitations. This kind of idealization appears to be required if computation is associated with surveyability—since there is no upper limit on the length of a formal proof, other than that it must be finite.³⁹

The second sort of idealization concerns normativity. When the human follows an algorithm for addition, the assumption is that he or she is following it “properly”—calculation mistakes, inattention, forgetfulness, distractions, and so forth are immaterial to the computation process. These mistakes are of a different kind from the previous ones. In the preceding cases, real humans will never be able to add very large numbers: they will die or run out of material aids beforehand. This is not the claim here. When asked to calculate “67 + 58,” even in the actual world, the human computer usually replies “125.” The problem is that occasionally the human—when tired, distracted, or the like—might sometimes reply “126.” Idealization is therefore required to tell which reply is the correct one. Here too, one can describe the difference in terms of the competence/performance distinction. Competence is associated with the correct application of the (specific) set of instructions, whereas performance is associated with the actual application, which might involve all kinds of faults.⁴⁰

The restrictive conditions 1–5, as their name suggests, restrict human computers to the means that they can use, or the resources they are allowed to use.⁴¹ But what does it mean to say that the human computer is allowed to use these resources? Who allows it? And why is it that the human is allowed to use only computational resources that are limited to these restrictive conditions? Why these restrictive conditions and not others? In examining how others have addressed these issues (more implicitly than explicitly), we find two very different answers to the questions, which we have labeled as the cognitive and non-cognitive approaches (Copeland and Shagrir 2013).

According to the cognitive approach, the (permitted) restrictive conditions 1–5 essentially reflect the upper limitations on humans’ cognitive capacities—“essentially” in the sense that the correctness of the restrictive conditions is grounded in, or is justified by, those capacities. In this cognitive approach, the truth of the first premise in Turing’s analysis (that the human computer operates under the restrictive conditions 1–5) depends on empirical facts about human cognition. The claim, however, is not that the restrictive conditions reflect the limitations of general human mental processes, or not even of those mental processes involved in mathematical thinking in general.⁴² Rather, the claim is that they reflect the limitations of the cognitive capacities involved in the process of calculation, or the faculty of calculation (which does not necessarily refer to a designed cognitive module, but to the capacities involved in calculating the values of functions or numbers).⁴³

According to the non-cognitive approach, the restrictive conditions 1–5 need not reflect the limitations of the human condition. Whether or not they reflect the upper limits of the faculty of calculation is irrelevant to the analysis of computability. Conditions 1–5 are simply an explication of the concept of effective computation as it is used and functions in a certain context. The relevant context is that of logic and mathematics, in which the concept is tied to decision procedures, formal systems, and generating epistemically reliable, trustworthy results.

The cognitivist would agree, of course, that Turing explicated the “axioms of computability” by analyzing the concept of human computability as it is properly used and as it functions in the discourse of logic and mathematics. However, the cognitivist would argue that in addition to explicating the conditions, Turing grounds or justifies their correctness on the limitations of human cognitive-calculative capacities. In contrast, the non-cognitivist would maintain that the analysis offers no such justification for the conditions. In fact, according to the non-cognitivist, a call for further justification has no place whatsoever in the analysis of computability.

The difference between the two approaches can be made clear by considering the consequences for the extension of the concept of computability should the human faculty of calculation be found to violate one or more of conditions 1–5.⁴⁴ Imagine that scientists were to discover that human memory could involve an unbounded number of states, and, moreover, that this would result in hypercomputational mental powers—that is, in humans being able to calculate the values of functions that are not Turing machine computable. Would these discoveries threaten Turing’s analysis of computability? The cognitivist and the non-cognitivist give different answers.

The cognitivist answers yes. If it is found that humans can, as a matter of cognitive fact, encode an infinite procedure, perform infinitely many steps in a finite span of time (a supertask), or even observe an unbounded number of symbols at any given step when calculating a value of a function, cognitivists would regard this as undermining the analysis. If some of the constraints among 1–5 do not reflect actual upper limits on the faculty of calculation, then in the cognitive approach these constraints have no place in the analysis.

According to the non-cognitivist, however, the answer is no: discoveries about the human mind have no bearing on the analysis of computability. The non-cognitivist does not exclude the empirical possibility of the discovery that human memory is unbounded; the non-cognitivist simply denies that effective calculability is synonymous with this kind of cognitive calculability. Effective computability is calculability by finite means. Hence, the analysis of computability invokes a finite number of states of mind, because the analyzed concept is that of computation by means of a finite procedure. The focus is on what can be achieved by “finite means,” not on whether human beings are actually limited to finite means.

There is not necessarily a clear delineation between the cognitive and non-cognitive approaches. One might contend, for example, that some of the restrictive conditions reflect the limitations on cognitive capacities, while others arise from the nature of anything properly describable as “finite means.” Emil Post has one foot—or possibly even both feet—in the cognitive camp, saying that the purpose of his analysis “is not only to present a system of a certain logical potency but also, in its restricted field, of psychological fidelity” (1936: 105). Post refers to Church’s identification of effective calculability with recursiveness as amounting “not so much to a definition or to an axiom but to a natural law” (p. 105), adding that “to mask this identification under a definition hides the fact that a fundamental discovery in the limitations of the mathematicizing power of Homo Sapiens has been made” (p. 105 n. 8).⁴⁵ Gandy appears to understand Turing’s analysis in cognitivist terms, saying that Turing arrives at the restrictions “by considering the limitations of our sensory and mental apparatus” (2001: 11). Turing’s position, however, is more nuanced. On the one hand, he says that “for the present I shall only say that the justification lies in the fact that the human memory is necessarily limited” (1936: 59), which looks very much like a cognitive position. On the other hand, he later comments that we can sidestep states of mind altogether “by considering a more physical and definite counterpart” (p. 79), such as written symbolic configurations, which might suggest that he is taking the non-cognitive route after all. Church, Gödel, and Kripke appear to be far closer to the non-cognitive camp.⁴⁶

It has been claimed that Turing characterized effective computability in terms of Turing machine computability. The question is whether, and to what extent, this characterization captures the notion of machine computation in general and physical computation in particular. When addressing this issue, we are now in a position to prevent two potential mistakes.

One mistake is to identify computability with computing (this point pertains not only to effective computation, but to any kind of computation). The term computability refers to the functions (numbers, predicates) that can be computed.⁴⁷ The term computing refers to the processes by means of which these functions are carried out. As such, we can hardly expect computability to coincide with computing, namely, with the process of computation. Take a computable function, such as the zero function, whose output is zero for every input. It is computable in the sense that there is a computing process by which one can arrive at its values. But presumably there will also be many other, non-computing processes by which one arrives at the values of this (computable) function. Thus, computability cannot distinguish between the computing and non-computing processes that lead to the same (computable) function. Computability distinguishes between computable and non-computable functions. It does not distinguish between the computing and non-computing processes by which we can arrive at the values of the computable functions. As for effective computability, I do not think that it even provides a necessary condition for computing. As we have previously implied (Section 2.3.3), there are cases of hypercomputation—namely, of computing functions that are not Turing machine computable at all. In Chapter 3, we will discuss more cases of physical hypercomputation in detail.

The second mistake to avoid is the application of Turing’s characterization of effective computation to machine computation in general.⁴⁸ As previously noted, Turing analyzed effective calculation—namely, calculation by a human being who is following an effective (that is, finite and mechanical) procedure. In particular, constraints that apply to the human computer do not apply to mechanical devices in general. One might challenge the human interpretation underpinning Turing’s analysis. However, even those who do not accept this interpretation seem to agree that constraints 1–5 are too restrictive to be applied to computation in general. Gandy (1980), for example, stressed that Turing’s analysis does not apply to machines that perform parallel computation, in which the number of processing units is unbounded. A simple example of parallel computation is the well-known Game of Life (hereafter “Life”). Life is a potentially infinite two-dimensional grid of cells, each of which is in one of two possible states, alive or dead. Every cell interacts with its eight neighbors—that is, the cells that are horizontally, vertically, or diagonally adjacent. At each moment in time, the following transitions occur:

The initial pattern is any arbitrary arrangement of live/dead cells. The first generation is created by applying the preceding rules simultaneously to every cell in the grid; births and deaths occur simultaneously. The rules continue to be applied repeatedly to create further generations. It would seem that this evolution is a clear case of a computational process, although it does not conform to all of Turing’s restrictions.

Specifically, Life does not satisfy Turing’s fourth condition. As Gandy pointed out, Turing assumed that “a human being can only write one symbol at a time,” and this assumption cannot be carried over to a parallel machine that “prints an arbitrary number of symbols simultaneously” (1980: 124–125). In Life, there is no upper bound on the number of cells that make up the grid, yet the symbols in all the cells are updated simultaneously. Thus, there is no upper limit on the number of changes (“change of cell”) that can take place at each step. This is precisely the difference between the human computer and Life: even if the human computer can run computation in parallel, there is an upper limit on the number of parts that operate in parallel. Life is a parallel machine with no such limit.

Life therefore indicates that Turing’s conditions 1–5 are too restrictive with respect to machine computation in general. Life performs computations but does not satisfy all of Turing’s restrictive conditions. This does not mean that we cannot extend Turing’s condition in a way that will include Life and other parallel machines. It also does not mean that Life cannot be seen as an effective or algorithmic computation in some extended sense. We will discuss precisely these possibilities in Chapter 3. The conclusion, rather, is that Turing’s conditions on human computation cannot be taken as a characterization of machine computation. Assuming that Life, and other parallel machines, are instances of physical computation, we can also conclude that Turing’s conditions fall short of capturing physical computation (I will elaborate on this as well in Chapter 3).

I have reviewed Turing’s analysis of effective calculability, in which Turing formulates a set of constraints (“axioms”) on effective calculability and shows that its scope does not exceed Turing machine computability. The conclusion is that Turing’s analysis pertains specifically to human calculation, and that his analysis is too restrictive to apply to computing in general. One might be encouraged at this point to relax Turing’s conditions so that they might apply to more computing systems. But while this expansion is appealing with respect to some kinds of computation, I suspect it is fruitless with respect to characterizing physical computation. In Chapter 3, I will develop this line of argument in detail.