On Computability 599 to G(y) ~x v. The new atoms are thus always taken from U\SUp(x).44 One final definition: for given states z and x let A(z,x) stand for Sup(z)\Sup(x). Note that the number of new atoms introduced by G is bounded, i.e., IA(G(y), Sup(x))1 < n for some natural number n (any xE8 and any causal neighborhood y for x). So, how is the next state of a Turing computor assembled? By simple set theoretic operations, namely, difference \ and union U. Recalling the boundedness and locality conditions for computors we define that M = (8; T, G) is a Turing Computor on 8, where 8 is a structural class, T a finite set of stereotypes, and G a structural operation on U T, if and only if, for every x E 8 there is a z E 8, such that: (L.O) (:3!y) yECn(x), (L.l) (:3!vE Dr(z,x)) v~xG(cn(x)), (A.1) z = (x\ Cn(x)) U Dr(z,x). L stands for Locality and A for Assembly. (:3!y) is the existential quantifier ex- pressing uniqueness. cn(x) denotes the sole causal neighborhood of x guaranteed by L.O, i.e., every state is required by L.O to contain exactly one pattern. This pattern in state x yields a unique determined region of a possible next state z; that is expressed by L.1. The state z is obtained according to the assembly condition A.l. It is determined up to E-isomorphism over x. A computation by M is a finite sequence of transition steps via G that is halted when the operation on a state w yields w as the next state. This result, for input x, is denoted by M(x). A function F is (Turing) computable if and only if there is a Turing computor M whose computation results determine - under a suitable encoding and decoding - the values of F for any of its arguments. After all these definitions one can use a suitable set theoretic representation of Turing machines to establish one lemma, namely, that Turing machines are Turing computors. (See section 5.4.) In the next subsection, we will provide a characterization of computations by machines that is as general and convincing as that of human computors. Gandy laid the groundwork in his thought-provoking paper Church's Thesis and Princi- ples for Mechanisms - a rich and difficult, but unnecessarily and maddeningly complex paper. The structure of Turing's argument actually guided Gandy's anal- ysis; however, Gandy realized through conversations with J. C. Shepherdson that the analysis \"must take parallel working into account\". In a comprehensive survey article published ten years after Gandy's paper, Leslie Lamport and Nancy Lynch argued that the theory of sequential computing \"rests on fundamental concepts of computability that are independent of any particular computational model\". They emphasized that the \"fundamental formal concepts underlying distributed computing\", if there were any, had not yet been developed. \"Nevertheless\", they wrote, \"one can make some informal observations that seem to be important\": 44This selection of atoms new for x has in a very weak sense a \"global\" aspect; as G is a structural operation, the precise choice of the atoms does not matter.
600 Wilfried Sieg Underlying almost all models of concurrent systems is the assumption that an execution consists of a set of discrete events, each affecting only part of the system's state. Events are grouped into processes, each process being a more or less completely sequenced set of events sharing some common locality in terms of what part of the state they affect. For a collection of autonomous processes to act as a coherent system, the processes must be synchronized. (p. 1166) Gandy's analysis of parallel computation is conceptually convincing and provides a sharp mathematical form of the informal assumption(s) \"underlying almost all models of concurrent systems\". Gandy takes as the paradigmatic parallel compu- tation, as I mentioned already, the evolution of the Game of Life or other cellular automata. 5.2 Gandy machines Gandy uses, as Turing did, a central thesis: any discrete mechanical device satis- fying some informal restrictive conditions can be described as a particular kind of dynamical system. Instead, I characterize a Gandy Machine axiomatically based on the following informal idea: the machine has to recognize the causal neighbor- hoods of a given state, act on them locally in parallel, and assemble the results to obtain the next state, which should be unique up to E-isomorphism. In anal- ogy to the definition of Turing computability, we call a function F computable in parallel if and only if there is a Gandy machine M whose computation results determine - under a suitable encoding and decoding - the values of F for any of its arguments. What then is the underlying notion of parallel computation? Generalizing the above considerations for Turing computors, one notices quickly complications, when new atoms are introduced in the images of causal neighbor- hoods as well as in the next state: the different new atoms have to be \"structurally coordinated\". That can be achieved by a second local operation and a second set of stereotypes. Causal neighborhoods of type 1 are parts of neighborhoods of type 2 and the overlapping determined regions of type 1 must be parts of determined regions of type 2, so that they fit together appropriately. This generalization is absolutely crucial to allow the machine to assemble the determined regions. Here is the definition: M = (5; T I , G I , T 2 , G 2 ) is a Gandy Machine on 5, where 5 is a structural class, 'I', a finite set of stereotypes, G i a structural operation on UTi (i = 1 or 2), if and only if for every x E 5 there is a z E 5 such that (L.I) (Vy E Cnl(X))(:J!v E Drl(Z,X))V ~x GI(y); (L.2) (Vy E Cn2(X))(:JV E Dr2(Z, x))v ~x G 2(y); (A.I) (VC)[C ~ Drl(Z, x))& n { Sup (v) n A(z, x)lv E C} i= 0 ----t (:Jw E Dr2(Z, x))(Vv E C)v <* w]; (A.2) z = U Drl(Z,X).
On Computability 601 The condition n{Sup(v) n A(z, x)lv E C} =1= 0 in (A.I) expresses that the deter- mined regions v in C have new atoms in common, i.e., they overlap. - It might be helpful to the reader to look at section 5.4 and the description of the game of life as a Gandy machine one finds there. The restrictions for Gandy machines, as in the case of Turing computors, amount to boundedness and locality conditions. They are justified directly by two physical limitations, namely, a lower bound on the size of atomic components and an upper bound on the speed of signal propagation. I have completed now all the foundational work and can describe two important mathematical facts for Gandy machines: (i) the state z following x is determined uniquely up to E-isomorphism over x, and (ii) Turing machines can effect such transitions. The proof of the first claim contains the combinatorial heart of matters and uses crucially the assem- bly conditions. The proof of the second fact is rather direct. Only finitely many finite objects are involved in the transition, and all the axiomatic conditions are decidable. Thus, a search will allow us to find z. This can be understood as a Representation Theorem: any particular Gandy machine is computationally equiv- alent to a two-letter Turing machine, as Turing machines are also Gandy machines. The first fact for Gandy machines, z is determined uniquely up to E-isomorphism over x, follows from the next theorem.Y Before being able to formulate and prove it, we need to introduce one more concept. A collection C of parts for x is a cover for x just in case x ~ U C. THEOREM. Let M be (8; T I , G I , T z, G z ) as above and x E 8; ifthere are z and z' in 8 satisfying principles (L.I-2), (A.I), and if Drl(Z,X) and Drl(Z',X) cover z and z', then Drl(Z,X) ~x Drl(Z',X). In the following Dr- , Dr~, A, and A' will abbreviate Drl(Z,X), Drl(Z',X), A(z,x), and A(z',x) respectively. Note that Dr , and Dr~ are finite. Using (L.I) and (L.2) one can observe that there is a natural number m and there are sequences Vi and v~, i < m, such that Drj = {viii < m}, Dr~ = {v~li < m}, and v~ is the unique part of z' with Vi ~xV~ via permutations 7fi (for all i < m). See Figure 1, which is a picture of the situation. To establish the Theorem, we have to find a single permutation 7f that extends to an E-isomorphism over x for all Vi and v~ simultaneously. Such a 7f must obviously satisfy for all i < m: .) \"-' , . (I Vi =x Vi VIa tt and, consequently, (ii) 7f[Sup(Vi)]=Sup(vD. 45In [Gandy, 1980] this uniqueness up to E-isomorphism over x is achieved in a much more complex way, mainly, because parts of a state are proper subtrees, in general non-located. Given an appropriate definition of cover, a collection C is called an assembly for x, if C is a cover for x and the elements of C are maximal. The fact that C is an assembly for exactly one x, if indeed it is, is expressed by saying that C uniquely assembles to x; see [Sieg and Byrnes, 1999a, 157]. In my setting, axiom (A.2) is equivalent to the claim that Dr, (z,x) uniquely assembles to z.
602 Wilfried Sieg x Figure 1. As 7r is an E-isomorphism over x, we have: (iii) 7r[A] = N. Condition (ii) implies for all i < m and all rEA the equivalence between rESup(vi) and r\" ESup(v~). This can also be expressed by (ii*) f.L(r)=J1/(r1f), for all rE A, where f.L(r) = {ilr E SUp(Vi)} and f.L'(r) = {ilr E Sup(vD}; these are the signatures of r with respect to z and z'. To obtain such a permutation, the considerations are roughly as follows: (i) if the Vi do not overlap, then the 7ri will do; (ii) ifthere is overlap, then an equivalence relation re (;:::;') on A(N) is defined by rI;:::;r2 iff f.L(rI) = f.L(r2) , and analogously for ;:::;'; (iii) then we prove that the \"corresponding\" equivalence classes [r]\"\" and [s]\"\", (the signatures of their elements are identical) have the same cardinality. [r]\"\" can be characterized as n{SUp(Vi) n Ali E f.L(r)}; similar for [s]\"\",. This characterization is clearly independent of the choice of representative by the very definition ofthe equivalence relation(s). With this in place, a global E-isomorphism can be defined. These considerations are made precise through the proofs of the combinatorial lemma and two corollaries in the next section. 5.3 Global assembly All considerations in this section are carried out under the assumptions of the Theorem: M = (S; T I, G I , T 2, G 2 ) is an arbitrary Gandy machine and xES an
On Computability 603 arbitrary state; we assume furthermore that z and z' are in S, the principles (L.l- 2) and (A.l) are satisfied, and that Dr! and Dr~ cover z and z', because of (A.2). We want to show that Dr! ~xDr~, knowing already that there are sequences Vi and v~ of length m, such that Dr! = {vii i-cm}, Dr~ = {v~1 i-crn] and v~ is the unique part of z' with Vi ~xV~ via permutations 7l\"i (for all i-cm). I start out with the formulation ofa key lemma concerning overlaps. LEMMA. (Overlap Lemma.) Let ro E A and p,(ro) -# 0; then there is a permutation p on U with Vi ~x v~ via p for all i E p,(ro). Proof. We have {viii E p,(ro)} ~ Dr- ; as ro is in A and in SUP(Vi) for each i E p,(ro) -# 0, we have also that n{SUp(Vi) n Ali E p,(ro)} -# 0. The antecedent of (A.1) is satisfied, and we conclude that there is awE Dr2 such that Vi <* w <* z, for all i E p,(ro). Using (L.2) we obtain a w' E Dr2 with w ~x w'. This E- isomorphism over x is induced by a permutation p and yields for all i E p,(ro) Vf <* w\" = W' <* z'. So we have, Vi ~x vf and vf <* z', thus - using (L.l) - vf=v~; that holds for all i E p,(ro). • Note that the condition p,(r)-# 0 is satisfied in our considerations for any rEA, as Dr- is a cover of z; so we have for any such r an appropiate overlap permutation pr for r. The crucial combinatorial lemma we have to establish is this: LEMMA. (Combinatorial Lemma.) For ro E A : I{r E Alp,(ro) ~ p,(r)}I I{s E A'1p,(ro) ~ p,'(s)}I. Proof. Consider ro E A. I establish first the claim p[{r E Alp,(ro) ~ p,(r)}] ~ {s E A'1p,(ro) ~ p,'(s)}, where p is an overlap permutation for roo The claim follows easily from P by observing that r is in A'. Assume, to establish this conditional indirectly, for P arbitrary rEA that p,(ro) ~ p,(r) and --,(p,(ro) ~ p,'(r ». The first assumption implies that r E SUP(Vi) for all i E p,(ro), and the construction of p yields then: P (\7) r E Sup(v~) for all i E p,(ro). The second assumption implies that there is a k in p,(ro)\p,'(r P ) . Obviously, k E p,(ro) and k t/:. p,'(r ) . The first conjunct k E p,(ro) and (\7) imply that x\" E P Sup(vj.); as the second conjunct k t/:. p,'(r ) means that r P t/:. Sup(vU, we have P obtained a contradiction. Now I'll show that p[{r E Alp,(ro) ~ p,(r)}] cannot be a proper subset of {s E A'1p,(ro) ~ p,'(s)}. Assume, to obtain a contradiction, that it is; then there is
604 Wilfried Sieg s* E A' that satisfies M(ro) C;;; M'(S*) and is not a member of p[{r E AIM(ro) C;;; M(r)}]. As M(ro) C;;; M'(S*), s* is in Sup(vD for all i E M(ro); the analogous fact holds for all rEA satisfying M(ro) C;;; M(r), i.e., all such r must be in SUP(Vi) for all i E M(ro). As Vi ~x v~ via p for all i E M(ro), s\" must be obtained as a p-image of some r\" in Sup(x) or in A (and, in the latter case, violating M(ro) C;;; M(r*)). However, in either case we have a contradiction. The assertion of the Lemma is now immediate. • Next I establish two consequences of the Combinatorial Lemma, the second of which is basic for the definition of the global isomorphism tt . COROLLARY 1. For any I C;;; {a, 1, ..., m -I} with I C;;; M(ro) for some ro in A, I{r E All C;;; M(r)}1 = I{s E A'II C;;; M'(s)}l· Proof. Consider an arbitrary I C;;; M(ro) for some ro in A. If I = M(ro), then the k 1 claim follows directly from the Combinatorial Lemma. If I C M(ro), let r\", ...,r - j be elements r of A with I C M(r) and require that M(r ) -I- M(rJ'), for all j,j' < k and j -I- i', and for every rEA with I C M(r) there is a unique j < k with j M(r) = M(r ) . The Combinatorial Lemma implies, for all j < k, Now it is easy to verify the claim of Corollary 1: I{r E All C;;; M(r)}1 = j I{r E AI(::Jj < k)M(r ) C;;; M(r)}1 = j I{s E A'1(::Jj < k)M(r ) C;;; M'(s)}1 = I{s E A'II C;;; M'(s)}l· • This completes the proof of Corollary 1. The second important consequence of the Combinatorial Lemma can be obtained now by an inductive argument. COROLLARY 2. For any I C;;; {a, 1, ..., m - I} with I C;;; M(ro) for some ro in A. I{r E All = M(r)} I = I{s E A'II = M'(s)}l· Proof. (By downward induction on III). Abbreviating I{r E All = M(r)}1 by VI and I{s E A'II = M'(s)}1 by vL the argument is as follows: Base case (III = m): In this case there are no proper extensions 1* of I, and we have VI = I{r E All = M(r)}1 = I{r E All C;;; M(r)}l, as there is no proper extension of I, = I{s E A'II C;;; M'(s)}l, by Corollary 1, = I{s E A'II = M'(s)}l, again, as there is no proper extension, = v~
On Computability 605 Induction step (III) < m): Assume that the claim holds for all 1* with n + 1 < 11*Is: m and show that it holds for I with III = n. Using the induction hypothesis we have, summing up over all proper extensions 1* of I: Now we argue as before: VI = I{r E All = Jl(r)} I = I{r E All S;; Jl(r)}l- L,1*V1* = I{s E A'II S;; Jl'(s)}l- L,I*V~*, by Corollary 1 and (\"), = I{s E A'II = Jl'(s)}I = v~ This completes the proof of Corollary 2. • Finally, we can define an appropriate global permutation tt . Given an atom rEA, there is an overlap permutations p\", which can be restricted to [r]\"\", = n{Sup(vi)nAli E Jl(rn; let p* denote this restriction. Because of Corollary 2, p» is a bijection between [r]\"\", and [p* (r)]\"\"\". The desired global permutation is now defined as follows for any atom r E U{Sup(vi)li < m}: Ti(r) = {p*(r) if r E ~{SuP(vi)nAI iE u (rn r otherwise Ti is a well-defined bijection with Ti[A] = A' and Jl(r) = Jl'(r 7r ) . It remains to establish: Claim: For all i < m, Vi ~x v~ via Ti. For the Proof consider an arbitrary i < m. By the basic set-up of our con- siderations, we have Tii(Vi) = v~. If Vi does not contain in its support an el- ement of A, then Ti and Tii coincide; if vi's support contains an element of A that is possibly even in an overlap, the argument proceeds as follows. Notice first of all that all elements of [r]\"\", are in SUP(Vi) as soon as one rEA is in SUP(Vi)' Taking this into account, we have by definition of Ti and Vi i [r]\"\",: Ti(Vi i [r]\",,) = P*(Vi i [r]\",,).46 The definition of p* and the fact that pr(Vi) = v~ al- low us to infer that P*(Vi i [r]\",,) = v~ i [p*(r)]\"\",. As Jl'(p*(r)) = Jl'(Tii(r))[= Jl(r)] we can extend this sequence of identities by v~ i [p*(r)]\"\", = v~ i [Tii(r)]\"\",. Con- sequently, as Tii(Vi) = v~, we have v~ i [Tii(r)]\"\", = Tii(Vi i [r]\",,). These considerations hold for all r ESUp(Vi)nA; we can conclude Ti(Vi) = Tii(Vi) and, with Tii(Vi) = v~, we have Ti(Vi) = v~. This concludes, finally, the argument for the Theorem. 46 1 is the pruning operation; it applies to an element x of HF and a subset Y of its support: x I Y is the subtree of x that is built up exclusively from atoms in Y. The E-recursive definition is: (xnY) U [{y I (YnTc(y))ly E x}\{0}]. Cf. [Sieg and Byrnes, 1999a, 155-6].
5.4 Models There is a rich variety of models, as the game of life, other cellular automata and many artificial neural nets are Gandy machines. Let me first sketch a set theoretic presentation of a Turing machine as a Turing computor and then, even more briefly, that of the Game of Life as a Gandy machine. Consider a Turing machine with symbols So, ..., Sk and internal states qo, ... , qm; its program is given as a finite list of quadruples of the form qiSjCkqm, expressing that the machine is going to perform action Ck and change into internal state qm, when scanning symbol Sj in state qi. The tape is identified with a set of overlapping pairs Tp := {(b, b),(b, c), ..., (d,e), (e, e)} where b,c, ..., d, e are distinct atoms; C is the leftmost square of the tape with a possibly non-blank symbol on it, d its rightmost one. The symbols are rep- resented by §\"Jo := {1'} (]+l) , 0 ::; j ::; k; the internal states are given by q .- -J {1'} (k+l)+(j+l), 0 ::; j ::; i. The tape content is given by and, finally, the id is represented as the union of Tp, Ct, and {(q 0' 1')} with r -t being a square of Tp. So the structural set S of states is obtained as the set of all ids closed under E-isomorphisms. Stereotypes (for each program line given by qiSj) consist of parts like these are the causal neighborhoods on which G operates. Consider the program line qiSjSkql (print Sk); applied to the above causal neighborhood G yields {(<.11' 1'), (§..k' 1'), (t, 1'), (1', u)}. For the program line qisjRql (move Right) two cases have to be distinguished. In the first case, when r is not the rightmost square, G yields {(<.11' u), (§..j' 1'), (t, 1'), (1', u)}; in the second case, when r is the rightmost square, G yields where * is a new atom. The program line qisjLql (move Left) is treated similarly. It is easy to verify that a Turing machine presented in this way is a Turing Computor. Cellular automata introduced by Ulam and von Neumann operate in parallel; a particular cellular automaton was made popular by Conway, the Game of Life. A cellular automaton is made up of many identical cells. Typically, each cell is located on a regular grid in the plane and carries one of two possible values. After
On Computability 607 each time unit its values are updated according to a simple rule that depends on its own previous value and the previous values of the neighboring cells. Cellular automata of this sort can simulate universal Turing machines, but they also yield discrete simulations of very general and complex physical processes. Gandy considered playing Conway's Game of Life as a paradigmatic case of parallel computing. It is being played on subsets of the plane, more precisely, subsets that are constituted by finitely many connected squares. For reasons that will be obvious in a moment, the squares are also called internal cells; they can be in two states, dead or alive. In my presentation the internal cells are surrounded by one layer of border cells; the latter, in turn, by an additional layer of virtual cells. Border and virtual cells are dead by convention. Internal cells and border cells are jointly called real. The layering ensures that each real cell is surrounded by a full set of eight neighboring cells. For real cells the game is played according to the rules: 1. living cells with 0 or 1 (living) neighbor die (from isolation); 2. living cells with 4 or more (living) neighbors die (from overcrowding); 3. dead cells with exactly 3 (living) neighbors become alive. 4. In all other cases the cell's state is unchanged. A real cell a with neighbors al, ...,as and state s(a) is given by {a, s(a), (al, ...,as)}. The neighbors are given in \"canonical\" order starting with the square in the left- most top corner and proceeding clockwise; s(a) is {a} in case a is alive, otherwise {{a}}. The T'j-causal neighborhoods of real cells are of the form {{a, s(a), (al,\"\" as)}, {aI, s(al)},\"\" {as, s(as)}}. It is obvious how to define the structural operation G I on the causal neighborhoods of internal cells; the case of border cells requires attention. There is a big number of stereotypes that have to be treated, so I will discuss only one simple case that should, nevertheless, bring out the principled considerations. In the following diagram we start out with the cells that have letters assigned to them; the diagram should be thought of extending at the left and at the bottom. The v's indicate virtual cells, the b's border cells, the {a} 's internal cells that are alive, and the *'s new atoms that are added in the next step of the computation. Let's see how that comes about. Consider the darkly shaded square b 3 with its neighbors, i.e., its presentation applying G I to its causal neighborhood yields
608 Wilfried Sieg *0 Vg {ao} {ad where *2, *3, and *4 are new atoms (and V3 has been turned from a virtual cell into a real one, namely a border cell). Here the second set of stereotypes and the second structural operation come in to ensure that the new squares introduced by applying G 1 to \"adjacent\" border cells (whose neighborhoods overlap with the neighborhood of b 3 ) are properly identified in the next state. Consider as the appropriate T 2-causal neighborhood the set consisting of the T l-causal neighbor- hoods of b 2 , b 3 , and b 4 ; G 2 applied to it yields the set with presentations of the cells V2, V3, and V4. 5.5 Tieferlegung The above considerations constitute the mathematical core of this section. They lead to the conclusion that computability, when relativized to a particular kind of computing agent or device, has a perfectly standard methodological status: no thesis is needed, but rather the recognition that the axiomatic characterization is correct for the intended computing device. The recognition that the notions do not go beyond Turing computability is then an important mathematical fact. It seems to me that we have gained in Hilbert's broad terms a deepening of the foundations via the axiomatic method, a Tieferlegung der Fundamente. As I mentioned earlier, Codel advocated such an approach in a conversation with Church in early 1934 and suggested \"to state a set of axioms which would embody the generally accepted properties of this notion (i.e., effective calculability), and to do something on that basis.\" The sharpened version of Turing's work and a thorough-going re-interpretation of Gandy's approach allow us to fill in the blanks of Codel's suggestion; this resolves in my view the methodological issue raised at the end of section 4. Perhaps the remarks in the 1964 Postscriptum to the Princeton Lectures of 1934 echo his earlier considerations. \"Turing's work gives,\" according to Codel, \"an analysis of the concept of 'mechanical procedure'.... This concept is shown to be equivalent with that of a 'Turing machine'.\" The work, on which I reported, substantiates these remarks in the following sense: it provides an axiomatic analysis of the concept \"mechanical procedure\" and shows that this concept is computationally
On Computability 609 equivalent to that of a Turing machine. Indeed, it does so for two such concepts, namely, when the computing agents are computors or discrete machines; and it does so by imposing constraints on the computations these agents carry out in steps. The natural and well-motivated constraints guarantee the effectiveness of the steps in the most direct way. The axiomatic approach captures the essential nature of computation processes in an abstract way. The difference between the two types of calculators I have been describing is reduced to the fact that Turing computors modify one bounded part of a state, whereas Gandy machines operate in parallel on arbitrarily many bounded parts. The axiomatic conditions arise from underlying analyses that lead to a particular structural view. Of course, an appeal to some informal understand- ing can no more be avoided in this case than in any other case of an axiomatically characterized mathematical structure intended to model broad aspects of physical or intellectual reality. The general point is this: we don't have to face anything especially mysterious for the concept of calculability; rather, we have to face the ordinary issues for the adequacy of mathematical concepts and they are, of course, non-trivial. I have been distinguishing in other writings two aspects of mathematical ex- perience. The first, the quasi-constructive aspect, has to do with the recognition of laws for accessible domains; this includes, in particular, our recognition of the correctness of the Zermelo Fraenkel axioms in set theory and their extendibility by suitable axioms of infinity. The second, the conceptional aspect, deals with the un- covering of abstract, axiomatically characterized notions. These abstract notions are distilled from mathematical practice for the purpose of comprehending com- plex connections, of making analogies precise and of obtaining a more profound understanding. Bourbaki in their [1950] expressed matters quite in Dedekind and Hilbert's spirit, when claiming that the axiomatic method teaches us to look for the deep-lying reasons for such a discovery [that two or several quite distinct theories lend each other \"unexpected support\"], to find the common ideas of these theories, ... to bring these ideas forward and to put them in their proper light. (p. 223) Notions like group, field, topological space and differentiable manifold are ab- stract in this sense. Turing's analysis shows, when properly generalized, that com- putability exemplifies the second aspect of mathematical experience. Although Godel used \"abstract\" in a more inclusive way than I do here his broad claim is pertinent also for computability, namely, \"that we understand abstract terms more and more precisely as we go on using them, and that more and more abstract terms enter the sphere of our understanding.\" [1972, 306] 6 OUTLOOK ON MACHINES AND MIND Turing's notion of human computability is exactly right not only for obtaining a negative solution of the Entscheidungsproblem that is conclusive, but also for
610 Wilfried Sieg achieving a precise characterization of formal systems that is needed for the general formulation of Codel's incompleteness theorems. I argued in sections 1 and 2 that the specific intellectual context reaches back to Leibniz and requires us to focus attention on effective, indeed mechanical procedures; these procedures are to be carried out by computors without invoking higher cognitive capacities. The axioms of section 5.1 are intended for this informal concept. The question whether there are strictly broader notions of effectiveness has of course been asked for both cognitive and physical processes. I am going to address this question not in any general and comprehensive way, but rather by focusing on one central issue: the discussion might be viewed as a congenial dialogue between Codel and Turing on aspects of mathematical reasoning that transcend mechanical procedures. I'll start in section 6.1 by returning more fully to Codel's view on mechanical computability as articulated in his [1937J. There he drew a dramatic conclusion from the undecidability of certain Diophantine propositions, namely, that mathe- maticians cannot be replaced by machines. That theme is taken up in the Gibbs Lecture of 1951 where Codel argues in greater detail that the human mind in- finitely surpasses the powers of any finite machine; an analysis of the argument is presented in section 6.2 under the heading Beyond calculation. Section 6.3 is entitled Beyond discipline and gives Turing's perspective on intelligent machinery; it is devoted to the seemingly sharp conflict between Codel's and Turing's views on mind. Their deeper disagreement really concerns the nature of machines, and I'll end with some brief remarks on (supra-) mechanical devices in section 6.4. 6.1 Mechanical computability In section 4.2 I alluded briefly to the unpublished and untitled draft for a lecture Godel presumably never delivered; it was written in the late 1930s. Here one finds the earliest extensive discussion of Turing and the reason why Godel, at the time, thought Turing had established \"beyond any doubt\" that \"this really is the correct definition of mechanical computability\". Obviously, we have to clarify what \"this\" refers to, but first I want to give some of the surrounding context. Already in his [1933J Godel elucidated, as others had done before him, the mechanical feature of effective procedures by pointing to the possibility that machines carry them out. When insisting that the inference rules of precisely described proof methods have to be \"purely formal\" he explains: [The inference rules] refer only to the outward structure of the formu- las, not to their meaning, so that they could be applied by someone who knew nothing about mathematics, or by a machine. This has the consequence that there can never be any doubt as to what cases the rules of inference apply to, and thus the highest possible degree of exactness is obtained. [Collected Works III, p. 45] During the spring term of 1939 Godel gave an introductory logic course at Notre Dame. The logical decision problem is informally discussed and seen in
On Computability 611 the historical context of Leibniz's \"Calculemus\" .47 Before arguing that results of modern logic prevent the realization of Leibniz's project, Godel asserts that the rules of logic can be applied in a \"purely mechanical\" way and that it is therefore possible \"to construct a machine which would do the following thing\": The supposed machine is to have a crank and whenever you turn the crank once around the machine would write down a tautology of the calculus of predicates and it would write down every existing tautology . .. if you turn the crank sufficiently often. So this machine would really replace thinking completely as far as deriving of formulas of the calculus of predicates is concerned. It would be a thinking machine in the literal sense of the word. For the calculus of propositions you can do even more. You could construct a machine in form of a typewriter such that if you type down a formula of the calculus of propositions then the machine would ring a bell [if the formula is a tautology] and if it is not it would not. You could do the same thing for the calculus of monadic predicates. Having formulated these positive results Godel points out that \"it is impossible to construct a machine which would do the same thing for the whole calculus of predicates\". Drawing on the undecidability of predicate logic established by Church and Turing, he continues with a striking claim: So here already one can prove that Leibnitzens [sid] program of the \"calculemus\" cannot be carried through, i.e. one knows that the hu- man mind will never be able to be replaced by a machine already for this comparatively simple question to decide whether a formula is a tautology or not. I mention these matters to indicate the fascination Codel had with the mechanical realization of logical procedures, but also his penchant for overly dramatic formu- lations concerning the human mind. He takes obviously for granted here that a mathematically satisfactory definition of mechanical procedures has been given. Such a definition, Codel insists in [193?, 166], is provided by the work of Her- brand, Church and Turing. In that manuscript he examines the relation between mechanical computability, general recursiveness and machine computability. This is of special interest, as we will see that his methodological perspective here is quite different from his later standpoint. He gives, on pp. 167-8, a perspicuous presentation ofthe equational calculus that is \"essentially Herbrand's\" and defines general recursive functions. He claims outright that it provides \"the correct defi- nition of a computable function\". Then he asserts, \"That this really is the correct definition of mechanical computability was established beyond any doubt by Tur- ing.\" Here the referent for \"this\" has finally been revealed: it is the definition of general recursive functions. How did Turing establish that this is also the correct definition of mechanical computability? Codel's answer is as follows: 47This is [Codel 1939]. As to the character of these lectures, see [Dawson], p. 135.
612 Wilfried Sieg He [Turing] has shown that the computable functions defined in this way [via the equational calculus] are exactly those for which you can construct a machine with a finite number of parts which will do the following thing. If you write down any number nl, ... , n; on a slip of paper and put the slip of paper into the machine and turn the crank, then after a finite number of turns the machine will stop and the value of the function for the argument nl, ... ,n r will be printed on the paper. [Collected Works III, p. 168] The implicit claim is clearly that a procedure is mechanical just in case it is executable by a machine with a finite number of parts. There is no indication of the structure of such machines except for the insistence that they have only finitely many parts, whereas Turing machines are of course potentially infinite due to the expanding tape. The literal reading of the argument for the claim \"this really is the correct definition of mechanical computability was established beyond any doubt by Tur- ing\" amounts to this. The equational calculus characterizes the computations of number-theoretic functions and provides thus \"the correct definition of com- putable function\". That the class of computable functions is co-extensional with that of mechanically computable ones is then guaranteed by \"Turing's proof\" of the equivalence between general recursiveness and machine computability.v' Con- sequently, the definition of general recursive functions via the equational calculus characterizes correctly the mechanically computable functions. Without any ex- plicit reason for the first step in this argument, it can only be viewed as a direct appeal to Church's Thesis. If we go beyond the literal reading and think through the argument in parallel to Turing's analysis in his [1936], then we can interpret matters as follows. Turing considers arithmetic calculations done by a computor. He argues that they involve only very elementary processes; these processes can be carried out by a Turing machine operating on strings of symbols. Codel, this interpretation maintains, also considers arithmetic calculations done by a computor; these calculations can be reduced to computations in the equational calculus. This first step is taken in parallel by Godel and Turing and is based on a conceptual analysis; d. the next paragraph. The second step connects calculations of a computor to computations of a Turing machine. This connection is established by mathematical arguments: Turing simply states that machines operating on finite strings can be proved to be equivalent to machines operating on individual symbols, i.e., to ordinary Turing machines; Godel appeals to \"Turing's proof\" of the fact that general recursiveness and machine computability are equivalent. Notice that in Godel's way of thinking about matters at this juncture, the math- ematical theorem stating the equivalence of general recursiveness and machine 48In Turing's [1936] general recursive functions are not mentioned. Turing established in an Appendix to his paper the equivalence of his notion with -\-definability. As Church and Kleene had already proved the equivalence of -\-definability and general recursiveness, \"Turing's Theorem\" is thus established for Turing computability.
On Computability 613 computability plays the pivotal role: It is not Turing's analysis that is appealed to by Godel but rather \"Turing's proof\". The central analytic claim my inter- pretation attributes to Codel is hardly argued for. On p. 13 Codel just asserts, \"... by analyzing in which manner this calculation [of the values of a general re- cursive function] proceeds you will find that it makes use only of the two following rules.\" The two rules as formulated here allow substituting numerals for variables and equals for equals. So, in some sense, Codel seems to think that the rules of the equational calculus provide a way of \"canonically\" representing steps in calcu- lations and, in addition, that his characterization of recursion is the most general one. 49 The latter is imposed by the requirement that function values have to be calculated, as pointed out in [1934, 369 top]; the former is emphasized much later in a letter to van Heijenoort of April 23, 1963, where Codel distinguishes his def- inition from Herbrand's. His definition, Codel asserts, brought out clearly what Herbrand had failed to see, namely \"that the computation (for all computable functions) proceeds by exactly the same rules \". [Collected Works V, p. 308] By contrast, Turing shifts from arithmetically meaningful steps to symbolic processes that underlie them and can be taken to satisfy restrictive boundedness as well as locality conditions. These conditions cannot be imposed directly on arithmetic steps and are certainly not satisfied by computations in the equational calculus. So, we are back precisely at the point of the discussion in section 3. 6.2 Beyond calculation In [193?] Godel begins the discussion by reference to Hilbert's \"famous words\" that \"for any precisely formulated mathematical question a unique answer can be found\". He takes these words to mean that for any mathematical proposition A there is a proof of either A or not-A, \"where by 'proof' is meant something which starts from evident axioms and proceeds by evident inferences\". He argues that the incompleteness theorems show that something is lost when one takes the step from this notion of proof to a formalized one: \"... it is not possible to formalise mathematical evidence even in the domain of number theory, but the conviction about which Hilbert speaks remains entirely untouched. Another way of putting the result is this: it is not possible to mechanise mathematical reasoning; ... \" Then he continues, in a way that is similar to the striking remark in the Notre Dame Lectures, \"i.e., it will never be possible to replace the mathematician by a machine, even if you confine yourself to number-theoretic problems.\" (pp. 164-5) The succinct argument for this conclusion is refined in the Gibbs Lecture of 1951. In the second and longer part of the lecture, Godel gave the most sustained defense of his Platonist standpoint drawing the \"philosophical implications\" of the situation presented by the incompleteness theorems. 50 \"Of course,\" he says 49This is obviously in contrast to the view he had in 1934 when defining general recursive functions; cf. section 3.2. 0 5 T hat standpoint is formulated at the very end of the lecture as follows: p. 38 (CW III, 322/3): \"Thereby [i.e., the Platonistic view] I mean the view that mathematics describes a non-
614 Wilfried Sieg polemically, \"in consequence of the undeveloped state of philosophy in our days, you must not expect these inferences to be drawn with mathematical rigor.\" The mathematical aspect of the situation, he claims, can be described rigorously; it is formulated as a disjunction, \"Either mathematics is incompletable in this sense, that its evident axioms can never be comprised in a finite rule, that is to say, the human mind (even within the realm of pure mathematics) infinitely surpasses the powers of any finite machine, or else there exist absolutely unsolvable Diophantine problems of the type specified ... \" Codel insists that this fact is both \"mathe- matically established\" and of \"great philosophical interest\". He presents on pages 11-13 an argument for the disjunction and considers its conclusion as \"inevitable\". The disjunction is called in footnote 15 a theorem that holds for finitists and intuitionists as an implication. Here is the appropriate implication: If the evi- dent axioms of mathematics can be comprised in a finite rule, then there exist absolutely unsolvable Diophantine problems. Let us establish this implication by adapting Godel's considerations for the disjunctive conclusion; the argument is brief. Assume the axioms that are evident for the human mind can be comprised in a finite rule \"that is to say\", for Codel, a TUring machine can list them. Thus there exists a mechanical rule producing all the evident axioms for \"subjective\" mathematics, which is by definition the system of all humanly demonstrable math- ematical propositions.51 On pain of contradiction with the second incompleteness theorem, the human mind cannot prove the consistency of subjective mathemat- ics. (This step is of course justified only if the inferential apparatus for subjective mathematics is given by a mechanical rule, and if subjective mathematics satisfies all the other conditions for the applicability of the second theorem.) Consequently, the Diophantine problem corresponding to the consistency statement cannot be proved either in subjective mathematics. That justifies Codel's broader claim that it is undecidable \"not just within some particular axiomatic system, but by any mathematical proof the human mind can conceive\". (p. 13) In this sense the problem is absolutely undecidable for the human mind. So it seems that we have established the implication. However, the very first step in this argument, indicated by \"that is to say\", appeals to the precise concept of \"finite procedure\" as analyzed by TUring. Why is \"that is to say\" justified for Godel? To answer this question, I examine Codel's earlier remarks about finite procedures and finite machines.52 sensual reality, which exists independently both of the acts and [[of]) the dispositions of the human mind and is only perceived, and probably perceived very incompletely, by the human mind.\" 51This is in contrast to the case of \"objective\" mathematics, the system of all true mathematical propositions, for which one cannot have a \"well-defined system of correct axioms\" (given by a finite rule) that comprises all of it. In [Wang, 1974, 324-6]' Godel's position on these issues is (uncritically) discussed. The disjunction is presented as one of \"two most interesting rigorously proved results about minds and machines\" and is formulated as follows: \"Either the human mind surpasses all machines (to be more precise: it can decide more number theoretic questions than any machine) or else there exist number theoretical questions undecidable for the human mind.\" 52Boolos' Introductory Note to the Gibbs Lecture, in particular section 3, gives a different perspective on difficulties in the argument.
On Computability 615 Godel stresses in the first paragraph of the Gibbs Lecture that the incomplete- ness theorems have taken on \"a much more satisfactory form than they had had originally\". The greatest improvement was made possible, he underlines, \"through the precise definition of the concept of finite procedure, which plays a decisive role in these results\". Though there are a number of different ways of arriving at such a definition which all lead to \"exactly the same concept\" , the most satisfactory way is that taken by Turing when \"reducing the concept of a finite procedure to that of a machine with a finite number of parts\". Godel does not indicate the character of, or an argument for, the reduction of finite procedures to procedures effected by a machine with a finite number of parts, but he states explicitly that he takes finite machine \"in the precise sense\" of a Turing machine. (p. 9) This reduction is pivotal for establishing the central implication rigorously, and it is thus crucial to understand and grasp its mathematical character. How else can we assent to the claim that the implication has been established mathematically as a theorem? In his [1964] Codel expressed matters quite differently (and we discussed that later Godelian perspective extensively in section 4): there he asserts that Turing in [1936] gave an analysis of mechanical procedures and showed that the analyzed concept is equivalent to that of a Turing machine. The claimed equivalence is viewed as central for obtaining \"a precise and unquestionably adequate definition of the general concept of formal system\" and for supporting, I would like to add in the current context, the mathematical cogency of the argument for the implication. Godel neither proved the mathematical conclusiveness of the reduction nor the correctness of the equivalence. So let us assume, for the sake of the argument, that the implication has been mathematically established and see what conclusions of great philosophical interest can be drawn. There is, as a first background assumption, Codel's deeply rationalist and optimistic perspective that denies the consequent of the implication. That perspective, shared with Hilbert as we saw in section 6.1, was articulated in [193?], and it was still taken in the early 1970s. Wang reports in [1974, 324-5], that Codel agreed with Hilbert in rejecting the possibility that there are number-theoretic problems undecidable for the human mind. Our task is then to follow the path of Codel's reflections on the first alternative of his disjunction or the negated antecedent of our implication. That assertion states: There is no finite machine (i.e. no Turing machine) that lists all the axioms of mathematics which are evident to the human mind. Godel argues for two related conclusions: i) the working of the human mind is not reducible to operations of the brain, and ii) the human mind infinitely surpasses the powers of any finite machine. 53 A second background assumption is introduced to obtain the first conclusion: The brain, \"to all appearances\" , is \"a finite machine with a finite number of parts, 53This does not follow just from the fact that for every Turing machine that lists evident axioms there is another axiom evident to the human mind not included in the list. Turing had tried already in his 1939 paper, Ordinal Logics, to overcome the incompleteness results by strengthening theories systematically. He added consistency statements (or reflection principles) and iterated this step along constructive ordinals; Feferman perfected that line of investigation, d. his [1988]. Such a procedure was also envisioned in [Codel, 1946, 1-2].
616 Wilfried Sieg namely, the neurons and their connections\". (p. 15) As finite machines are taken to be Turing machines, brains are consequently also considered as Turing machines. That is reiterated in [Wang, 1974, 326], where Codel views it as very likely that \"The brain functions basically like a digital computer.\" Together with the above assertion this allows Godel to conclude in the Gibbs Lecture, \"the working of the human mind cannot be reduced to the working of the brain\".54 In [Wang] it is taken to be in conflict with the commonly accepted view, \"There is no mind separate from matter.\" That view is for Godel a \"prejudice of our time, which will be disproved scientifically (perhaps by the fact that there aren't enough nerve cells to perform the observable operations of the mind)\". Godel uses the notion of a finite machine in an extremely general way when considering the brain as a finite machine with a finite number of parts. It is here that the identification of finite machines with Turing machines becomes evidently problematic: Is it at all plausible to think that the brain has a similarly fixed structure and fixed program as a particular Turing machine? The argumentation is problematic also on different grounds; namely, Codel takes \"human mind\" in a more general way than just the mind of anyone individual human being. Why should it be then that mind is realized through any particular brain? The proposition that the working of the human mind cannot be reduced to the working of the brain is thus not obtained as a \"direct\" consequence of the incom- pleteness theorems, but requires additional substantive assumptions: i) there are no Diophantine problems the human mind cannot solve, ii) brains are finite ma- chines with finitely many parts, and iii) finite machines with finitely many parts are Turing machines. None of these assumptions is uncontroversial; what seems not to be controversial, however, is Codel's more open formulation in [193?] that it is not possible to mechanize mathematical reasoning. That raises immediately the question, what aspects of mathematical reasoning or experience defy formaliza- tion? In his note [1974] that was published in [Wang, 325~6], Codel points to two \"vaguely defined\" processes that may lead to systematic and effective, but non- mechanical procedures, namely, the process of defining recursive well-orderings of integers for larger and larger ordinals of the second number class and that of formulating stronger and stronger axioms of infinity. The point was reiterated in a modified formulation [Godel, 1972.3] that was published only later in Collected Works II, p. 306. The [1972.3] formulation of this note is preceded by [1972.2], where Codel gives Another version of the first undecidability theorem that involves number theoretic problems of Goldbach type. This version of the theorem may be taken, Codel states, \"as an indication for the existence of mathematical yes or no questions undecidable for the human mind\". (p. 305) However, he points to a fact that \"weighs against this interpretation\", namely, that \"there do exist unexplored series of axioms which are analytic in the sense that they only explicate the con- cepts occurring in them\". As an example he points also here to axioms of infinity, \"which only explicate the content of the general concept of set\". (p. 306) If the existence of such effective, non-mechanical procedures is taken as a fact or, more 54ef. also note 13 of the Gibbs Lecture and the remark on p. 17.
On Computability 617 cautiously, as a third background assumption, then Godel's second conclusion is established: The human mind, indeed, infinitely surpasses the power of any finite machine. Though Godel calls the existence of an \"unexplored series\" of axioms of infinity a fact, he also views it as a \"vaguely defined\" procedure and emphasizes that it requires further mathematical experience; after all, its formulation can be given only once set theory has been developed \"to a considerable extent\". In the note [1972.3] Codel suggests that the process of forming stronger and stronger axioms of infinity does not yet form a \"well-defined procedure which could actually be carried out (and would yield a non-recursive number-theoretic function)\": it would require \"a substantial advance in our understanding ofthe basic concepts of mathematics\" . In the note [1974], Codel offers a prima facie startlingly different reason for not yet having a precise definition of such a procedure: it \"would require a substantial deepening of our understanding of the basic operations of the mind\". (p. 325) Godel's Remarks before the Princeton bicentennial conference in 1946 throw some light on this seeming tension. Codel discusses there not only the role axioms of infinity might play in possibly obtaining an absolute concept of demonstrabil- ity, but he also explores the possibility of an absolute mathematical \"definition of definability\". What is most interesting for our considerations here is the fact that he considers a restricted concept of human dejinability that would reflect a human capacity, namely, \"comprehensibility by our mind\". That concept should satisfy, he thinks, the \"postulate of denumerability\" and in particular allow us to define (in this particular sense) only countably many sets. \"For it has some plausibility that all things conceivable by us are denumerable, even if you disregard the ques- tion of expressibility in some language.\" (p. 3) That requirement, together with the related difficulty of the definability of the least indefinable ordinal, does not make such a concept of definability \"impossible, but only [means] that it would involve some extramathematical element concerning the psychology of the being who deals with mathematics.\" Obviously, Turing brought to bear on his definition of computability, most fruitfully, an extramathematical feature of the psychology of a human computor.P'' Godel viewed that definition in [1946], the reader may recall, as the first \"absolute definition of an interesting epistemological notion\". (p. 1) His reflections on the possibility of absolute definitions of demonstrability and definability were encouraged by the success in the case of computability. Can we obtain by a detailed study of actual mathematical experience a deeper \"under- standing of the basic operations of the mind\" and thus make also a \"substantial advance in our understanding of the basic concepts of mathematics\"? 6.3 Beyond discipline Godel's brief exploration in [1972.3] of the issue of defining a non-mechanical, but effective procedure is preceded by a severe critique of Turing. The critical attitude is indicated already by the descriptive and harshly judging title of the note, A 55Cf. Parsons' informative remarks in the Introductory Note to [Godel, 1946, 148].
618 Wilfried Sieg philosophical error in Turing's work. The discussion of Church's thesis and Tur- ing's analysis is in general fraught with controversy and misunderstanding, and the controversy begins often with a dispute over what the intended informal concept is. When Godel spotted a philosophical error in Turing's work, he assumed that Turing's argument in the 1936 paper was to show that \"mental procedures cannot go beyond mechanical procedures\". He considered the argument as inconclusive: What Turing disregards completely is the fact that mind, in its use, is not static, but constantly developing, i.e., that we understand abstract terms more and more precisely as we go on using them, and that more and more abstract terms enter the sphere of our understanding. [Col- lected Works II, p. 306] Turing did not give a conclusive argument for Godel's claim, but then it has to be added that he did not intend to argue for it. Simply carrying out a mechanical procedure does not, indeed, should not involve an expansion of our understanding. Turing viewed the restricted use of mind in computations undoubtedly as static; after all, it seems that this feature contributed to the good reasons for replacing states of mind of the human computor by \"more definite physical counterparts\" in section 9, part III, of his classical paper. Even in his work of the late 1940s and early 1950s that deals explicitly with mental processes, Turing does not argue that mental procedures cannot go beyond mechanical procedures. Mechanical processes are, as a matter of fact, still made precise as Turing machine computations; machines that might exhibit intelligence have, in contrast, a more complex structure than Turing machines. Conceptual idealization and empirical adequacy are now being sought for quite different pur- poses, and Turing is trying to capture clearly what Godel found missing in his analysis for a broader concept of humanly effective calculability, namely, \"... that mind, in its use, is not static, but constantly developing\". 56 Codel continued the above remark in this way: There may exist systematic methods of actualizing this development, which could form part of the procedure. Therefore, although at each stage the number and precision of the abstract terms at our disposal 56[Godel, 1972.3J may be viewed, Codel mentions, as a note to the word \"mathematics\" in the sentence, \"Note that the results mentioned in this postscript do not establish any bounds of the powers of human reason, but rather for the potentialities of pure formalism in mathematics.\" This sentence appears in the 1964 Postscriptum to the Princeton Lectures Codel gave in 1934; Collected Works I, pp. 369-371. He states in that Postscriptum also that there may be \"finite non-mechanical procedures\" and emphasizes, as he does in many other contexts, that such pro- cedures would \"involve the use of abstract terms on the basis of their meaning\". (Note 36 on p. 370 of Collected Works 1) Other contexts are found in volume III of the Collected Works, for example, the Gibbs Lecture (p. 318 and note 27 on that very page) and a related passage in \"Is mathematics syntax of language?\" (p, 344 and note 24) These are systematically connected to Codel's reflections surrounding (the translation of) his Dialectica paper [1958J and [1972J. A thorough discussion of these issues cannot be given here; but as to my perspective on the basic difficulties, see the discussion in section 4 of my paper \"Beyond Hilbert's Reach?\".
On Computability 619 may be finite, both (and, therefore, also Turing's number of distin- guishable states of mind) may converge toward infinity in the course of the application of the procedure. The particular procedure mentioned as a plausible candidate for satisfying this description is the process of forming stronger and stronger axioms of infinity. We saw that the two notes, [1972-3] and [1974], are very closely connected. However, there is one subtle and yet substantive difference. In [1974] the claim that the number of possible states of mind may converge to infinity is obtained as a con- sequence of the dynamic development of mind. That claim is then followed by a remark that begins, in a superficially similar way, as the first sentence in the above quotation: Now there may exist systematic methods of accelerating, specializing, and uniquely determining this development, e.g. by asking the right questions on the basis of a mechanical procedure. Clearly, I don't have a full understanding of these enigmatic observations, but there are three aspects that are clear enough. First, mathematical experience has to be invoked when asking the right questions; second, aspects of that experience may be codified in a mechanical procedure and serve as the basis for the right questions; third, the answers may involve abstract terms that are incorporated into the non-mechanical mental procedure. We should not dismiss or disregard Codel's methodological remark that \"asking the right questions on the basis of a mechanical procedure\" may be part of a systematic method to push forward the development of mind. It allows us, even on the basis of a very limited understanding, to relate Godel's reflections tenuously with Turing's proposal for investigating matters. Prima facie their perspectives are radically different, as Codel proceeds by philosophical argument and broad, speculative appeal to mathematical experience, whereas Turing suggests attacking the problem largely by computational experimentation. That standard view of the situation is quite incomplete. In his paper Intelligent machinery written about ten years after [1939], Turing states what is really the central problem of cognitive psychology: If the untrained infant's mind is to become an intelligent one, it must acquire both discipline and initiative. So far we have been considering only discipline [via the universal machine, W.S.]. ... But discipline is certainly not enough in itself to produce intelligence. That which is required in addition we call initiative. This statement will have to serve as a definition. Our task is to discover the nature of this residue as it occurs in man, and to try and copy it in machines. (p. 21) How can we transcend discipline? A hint is provided in Turing's 1939 paper, where he distinguishes between ingenuity and intuition. He observes that in formal logics
620 Wilfried Sieg their respective roles take on a greater definiteness. Intuition is used for \"setting down formal rules for inferences which are always intuitively valid\", whereas in- genuity is to \"determine which steps are the more profitable for the purpose of proving a particular proposition\". He notes: In pre-Codel times it was thought by some that it would be possible to carry this programme to such a point that all the intuitive judgements of mathematics could be replaced by a finite number of these rules. The necessity for intuition would then be entirely eliminated. (p. 209) The distinction between ingenuity and intuition, but also the explicit link of in- tuition to incompleteness, provides an entry to exploit through concrete compu- tational work the \"parallelism\" of Turing's and Godel's considerations. Copying the residue in machines is the task at hand. It is extremely difficult in the case of mathematical thinking, and Godel would argue it is an impossible one, if ma- chines are Turing machines. Turing would agree. Before we can start copying, we have to discover at least partially the nature of the residue, with an emphasis on \"partially\", through some restricted proposals for finding proofs in mathematics. Let us look briefly at the broad setting. Proofs in a formal logic can be obtained uniformly by a patient search through an enumeration of all theorems, but additional intuitive steps remain necessary because of the incompleteness theorems. Turing suggested particular intuitive steps in his ordinal logics; his arguments are theoretical, but connect directly to the discussion of actual or projected computing devices that appears in his Lecture to London Mathematical Society and in Intelligent Machinery. In these papers he calls for intellectual searches (i.e., heuristically guided searches) and initiative (that includes, in the context of mathematics, proposing new intuitive steps). However, he emphasizes [1947, 122]: As regards mathematical philosophy, since the machines will be doing more and more mathematics themselves, the centre of gravity of the human interest will be driven further and further into philosophical questions of what can in principle be done etc. Codel and Turing, it seems, could have cooperated on the philosophical questions of what can in principle be done. They also could have agreed, so to speak ter- minologically, that there is a human mind whose working is not reducible to the working of any particular brain. Towards the end of Intelligent Machinery Tur- ing emphasizes, \"the isolated man does not develop any intellectual power\", and argues: It is necessary for him to be immersed in an environment of other men, whose techniques he absorbs during the first twenty 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.
On Computability 621 Turing calls this, appropriately enough, a cultural search and contrasts it with more limited, intellectual searches. Such searches, Turing says definitionally, can be carried out by individual brains. In the case of mathematics they would include searches through all proofs and would be at the center of \"research into intelligence of machinery\". Turing had high expectations for machines' progress in mathemat- ics; indeed, he was unreasonably optimistic about their emerging capacities. Even now it is a real difficulty to have machines do mathematics on their own: work on Godel's \"theoretical\" questions has to be complemented by sustained efforts to meet Turing's \"practical\" challenge. I take this to be one of the ultimate mo- tivations for having machines find proofs in mathematics, i.e., proofs that reflect logical as well as mathematical understanding. When focusing on proof search in mathematics it may be possible to use and expand logical work, but also draw on experience of actual mathematical practice. I distinguish two important features of the latter: i) the refined conceptual orga- nization internal to a given part of mathematics, and ii) the introduction of new abstract concepts that cut across different areas of mathematics.57 Logical for- mality per se does not facilitate the finding of arguments from given assumptions to a particular conclusion. However, strategic considerations can be formulated (for natural deduction calculi) and help to bridge the gap between assumptions and conclusion, suggesting at least a very rough structure of arguments. These logical structures depend solely on the syntactic form of assumptions and conclu- sion; they provide a seemingly modest, but in fact very important starting-point for strategies that promote automated proof search in mathematics. Here is a pregnant general statement that appeals primarily to the first feature of mathematical practice mentioned above: Proofs provide explanations of what they prove by putting their conclusion in a context that shows them to be correct.58 The deductive organization of parts of mathematics is the classical methodology for specifying such contexts. \"Leading mathematical ideas\" have to be found, proofs have to be planned: I take this to be the axiomatic method turned dy- namic and 10ca1. 59 This requires undoubtedly the introduction of heuristics that reflect a deep understanding of the underlying mathematical subject matter. The broad and operationally significant claim is, that we have succeeded in isolat- ing the leading ideas for a part of mathematics, if that part can be developed by machine - automatically, efficiently, and in a way that is furthermore easily accessible to human mathernaticians.v\" This feature can undoubtedly serve as a 57That is, it seems to me, still far removed from the introduction of \"abstract terms\" in Codel's discussions. They are also, if not mainly, concerned with the introduction of new mathematical objects. Cf. note 10. 5 8That is a classical observation; just recall the dual experiences of Hobbes and Newton with the Pythagorean Theorem, when reading Book 1 of Euclid's Elements. 59Saunders MacLane articulated such a perspective and pursued matters to a certain extent in his Cottingen dissertation. See his papers [1935] and [1979]. 6oTo mention one example: in an abstract setting, where representability and derivability conditions, but also instances of the diagonal lemma are taken for granted as axioms, Oodel's proofs can be found fully automatically; see [Sieg and Field]. The leading ideas used to extend the basic logical strategies are very natural; they allow moving between object and meta-theoretic
622 Wilfried Sieg springboard for the second feature I mentioned earlier, one that is so characteristic of the developments in modern mathematics, beginning in the second half of the 19 t h century: the introduction of abstract notions that do not have an intended interpretation, but rather are applicable in many different contexts. (Cf. section 5.5.) The above general statement concerning mathematical explanation can now be directly extended to incorporate also the second feature of actual mathematical experience. Turing might ask, whether machines can be educated to make such reflective moves on their own. It remains a deep challenge to understand better the very nature of reason- ing. A marvelous place to start is mathematics; where else do we find such a rich body of systematically and rigorously organized knowledge that is structured for intelligibility and discovery? The appropriate logical framework should un- doubtedly include a structure theory of (mathematical) proofs. Such an extension of mathematical logic and in particular of proof theory interacts directly with a sophisticated automated search for humanly intelligible proofs. How far can this be pushed? What kind of broader leading ideas will emerge? What deeper under- standing of basic operations of the mind will be gained? We'll hopefully find out and, thus, uncover with strategic ingenuity part of Turing's residue and capture also part of what Codel considered as \"humanly effective\" , but not mechanical - \"by asking the right questions on the basis of a mechanical procedure\". 6.4 (Supra-) Mechanical devices Turing machines codify directly the most basic operations of a human computor and can be realized as physical devices, up to a point. Codel took for granted that finite machines just are (computationally equivalent to) Turing machines. Simi- larly, Church claimed that Turing machines are obtained by natural restrictions from machines occupying a finite space and with working parts of finite size; he viewed the restrictions \"of such a nature as obviously to cause no loss of general- ity\". (Cf. section 4.5.) In contrast to Oodel and Church, Gandy did not take this equivalence for granted and certainly not as being supported by Turing's analysis. He characterized machines informally as discrete mechanical devices that can carry out massively parallel operations. Mathematically Gandy machines are discrete dynamical systems satisfying boundedness and locality conditions that are physi- cally motivated; they are provably not more powerful than Turing machines. (Cf. section 5.2.) Clearly one may ask: Are there plausible broader concepts of com- putations for physical systems? If there are systems that carry out supra-Turing processes they cannot satisfy the physical restrictions motivating the bounded- ness and locality conditions for Gandy machines. I.e., such systems must violate either the upper bound on signal propagation or the lower bound on the size of distinguishable atomic components.P! considerations via provability elimination and introduction rules. 61 For a general and informative discussion concerning \"hypercomputation\" , see Martin Davis's paper [2004J. A specific case of \"computations\" beyond the 'TUring limit is presented through
On Computability 623 In Paper machines, Mundici and I diagnosed matters concerning physical pro- cesses in the following way. Every mathematical model of physical processes comes with at least two problems, \"How accurately does the model capture physical re- ality, and how efficiently can the model be used to make predictions?\" What is distinctive about modern developments is the fact that, on the one hand, com- puter simulations have led to an emphasis on algorithmic aspects of scientific laws and, on the other hand, physical systems are being considered as computational devices that process information much as computers do. It seems, ironically, that the mathematical inquiry into paper machines has led to the point where (effective) mathematical descriptions of nature and (natural) computations for mathematical problems coincide. How could we have physical processes that allow supra- Turing computations? If harnessed in a machine, we would have a genuinely supra-mechanical device. However, we want to be able to effectively determine mathematical states from other such states ~ that \"parallel\" physical states, i.e., we want to make predic- tions and do that in a sharply intersubjective way. If that would not be the case, why would we want to call such a physical process a computation and not just an oracle? Wouldn't that undermine the radical intersubjectivity computations were to insure? There are many fascinating open issues concerning mental and physical processes that mayor may not have adequate computational models. They are empirical, broadly conceptual, mathematical and, indeed, richly interdisciplinary. ACKNOWLEDGMENTS The presentation given here has evolved over almost two decades, and I have drawn systematically on my earlier publications, in particular on [1994]' [1996], [1997], [2002a,b] and [2007]. Indeed, parts 5.2 and 5.3 are taken from [2002b]; part 6 was published as [2007]. Pioneering papers from Dedekind, Kronecker and Hilbert through Church, Godel, Kleene, Post and Turing to Gandy have been a source of continuing inspiration. The historical accounts by Davis, Gandy, Kleene and Rosser have been helpful in clarifying many developments, so has the correspon- dence between Godel and Herbrand, as well as that between Bernays and Church. A detailed review of classical arguments for Church's and Turing's theses is found in Kleene's Introduction to Metamathematics, in particular, sections 62,63 and 70; section 6.4 of [Shoenfield, 1967] contains a careful discussion of Church's Thesis. The first chapter of [Odifreddi, 1989] and Cooper's essay [1999] provide a broad perspective for the whole discussion, as does [Soare, 1999]. Much of the material was presented in talks and seminars, and I am grateful to critical responses by the many audiences; much of the work was done in collaboration, and I owe particular Siegelmann's ANNs (artificial neural nets): they perform hypercomputations only if arbitrary reals are admitted as weights. Finally, there is the complex case of quantum computations; if I understand matters correctly, they allow a significant speed-up for example in Shore's algorithm, but the current versions don't go beyond the Turing limit.
624 Wilfried Sieg debts to John Byrnes, Daniele Mundici, Mark Ravaglia and last, but undoubtedly not least, Guglielmo Tamburrini. Finally, the material was organized for four sem- inars I gave in November of 2004 at the University of Bologna; I am grateful to Rossella Lupacchini and Giorgio Sandri for their invitation, critical support and warm hospitality. BIBLIOGRAPHY [Ackermann, 1925J W. Ackermann. Begriindung des \"tertium non datur\" mittels der Hilbertschen Theorie der Widerspruchsfreiheit. Mathematische Annalen, 93: 1-26, 1925. [Ackermann, 1928] W. Ackermann. Zum Hilbertschen Aufbau der rellen Zahlen. Mathematische Annalen, 99: 118-133, 1928. [Baldwin, 2004] J. Baldwin. Review of [Wolfram, 2002}. Bulletin of Symbolic Logic, 10(1): 112- 114, 2004. [Behmann, 1922J H. Behmann. Beitrage zur Algebra der Logik, insbesondere zum Entschei- dungsproblem. Mathematische Annalen, 86: 163-229, 1922. [Benacerraf and Putnam, 1983J P. Benacerraf and H. Putnam. Philosophy of Mathematics - Selected Readings (Second edition). Cambridge University Press, 1983. [Bernays, 1918J P. Bernays. Beitriiqe zur axiomatischen Behandlung des Loqik-Kalkiils. Habili- tationsschrift. Giittingen, 1918. [Bernays, 1922] P. Bernays. Uber Hilberts Gedanken zur Grundlegung der Arithmetik. Jahres- bericht der Deutschen Mathematiker Vereinigung, 31: 10--19, 1922. [Bernays, 1926J P. Bernays. Axiomatische Untersuchung des Aussagen-Kalkuls der \"Principia mathematica\". Mathematische Zeitschrift, 25: 305-320, 1926. [Bernays, 1967J P. Bernays. Hilbert, David. In P. Edwards (Editor in Chief), The Encyclopedia of Philosophy, vol. 3, pages 496-504, 1967. [Bernays, 1976] P. Bernays. Abhandlungen zur Philosophie der Mathematik. Wissenschaftliche Buchgesellschaft, Darmstadt, 1976. [Boniface and Schappacher, 2001] J. Boniface and N. Schappacher. Sur Ie concept de nombre en mathernatique - Cours inedit de Leopold Kronecker it Berlin (1891). Revue d'histoire des mathematiques, 7: 207-275, 2001. [Blichi, 1990J J. R. BlichL The Collected Works of J. Richard Buchi. S. Mac Lane and D. Siefkes (eds.), Springer Verlag, 1990. [Byrnes and W. Sieg, 1996J J. Byrnes and W. Sieg. A graphical presentation of Gandy's parallel machines (Abstract). Bulletin of Symbolic Logic, 2: 452-3, 1996. [Carnap, 1931] R. Carnap. Die logizistische Grundlegung der Mathematik. Erkenntnis, 2: 91- 105, 1931. (Translation in [Benacerraf and Putnam]). [Church, 1932] A. Church. A set of postulates for the foundation of logic I. Annals of Mathe- matics, 33(2): 346-366, 1932. [Church, 1933J A. Church. A set of postulates for the foundation of logic II. Annals of Mathe- matics, 34(2): 839-864, 1933. [Church, 1934] A. Church. The Richard Paradox. American Mathematical Monthly, 41: 356- 361, 1934. [Church, 1935] A. Church. An unsolvable problem of elementary number theory. Preliminary report (abstract). Bulletin of the American Mathematical Society, 41: 332-333, 1935. [Church, 1936J A. Church. An unsolvable problem of elementary number theory. American Jour- nal of Mathematics, 58: 345-363, 1936. (Reprinted in [Davis, 1965].) [Church, 1936a] A. Church. A note on the Entscheidungsproblem. Journal of Symbolic Logic, 1(1): 40--41, 1936. [Church, 1937] A. Church. Review of [Turing, 1936]. Journal of Symbolic Logic, 2(1): 42-43, 1937. [Church, 1937aJ A. Church. Review of [Post, 1936J. Journal of Symbolic Logic, 2(1): 43, 1937. [Church and Kleene, 1935J A. Church and S. C. Kleene. Formal definitions in the theory of ordinal numbers. Bulletin of the American Mathematical Society, 41: 627, 1935. [Church and Kleene, 1936J A. Church and S. C. Kleene. Formal definitions in the theory of ordinal numbers. Fundamenui Mathematicae, 28: 11-21, 1936.
On Computability 625 [Colvin, 1997] S. Colvin. Intelligent Machinery: Turing's Ideas and Their Relation to the Work of Newell and Simon. M.S. Thesis, Carnegie Mellon University, Department of Philosophy, 63 pp., 1997. [Cooper, 1999J S. B. Cooper. Clockwork or Turing Universe - Remarks on causal determinism and computability. In S. B. Cooper and J. K. Truss (eds.), Models and Computability, London Mathematical Society, Lecture Note Series 259, Cambridge University Press, pages 63-116, 1999. [Copeland, 2004] J. Copeland. The Essential Turing. Oxford University Press, 2004. [Crossley, 1975] J. N. Crossley (ed.). Algebra and Logic; Papers from the 1974 Summer Research Institute of the Australasian Mathematical Society; Monash University. Springer Lecture Notes in Mathematics 450, 1975. [Crossley, 1975a] J. N. Crossley. Reminiscences of logicians. In [Crossley, 1975], 1-62, 1975. [Davis, 1958] M. Davis. Computability and Unsolvability. McGraw-Hill, New York, 1958. (A Dover edition was published in 1973 and 1982.) [Davis, 1965] M. Davis (ed.). The Undecidable, Basic papers on undecidable propositions, un- solvable problems and computable functions. Raven Press, Hewlett, New York, 1965. [Davis, 1973J M. Davis. Hilberts tenth problem is unsolvable. American Mathematical Monthly, 80: 233-269, 1973. (Reprinted in the second Dover edition of [Davis, 1958].) [Davis, 1982] M. Davis. Why Codel didnt have Church's Thesis. Information and Control, 54: 3-24, 1982. [Davis, 2004] M. Davis. The myth of hypercomputation. In C. Teuscher (ed.), Alan Turing: Life and Legacy of a Great Thinker. Springer, 195--211, 2004. [Dawson, 1986J J. Dawson. A Godel chronology. In [Godel, 1986, 37-43J. [Dawson, 1991J J. Dawson. Prelude to recursion theory: the Codel-Herbrand correspondence. Manuscript, 1991. [Dawson, 1997] J. Dawson. Logical Dilemmas. A. K. Peters, Wellesley, Massachusetts, 1997. [De Pisapia, 2000] N. De Pisapia. Gandy Machines: An Abstract Model of Parallel Computation for Turing Machines, the Game of Life, and Artificial Neural Networks. M.S. Thesis, Carnegie Mellon University, Department of Philosophy, 75 pp., 2000. [Dedekind, 1888J R. Dedekind. Was sind und was sollen die Zahlen? Vieweg, Braunschweig, 1888. (Translation in [Ewald, 1996].) [Ewald, 1996] W. Ewald (ed.). From Kant to Hilbert: A Source Book in the Foundations of Mathematics. Two volumes. Oxford University Press, 1996. [Feferman, 1988] S. Feferman. Turing in the land of O(z). In [Herken, 1988, 113-147]. [Frege, 1879] G. Frege. Begriffsschrift. Verlag Nebert, Halle, 1879. [Frege, 1893] G. Frege. Grundgesetze der Arithmetik, begriffsschrijtlich abgeleitet. Jena, 1893. (Translation in [Geach and Black].) [Frege, 1969] G. Frege. In H. Hermes, F. Kambartel, and F. Kaulbach (eds.), Nachgelassene Schrijten. Meiner Verlag, Hamburg, 1969. [Frege, 1984] G. Frege. In B. McGuinness (ed.), Collected Papers on Mathematics, Logic, and Philosophy. Oxford University Press, 1984. [Gandy, 1980] R. Gandy. Churchs Thesis and principles for mechanisms. In J. Barwise, H. J. Keisler, and K. Kunen (eds.), The Kleene Symposium. North-Holland Publishing Company, Amsterdam, 123-148, 1980. [Gandy, 1988] R. Gandy. The confluence of ideas in 1936. In [Berken, 1988, 55-111]. [Geach and Block, 1977J Geach and Block. Translations from the Philosophical Writings of Got- tlob F'rege. Blackwell, Oxford, 1977. [Godel, 1931] K. Codel. tiber formal unentscheidbare Siitze der Principia Mathematica und ver- wandter Systeme I. Monatshefte fur Mathematik und Physik, 38: 173-198, 1931. (Translation in [Davis, 1965], [van Heijenoort, 1967J and Collected Works I.) [Godel, 1931a] K. Codel. Diskussion zur Grundlegung der Mathematik. In Collected Works I, 200--204, 1931. [Godel, 1933J K. Codel. Zur intuitionistischen Arithmetik und Zahlentheorie. In Collected Works I, 286-295, 1933. [Godel, 1933a] K. Codel. The present situation in the foundations of mathematics. In Collected Works III, 45-53, 1933. [Godel, 1934] K. Codel. On undecidable propositions of formal mathematical systems. In Col- lected Works I, 346-371, 1934. [Godel, 1936] K. Godel. tiber die Lange von Beweisen. In Collected Works I, 396-399, 1936.
626 Wilfried Sieg [Codel, 1946] K. GCidel. Undecidable Diophantine propositions. In Collected Works III, 164-175, 1946. [GCidel, 1938] K. GCidel. Vortrag bei Zilsel. In Collected Works III, 86-113, 1938. [GCidel, 1946] K. GCidel. Remarks before the Princeton bicentennial conference on problems in mathematics. In Collected Works II, 150-153, 1946. [Gi:idel, 1951] K. GCidel. Some basic theorems on the foundations of mathematics and their implications. In Collected Works III, 304-323, 1951. [GCidel, 1963] K. GCidel. Postscriptum for [1931J. In Collected Works I, 195, 1963. [Codel, 1964J K. Gi:idel. Postscriptum for [1934]. In Collected Works I, 369-371, 1964. [Gi:idel, 1972] K. GCidel. Some remarks on the undecidability results. In Collected Works II, 305--306, 1972. [Codel, 1972.1] K. GCidel. The best and most general version of the unprovability of consistency in the same system. First of the three notes [1972]. [Codel, 1972.2] K. GCidel. Another version of the first undecidability result. Second of the three notes [1972]. [GCidel, 1972.3J K. G6del. A philosophical error in Turings work. Third of the three notes [1972]. [Codel, 1974] K. G6del. Note in [Wang, 1974, 325-6J. [GCidel, 1986J K. G6del. Collected Works 1. Oxford University Press, 1986. [Codel, 1990J K. G6del. Collected Works II. Oxford University Press, 1990. [Codel, 1995J K. Gi:idel. Collected Works III. Oxford University Press, 1995. [Codel, 2003] K. G6del. Collected Works IV- V. Oxford University Press, 2003. [Griffor, 1999] E. R. Griffor (ed.). Handbook of Computability Theory. Elsevier, 1999. [Herbrand, 1928] J. Herbrand. On proof theory. 1928. In [Herbrand, 1971, 29-34]. [Herbrand, 1929] J. Herbrand. On the fundamental problem of mathematics. 1929. In [Herbrand, 1971, 41-43J. [Herbrand, 1930J J. Herbrand. Investigations in proof theory. 1930. In [Herbrand, 1971, 44-202J. [Herbrand, 1931] J. Herbrand. On the fundamental problem of mathematical logic. 1931. In [Herbrand, 1971, 215-259J. [Herbrand, 1931aJ J. Herbrand. On the consistency of arithmetic. 1931. In [Herbrand, 1971, 282-298]. [Herbrand, 1971J J. Herbrand. Logical Writings. W. Goldfarb (ed.). Harvard University Press, 1971. [Herken, 1988J R. Herken (ed.). The Universal Turing Machine - A Half-Century Survey. Oxford University Press, 1988. [Herron, 1995] T. Herron. An Alternative Definition of Pushout Diagrams and their Use in Characterizing K-Graph Machines. Carnegie Mellon University, 1995. [Heyting, 1930J A. Heyting. Die formalen Regeln der intuitionistischen Logik. Sitzungsberichte der Preussischen Akademie der Wissenschaften, physikalisch-mathematische Klasse, 42-56, 1930. [Heyting, 1930a] A. Heyting. Die formalen Regeln der intuitionistischen Mathematik. Ibid., 57- 71, 158-169, 1930. [Heyting, 1931J A. Heyting. Die intuitionistische Grundlegung der Mathematik. Erkenntnis, 2: 106-115, 1931. (Translation in [Benacerraf and Putnam, 1983].) [Hilbert, 1899J D. Hilbert. Grundlagen der Geometric. Teubner, Leipzig, 1899. [Hilbert, 1900J D. Hilbert. Uber den Zahlbegriff. Jahresbericht der Deutschen Mathematiker Vereinigung, 8: 180-194, 1900. [Hilbert, 1901] D. Hilbert. Mathematische Probleme Vortrag, gehalten auf dem internationalen Mathematiker-Kongref3 zu Paris 1900. Archiv der Mathematik und Physik, 1: 44-63 and 213- 237, 1901. (Partial translation in [Ewald, 1996J.) [Hilbert, 1917*] D. Hilbert. Prinzipien der Mathematik. Lectures given by Hilbert and Bernays in the winter term of the academic year 1917/18. 1917*. [Hilbert, 1921*] D. Hilbert. Grundlagen der Mathematik. Lectures given by Hilbert and Bernays in the winter term of the academic year 1921/22. 1921*. [Hilbert, 1922] D. Hilbert. Neubegriindung der Mathematik. Abhandlungen aus dem mathema- tischen Seminar der Hamburgischen Universitiit, 1: 157-177, 1922. [Hilbert, 1923J D. Hilbert. Die logischen Grundlagen der Mathematik. Mathematische Annalen, 88: 151-165,1923. [Hilbert, 1926] D. Hilbert. Uber das Unendliche. Mathematische Annalen, 95: 161-190, 1926.
On Computability 627 [Hilbert, 1928] D. Hilbert. Die Grundlagen der Mathematik. Abhandlungen aus dem mathema- tischen Seminar tier Hamburgischen Uniuersitiit, 6: 65-85, 1928. [Hilbert, 1929] D. Hilbert. Probleme der Grundlegung der Mathematik. Mathematische An- nalen, 102: 1-9, 1929. [Hilbert, 1931] D. Hilbert. Die Grundlegung der elementaren Zahlenlehre. Mathematische An- nalen, 104: 485-494, 1931. [Hilbert and Ackermann, 1928J D. Hilbert and W. Ackermann. Grundziiqe der theoretischen Logik. Springer Verlag, Berlin, 1928. [Hilbert and Bernays, 1934] D. Hilbert and P. Bernays. Grundlagen der Mathematik 1. Springer Verlag, Berlin, 1934. [Hilbert and Bernays, 1939J D. Hilbert and P. Bernays. Grundlagen der Mathematik II. Springer Verlag, Berlin, 1939. [Kalmar, 1955] L. Kalmar. Uber ein Problem, betreffend die Definition des Begriffes der allgemein-rekursiven Funktion. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik, 1: 93-5, 1955. [Kleene, 1935J S. C. Kleene. General recursive functions of natural numbers. Bulletin of the American Mathematical Society, 41: 489, 1935. [Kleene, 1935a] S. C. Kleene. >.-definability and recursiveness. Bulletin of the American Math- ematical Society, 41: 490, 1935. [Kleene, 1936] S. C. Kleene. General recursive functions of natural numbers. Mathematische Annalen, 112: 727-742, 1936. (Reprinted in [Davis, 1965J.) [Kleene, 1936a] S. C. Kleene. A note on recursive functions. Bulletin of the American Mathe- matical Society, 42: 544-546, 1936. [Kleene, 1952] S. C. Kleene. Introduction to Metamathematics. Elsevier, Groningen, 1952. [Kleene, 1981] S. C. Kleene. Origins of recursive function theory. Annals of the History of Com- puting, 3: 52-66, 1981. [Kleene, 1987J S. C. Kleene. Reflections on Church's Thesis. Notre Dame Journal of Formal Logic, 28: 490-498, 1987. [Kolmogorov and Uspensky, 1963J A. Kolmogorov and V. Uspensky. On the definition of an algorithm. AMS Translations, 21(2): 217-245, 1963. [Kronecker, 1887] L. Kronecker. Uber den Zahlbegriff. In Philosophische Aufsiitze, Eduard Zeller zu seinem fiinfzigjiihrigen Doctorjubilaum gewidmet. Fues, Leipzig, 271-74, 1887. (Translation in [Ewald, 1996].) [Kronecker, 1891J L. Kronecker. Uber den Zahlbegriff in der Mathematik. 1891. In [Boniface and Schappacher, 2001]. [Lamport and Lynch, 1990] L. Lamport and N. Lynch. Distributed Computing: Models and Methods. In J. van Leeuwen (ed.), Handbook of Theoretical Computer Science. Elsevier, Groningen, 1990. [Lowenheim, 1915] L. Lowenheim. Uber M6glichkeiten im Relativkalkiil, Mathematische An- nalen, 76: 447-470. (Translation in [van Heijenoort, 1967J.) [MacLane, 1934] S. MacLane. Abqekiirzte Beweise im Logikkalkul. Inaugural-Dissertation, G6ttingen, 1934. [MacLane, 1935J S. MacLane. A logical analysis of mathematical structure. The Monist, 118- 130, 1935. [MacLane, 1979] S. MacLane. A late return to a thesis in logic. In 1. Kaplansky (ed.), Saunders MacLane Selected Papers. Springer-Verlag, 1979. [Mancosu, 1999] P. Mancosu. Between Russell and Hilbert: Behmann on the foundations of mathematics. Bulletin of Symbolic Logic, 5(3): 303-330, 1999. [Mancosu, 2003] P. Mancosu. The Russellian influence on Hilbert and his school. Synthese, 137: 59-101, 2003. [Mates, 1986J B. Mates. The Philosophy of Leibniz. Oxford University Press, 1986. [Mendelson, 1990J E. Mendelson. Second thoughts about Church's Thesis and mathematical proofs. Journal of Philosophy, 87(5): 225-33, 1990. [Mundici and Sieg, 1995] D. Mundici and W. Sieg. Paper machines. Philosophia Mathematica, 3: 5-30, 1995. [Odifreddi, 1989] Odifreddi. Classical Recursion Theory. North Holland Publishing Company, Amsterdam, 1989.
628 Wilfried Sieg [Odifreddi, 1990J Odifreddi. About Logics and Logicians - A Palimpsest of Essays by Georg Kreisel. Volume II: Mathematics; manuscript, 1990. [Parsons, 1995J C. D. Parsons. Quine and Godel on analyticity. In P. Leonardi and M. Santam- brogio (eds.), On Quine. Cambridge University Press, 1995. [Post, 1936J E. Post. Finite combinatory processes. Formulation 1. Journal of Symbolic Logic, 1: 103-5, 1936. [Post, 1941J E. Post. Absolutely unsolvable problems and relatively undecidable propositions Account of an anticipation. 1941. (In [Davis, 1965, 340-433].) [Post, 1943] E. Post. Formal reductions of the general combinatorial decision problem. Amereri- can Journal of Mathematics, 65(2): 197-215, 1943. [Post, 1947] E. Post. Recursive unsolvability of a problem of Thue. Journal of Symbolic Logic, 12: 1-11, 1947. [Post, 1994J E. Post. Solvability, Provability, Definability: The Collected Works of Emil L. Post. M. Davis (ed.). Birkhauser, 1994. [Ravaglia, 2003J M. Ravaglia. Explicating the Finitist Standpoint. Ph.D. Thesis; Department of Philosophy, Carnegie Mellon University, 2003. [Rosser, 1935J B. Rosser. A mathematical logic without variables. Annals of Mathematics, 36: 127-150, 1935. [Rosser, 1936] B. Rosser. Extensions of some theorems of Godel and Church. Journal of Symbolic Logic, 1: 87-91, 1936. [Rosser, 1984] B. Rosser. Highlights of the history of the lambda-calculus. Annals of the History of Computing, 6(4): 337-349, 1984. [Shanker, 1987J S. G. Shanker. Wittgenstein versus Turing on the nature of Church's Thesis. Notre Dame Journal of Formal Logic, 28(4): 615-649, 1987. [Shanker, 1998J S. G. Shanker. Wittgenstein's Remarks on the Foundations of AI. Routledge, London and New York, 1998. [Shapiro, 1983J S. Shapiro. Remarks on the development of computability. History and Philos- ophy of Logic, 4: 203-220, 1983. [Shapiro, 1994] S. Shapiro. Metamathematics and computability. In 1. Grattan-Guinness (ed.), Encyclopedia of the History and Philosophy of the Mathematical Sciences. Routledge, London, 644-655, 1994. [Shapiro,2006J S. Shapiro. Computability, proof, and open-texture. In A. Olszewski, J. Wolen- ski, and R. Janusz (eds.), Church's Thesis after 70 Years. Logos Verlag, Berlin, 355-390, 2006. [Shepherdson, 1988J J. Shepherdson. Mechanisms for computing over arbitrary structures. In [Herken, 1988, 581-601J. [Shoenfield, 1967J J. Shoenfield. Mathematical Logic. Addison-Wesley, Reading, Massachusetts, 1967. [Sieg, 1994J W. Sieg. Mechanical procedures and mathematical experience. In A. George (ed.), Mathematics and Mind. Oxford University Press, 71-117, 1994. [Sieg, 1996J W. Sieg. Aspects of mathematical experience. In E. Agazzi and G. Darvas (eds.), Philosophy of mathematics today. Kluwer, 195-217, 1996. [Sieg, 1997J W. Sieg. Step by recursive step: Church's analysis of effective calculability. Bulletin of Symbolic Logic, 3: 154-80, 1997. [Sieg, 1999] W. Sieg. Hilbert's programs: 1917-1922. Bulletin of Symbolic Logic, 5(1): 1-44, 1999. [Sieg,2002J W. Sieg. Beyond Hilberts Reach? In D. B. Malalment (ed.), Reading Natural Phi- losophy. Open Court, Chicago, 363-405, 2002. [Sieg, 2002a] W. Sieg. Calculations by man and machine: conceptual analysis. Lecture Notes in Logic, 15: 390-409, 2002. [Sieg, 2002b] W. Sieg. Calculations by man and machine: mathematical presentation. In P. Cardenfors, J. Wolenski and K. Kijania-Placek (eds.), In the Scope of Logic, Methodology and Philosophy of Science, volume one of the llth International Congress of Logic, Methodology and Philosophy of Science, Cracow, August 1999. Kluwer, Synthese Library volume 315: 247- 262, 2002. [Sieg, 2005J W. Sieg. Only two letters. Bulletin of Symbolic Logic, 1l(2): 172-184, 2005. [Sieg, 2006J W. Sieg. Codel on computability. Philosophia Mathematica, 14: 189-207, 2006. [Sieg, 2007J W. Sieg. On mind and Turing's machines. Natural Computing, 6: 187-205, 2007.
On Computability 629 [Sieg and Byrnes, 1996] W. Sieg and J. Byrnes. K-graph machines: generalizing Turing's ma- chines and arguments. In P. Hajek (ed.), Godel '96. Lecture Notes in Logic 6, Springer Verlag, 98~1l9, 1996. [Sieg and Byrnes, 1999] W. Sieg and J. Byrnes. G6del, Turing, and K-graph machines. In A. Cantini, E. Casari, P. Minari (eds.), Logic and Foundations of Mathematics. Synthese Library 280, Kluwer, 57-66, 1999. [Sieg and Byrnes, 1999a] W. Sieg and J. Byrnes. An abstract model for parallel computations: Gandy's Thesis. The Monist, 82(1): 150-64, 1999. [Sieg and Field, 2005] W. Sieg and C. Field. Automated search for G6del's proofs. Annals of Pure and Applied Logic, 133: 319---338, 2005. [Sieg and Parsons, 1995J W. Sieg and C. D. Parsons. Introductory Note to [Codel, 1938]. In cssa» Collected Works III, 62-85, 1995. [Sieg and Ravaglia, 2005] W. Sieg and M. Ravaglia. David Hilbert and Paul Bernays, Grundla- gen der Mathematik. In 1. Grattan-Guinness (ed.), Landmark Writings in Western Mathe- matics, 1640-1940. Elsevier, 981-999, 2005. [Sieg and Schlimm, 2005] W. Sieg and D. Schlimm. Dedekind's analysis of number: Systems and axioms. Synthese, 147: 121-170,2005. [Sieg et al., 2002] W. Sieg, R. Sommer, and C. Talcott (eds.). Reflections on the Foundations of Mathematics - Essays in Honor of Solomon Feferman. Association for Symbolic Logic, Lecture Notes in Logic 15, 2002. [Siegelmann, 1997] H. T. Siegelmann. Neural Networks and Analog Computation - Beyond the Turing Limit. Birkhauser, 1997. [Sinaceur, 2000] H. Sinaceur. Address at the Princeton University Bicentennial Conference on Problems of Mathematics (December 17-19, 1946), by Alfred Tarski. Bulletin of Symbolic Logic, 6(1): 1-44, 2000. [Skolern, 1923] T. Skolem. Begriindung der elementaren Arithmetik durch die rekurrierende Denkweise ohne Anwendung scheinbarer Vernderlichen mit unendlichem Ausdehnungsbereich; Skrifter utgit av Videnskapsselskapet i Kristiana, 1. Matematisk-naturvidenskabelig klasse, no. 6, 1-38. (Translation in [van Heijenoort, 1967].) [Skolem, 1923a] T. Skolem. Einige Bemerkungen zur axiomatischen Begriindung der Mengen- lehre. In Matematikerkongressen I Helsingfors den 4-7 Juli 1922. Akademiska Bokhandeln, Helsinki, 217-232, 1923. (Translation in [van Heijenoort, 1967].) [Spruit and G. Tamburrini, 1991] L. Spruit and G. Tamburrini. Reasoning and computation in Leibniz. History and Philosophy of Logic, 12: 1-14, 1991. [Smullyan, 1961] R. Smullyan. Theory of formal systems. Annals of Mathematics Studies 47, Princeton University Press, 1961. (A revised edition was published in 1968.) [Smullyan, 1993] R. Smullyan. Recursion theory for metamathematics. Oxford University Press, 1993. [Scare, 1996] R. Soare. Computability and recursion. Bulletin of Symbolic Logic, 2(3): 284-321, 1996. [Soare, 1999] R. Soare. The history and concept of computability. In [Griffor, 1999, 3-36]. [Stillwell, 2004] J. Stillwell. Emil Post and his anticipation of G6del and Turing. Mathematics Magazine, 77(1): 3-14, 2004. W• Bulletin mathematique de la Societe [Sudan, 1927] G. Sudan. Sur Ie nombre transfini W roumaine des sciences, 30: 1l~30, 1927. [Tait, 1981] W. W. Tait. Finitism. Journal of Philosophy, 78: 524-546, 1981. [Tait, 2002] W. W. Tait. Remarks on finitism. In [Sieg, Sommer, and Talcott, 2002, 410-419]. [Tamburrini, 1987] G. Tamburrini. Reflections on Mechanism. Ph.D. Thesis, Department of Philosophy, Columbia University, New York, 1987. [Tamburrini, 1997] G. Tamburrini. Mechanistic theories in cognitive science: The import of Turing's Thesis. In M. L. Dalla Chiara, K. Doets, D. Mundici, and J. van Benthem (eds.), Logic and Scientific Methods. Synthese Library 259, Kluwer, 239-57, 1997. [Turing, 1936] A. Turing. On computable numbers, with an application to the Entschei- dungsproblem. Proceedings of the London Mathematical Society, series 2, 42: 230-265, 1936. (Reprinted in [Davis, 1965].) [Turing, 1939] A. Turing. Systems of logic based on ordinals. Proceedings of the London Math- ematical Society, series 2, 45: 161-228, 1939. (Reprinted in [Davis, 1965].)
630 Wilfried Sieg [Turing, 1947] A. Turing. Lecture to the London Mathematical Society on 20 February 1947. In D. C. Ince (ed.), Collected Works oj A. M. Turing - Mechanical Intelligence. North Holland, 87-105, 1992. [Turing, 1948] A. Turing. Intelligent Machinery. 1948. In D. C. Ince (ed.), Collected Works oj A. M. Turing - Mechanical Intelligence. North Holland, 107-127, 1992. [Turing, 1950] A. Turing. Computing machinery and intelligence. Mind, 59: 433-460, 1950. [Turing, 1950a] A. Turing. The word problem in semi-groups with cancellation. Annals oj Math- ematics, 52: 491-505, 1950. [Turing, 1954] A. Turing. Solvable and unsolvable problems. Science News, 31: 7-23, 1954. [Uspensky, 1992] V. A. Uspensky. Kolmogorov and mathematical logic. Journal oj Symbolic Logic, 57: 385-412, 1992. [Uspensky and Semenov, 1981] V. A. Uspensky and A. L. Semenov. What are the gains of the theory of algorithms: Basic developments connected with the concept of algorithm and with its application in mathematics. In A. P. Ershov and D. E. Knuth (eds.), Algorithms in Modern Mathematics and Computer Science. Lecture Notes in Computer Science, 122: 100-235, 1981. [van Heijenoort, 1967J J. van Heijenoort (ed.). From Frege to Godel - A Source Book in Math- ematical Logic, 1879-1931. Harvard University Press, 1967. [van Heijenoort, 1985] J. van Heijenoort. Selected Essays. Bibliopolis, Naples, 1985. [van Heijenoort, 1985a] J. van Heijenoort. Jacques Herbrand's work in logic and its historical context. In [van Heijenoort, 1985, 99-122]. [von Neumann, 1927] J. von Neumann. Zur Hilbertschen Beweistheorie. Mathematische Zeitschrift, 26: 1-46, 1927. [von Neumann, 1931] J. von Neumann. Die formalistische Crundlegung der Mathematik. Erkenntnis,2: 116-121, 1931. (Translation in [Benacerraf and Putnam, 1983].) [Wang, 1974] H. Wang. From Mathematics to Philosophy. Routledge & Kegan Paul, London, 1974. [Wang, 1981] H. Wang. Some facts about Kurt Code!' Journal oj Symbolic Logic, 46: 653-659, 1981. [Whitehead and Russell, 1910] A. N. Whitehead and B. Russell. Principia Mathematica, vol. 1. Cambridge University Press, 1910. [Whitehead and Russell, 1912] A. N. Whitehead and B. Russell. Principia Mathematica, vol. 2. Cambridge University Press, 1912. [Whitehead and Russell, 1913] A. N. Whitehead and B. Russell. Principia Mathematica, vol. 3. Cambridge University Press, 1913. [Wittgenstein, 1980] L. Wittgenstein. Remarks on the philosophy oj psychology, vol. 1. C. E. M. Anscombe and C. H. van Wright (eds.). Blackwell, Oxford, 1980. [Wolfram, 2002] S. Wolfram. A New Kind oj Science. Wolfram Media, Inc., Champaign, 2002. [Zach, 1999] R. Zach. Completeness before Post: Bernays, Hilbert, and the development of propositional logic. Bulletin oj Symbolic Logic, 5: 331-366, 1999. [Zach, 2003] R. Zach. The practice of finitism: Epsilon calculus and consistency proofs in Hilbert's program. Synthese, 137: 211-259, 2003.
INCONSISTENT MATHEMATICS: SOME PHILOSOPHICAL IMPLICATIONS Chris Mortensen 1 INTRODUCTION: THE PARADOXES We begin with the paradoxes. Many puzzles that have been called paradoxes have been discovered. Some of these are trivial, such as the paradox of the Barber. Others are tricky but it is possible to discern a way through them, such as the Unexpected Examination. Others are genuinely profound in their implications. Among these, two groups were distinguished: semantic paradoxes such as the Liar and Grelling's; and set-theoretic paradoxes such as Russell's and Curry's. In the last quarter of the twentieth century, the semantic paradoxes led Routley and Priest to conclude that some contradictions are true [Priest, 1979; 1987; Priest, Routley and Norman, 1989]. This view, known as dialetheism, was at once highly radical and yet disarmingly simple. To describe it as radical is to allude to its reception among the body of contemporary philosophers, the large majority of whom still regard it as extreme. To describe it as simple is to allude to the appeal to simplicity in support: alternative solutions to the Liar, such as Tarski's hierarchy of languages, look unsimple by comparison. A similar observation can be made about the set-theoretic paradoxes: naive set theory with unrestricted comprehension is simple and natural in comparison with contrived patch-ups such as Zermelo-Frankel set theory or Russell's theory of types. The present essay is not about the semantic paradoxes, and not so much about the set-theoretic paradoxes either. Nonetheless, the example of the paradoxes hopefully softens the reader up for two points. The first point is that the idea that some contradictions might be true has considerable antiquity. Routley and Priest were in a long tradition. Some of the Ancient Greeks, notably Herakleitos and the author of the Dissoi Logoi, seem to have taken dialetheism seriously; and this generated a Western tradition which extends to Hegel, Marx and Engels. In the Eastern tradition there have been the Tao-te-Ching, Chan Buddhism in China, and Zen in Japan. The second point is that if dialetheism is true then any logic which validates the classical law Ex Contradictione Quodlibet (ECQ), from a contradiction any conclusion may be validly deduced, cannot be entirely correct as a description of universal principles of reasoning. This conclusion is Handbook of the Philosophy of Science. Philosophy of Mathematics Volume editor: Andrew D. Irvine. General editors: Dov M. Gabbay, Paul Thagard and John Woods. © 2009 Elsevier B.V. All rights reserved.
632 Chris Mortensen supported by the evident artificiality of ECQ. A logic in which ECQ fails is known as pamconsistent, or inconsistency-tolerant. The effect of the set-theoretic paradoxes on the nature of mathematics is condi- tioned by the question of foundationalism. If mathematics has a foundation, then set theory is a good candidate. Frege and Russell's logicist program had two pil- lars: that mathematics has a foundation, which is set theory, and that set theory in turn reduces to logic. If natural set theory is inconsistent then this seems to weaken the first pillar. It also seems to weaken foundationalism generally, if no better foundation can be found. In passing, it cannot be ruled out a priori that some other field of mathematics, such as category theory, might serve as a better foundation for mathematics than set theory. However, it seems clear that category theory employs similar strong comprehension-like principles to those of set theory, and so has similar problems with consistency (see [Hatcher, 1982]). If consistent set theory is bought only at the cost of unsimple and artificial principles which do not look much like principles of logic or definition, then, as Russell realised, the second pillar of logicism falls too. However, what Frege and Russell did not envisage is the possibility of accepting the contradictions outright. Set-theoretic foundationalism might survive, and both pillars of logicism with it, if the alleged contradictions caused by an unrestricted comprehension principle were restricted to regions where little or no damage to mathematics ensues. The barrier is, of course, ECQ, but we have just been seeing independent reasons for rejecting that. Hence we can register a preliminary conclusion: foundationalism and logicism might be salvageable if contradictions which are true-in-mathematics are tolerated, and ECQ abandoned. Nonetheless, we will later see different reasons for rejecting both foundationalism and logicism. The barrier that ECQ erects against liberated thinking can be described in another way. It is the idea that once a contradiction presents itself as proved in a theory, then reasoning with that theory must cease. Distinctions between different inconsistencies are impossible because any attempt to describe their structure dissolves into any other attempt. It is the doctrine that the inconsistent has no structure. Such a view, if true, would immediately ruin any attempt to develop a Theory of Inconsistency. This essay aims to refute that view. 2 THE ROLE OF LOGIC It might help the reader to begin by setting aside the Platonist question of what kind of an object, mathematical or otherwise, could possibly have inconsistent properties. In its place, it is recommended to put the primacy of the proposition and the theory in which it occurs. Mathematical texts and lectures do not present abstract objects for transcendental scrutiny. They begin with assertions. Cer- tainly, mathematical texts employ also diagrams. But mathematical texts, where they use diagrams, make assertions about them from the start. The intuitively natural epistemic method for mathematical propositions and theories is of course proof Mathematical truth is, at first pass, mathematical provability. This does
Inconsistent Mathematics 633 not restrict us to a narrow conception of provability as constructability, as the intuitionists have done: a generous inclusive methodology of proof, which can in- clude model theory, should be our starting point. It does mean, however, that we should be open both to the possibility that the intuitionists allowed, that neither A nor not-A be provable for some A, and the possibility that both A and not-A be provable, for some A. It also means that we should be less inclined to ask how could an inconsistent proposition be true in mathematics. Rather we should be more inclined to wonder where that might lead. Perhaps later might come an appreciation of mathematical objects with inconsistent properties, as the truth- makers for preferred mathematical propositions, and a basis for model theory. But this metaphysical extra is certainly not necessary to make a beginning with. Hence, our starting point is collections of propositions. More precisely, if we are to study structure, we must deal with mathematical theories, that is, sets of propositions closed under a deducibility relation. Deducibility relations are characteristic of logics; and it is well-known that there are many deducibility relations, since there are many logics. Hence the discussion has to be generalised to L-theories, that is, theories of a logic (or deducibility relation) L. An L-theory Th is inconsistent iff for some proposition A both A E Th and\", A E Th, where rv represents the symbol for negation (there are other symbols for special kinds of negations). Th is incomplete iff for some A neither A E Th nor r- A E Th. Th is trivial iff Th is the whole language, i.e. Th contains every proposition; otherwise Th is nontrivial. The members of any L-theory are also called its theorems, and are said to hold in the theory. In the end it will be desirable to suppress the logical apparatus provided by L as much as possible. However, for the present, consideration oflogic is forced upon us by the logical principle ECQ itself, which, if correct, would ensure that there is just one inconsistent theory, the trivial theory. This, in turn, would prevent any distinctions between kinds of inconsistency, between inconsistent mathematical structures. But at this point we are able to exercise some free choice: we can decide to countenance mathematical theories of logics for which ECQ fails. If there are none, then invent them. There are plenty of paraconsistent logics around to supply adequate logical apparatus. Thus there is a sense in which classical logic, regarded as the logic of mathematics, is made false by the existence of inconsistent mathematical theories. To paraphrase Marx, philosophers have hitherto attempted to understand the nature of contradiction, the point however is to change it. Given a logic, there are two ways to construct theories of that logic: by axioms or by models. The first intentionally inconsistent arithmetical theory was Robert K. Meyer's RM3(mod 2), which was specified by a model. Its background logic was the paraconsistent 3-valued logic RM3. The theory RM3(mod 2) was inconsistent because both 0 = 2 and\", (0 = 2) were theorems. However, Meyer constructed this theory because he wanted to study the relevant arithmetic R#, which is axiomatically constructed. The logic for R# is Anderson and Belnap's quantified relevant logic R, axiomatically presented. R# is then given by taking the classical axioms for Peano Arithmetic, replacing their classical implication connectives :J by
634 Chris Mortensen the implication connective ~ of R, and closing under the deducibility relation for R. There is no suggestion that R# is inconsistent. However, by virtue of Meyer's result that R# <;:;; RM3(mod 2), it follows that R# can have 0 = 2 added as an axiom, the result being an inconsistent axiomatically-presented arithmetic which is nontrivial. Indeed, RM3(mod 2) itself has an axiomatic presentation: to R# add 0=2 together with all instances of the propositional axiom Mingle, A ~ (A ~ A). See [Meyer 1976; Meyer and Mortensen, 1984; Mortensen, 1995]. The question can be asked: given that there are many paraconsistent logics, which is \"best\" for inconsistent mathematics? The answer that emerged was that it doesn't much matter which: the properties of inconsistent theories tend to be invariant over a large class of background logics. To be more exact, when theories are specified by means of models, their logical properties tend to take second place behind mathematical calculations which are performed at the sub-atomic level (sub- atomic relative to the atoms of logic, that is). This suggests an important idea: that mathematics is after all different from logic since logic deals with the general properties of propositions, predicates and identity, while mathematics deals with calculations in particular kinds of structures. We will be developing this theme as we proceed. Even so, there is one paraconsistent logic which is particularly natural: closed set logic. It is well known that intuitionist logic is the logic of open sets; closed set logic is its topological dual. For many familiar logics, such as tense and modal logics, we can think of propositions as indexed by sets of points in an appropriate space, such as a set of times, or a set of possible worlds, or a phase-space. This idea can then be extended by supposing that the index set has a topological structure. If we make the stipulation that propositions only ever hold on open sets of points, we obtain open set logic. It is not difficult to then think of the disjunction of two propositions as holding on the union of the sets on which they hold, and conjunction as holding on the intersection. Considering negation however, it is apparent that the negation of a proposition A cannot hold on the set-theoretic complement of set of points on which A holds, since the set-theoretic complement of an open set is not in general open. It is thus customary to take for negation the largest open set contained in the set-theoretic complement. We can then see the familiar intuitionist property of negation emerging: at the boundary neither A nor not-A holds. Theories of open set logic may thus be incomplete. It is widely acknowledged that this is a natural-sounding semantics. Applying the topological open-closed duality, we must have closed set logic. Closed set logic is the stipulation that whatever holds, holds on closed sets of points. The interesting case is negation. It is thus customary to take the smallest closed set containing the set-theoretic complement. We then have the familiar paraconsistent property of negation emerging: at the boundary both A and not-A holds. It is apparent that this is an equally natural semantics to that of open set logic. It is one in which ECQ fails and which supports inconsistent theories. This is as natural as the natural transformation: open ~ closed.
Inconsistent Mathematics 635 Unfortunately, it was soon found that inconsistency can spread for reasons other than ECQ. Curry's paradox generates triviality for naive set theory even in the absence of negation, even in the absence of ECQ (see e.g., [Meyer, Rout- ley and Dunn, 1979]). All that is necessary is the logical law of Contraction (A -+ (A -+ B)) -+ (A -+ B) as well as Modus Ponens, Simplification and Univer- sal Instantiation. Indeed, even weaker principles suffice, as shown by Slaney [1989] and Rogerson [2000]. Thus we must not live in a fool's paradise when constructing inconsistent theories axiomatically. Maybe some variant of Curry's paradox can jump up and bite us as a consequence of our axioms, even if we are sure that ECQ cannot hurt our theories. Nevertheless, we have a guarantee from model theory that the spread of con- tradictions can be stopped short of triviality, at least for naive set theory. This was essentially shown by Brady very early on [1971], using a model-theoretic fixed- point method derived from Gilmore [1967]. (It should be noted that Brady's result was not explicitly inconsistent, but the latter follows by a trivial manouvre, as he later realised [1989].) Similar work was done independently by Da Costa ( see e.g. [1974)]. The importance of Brady's and Da Costa's result cannot be stressed enough. Brady demonstrated nontriviality in the presence of the Russell Set and the Curry set; so by brute force, whatever logical principles have to fail for these sets not to lead to explosion, must fail in Brady's construction. In a further paral- lel to Meyer, Brady developed the method in later papers to show that classically false ordinal equations are not provable in naive set theory either (see [1989]). Thus, just as in arithmetic, the contradictions in naive set theory are far away and contained, and do not interfere with serious mathematical calculations. Hence, problems for inconsistency arising from logic are not insurmountable. But this is far from being an end to it. Dunn pointed out that if any classically false equation was added to real number theory, then every equation became provable. The proof of this is elementary algebra: from a = b, where a and b are distinct real numbers, we can subtract a from both sides to get 0 = (b-a). Each side may then be multiplied by any number we please to get 0 = r for any real number r. Hence by the principle of the substitutivity of identicals, every real number equals every other. We can coin the term mathematically trivial for any (mathematical) theory all of whose (logically) atomic propositions are theorems. Now mathematical triviality implies full triviality in the presence of the rule ECQ. But in general it does not do so. Yet, it is mathematical triviality that is catastrophic for mathematics: no calculation would mean anything. And in Dunn's argument we have an example where mathematical triviality is spread by principles other than ECQ or anything else from pure logic. Conversely, if calculations are possible at all, then it is nothing short of crude classical hegemony to insist that a detour through mere logical principles such as ECQ ought to render the theory useless for this purpose or any other. Correspondingly, we can define a theory to be transparent if it permits full substitutivity of identicals; that is, if h = t2 holds then Fi ; holds iff Ft2 holds,
636 Chris Mortensen where F is any context. A theory is functional if substitutivity of identicals is restricted to logically atomic contexts; that is, F is any atomic context. In theories of classical logic, functionality implies transparency, but this is not so in the general case. Furthermore, Dunn's argument requires no more than functionality to work. But now we can see that it is functionality that matters more for mathematics than transparency, since functionality is what ensures that calculations can proceed. Failure of substitutivity because of logic is not such a weighty matter, while both functionality and its failure are of greater moment for mathematics. 3 PURE MATHEMATICS It is impossible in this brief account to survey all the results of inconsistent math- ematics. However, some broad outlines can be touched on. The study has tended to concentrate on techniques from model theory rather than axiomatics, and we will take that approach here. Thus we begin with a first-order language containing (i) names for mathematical objects, such as the natural numbers, integers, real numbers, sets, topological spaces; (ii) term-forming operations on these objects, such as +,x, -,7, / (successor) ; (iii) atomic predicates and relations, such as =,~, E; (iv) logical operations such as &, V, \"', :J, ---., +-*, \/,3. Well-formed formulae are defined in the usual way. A model is a triple (D, L, 1), where D is a domain of mathematical objects, L is a many-valued logic, some of whose values are designated and the others undesignated, and I is an interpretation which maps names to elements of the domain, term-forming operators to (partial) operators on the domain, predicates to subsets of the domain, n-ary relations to subsets of D\"; and wffs to the values of L in accordance with the interpretations of parts of the wff to the domain or other values respectively. The theory associated with the model is then formed by taking the all those wffs of the model which take a designated value in the interpretation. One device worth mentioning is the use of extensions and anti-extensions for each predicate and n-ary relation. The idea, due to Dunn and used by Priest, is that the extension and anti-extension of a predicate can overlap and in that case the predicate is counted as both true and false ofthose objects. However, it is not necessary to use this device, and it is less than fully general when a logic having numerous values is being used. The reader is cautioned at this stage from taking models with too much ontological seriousness. Models are to be regarded in the first instance as devices for controlling the membership of theories. Notice also in passing the implied distinction between mathematics and logic in that, with the exception of = and perhaps E, logic proper only enters under (iv).
Inconsistent Mathematics 637 To take an example, consider the language to contain names for all natural numbers (perhaps constructed in the usual way from 0 and the successor oper- ation), arithmetical operations +, x, I, and a single binary relation =. Let the domain D be the natural numbers modulo 2, and the logic L be the 3-valued paraconsistent logic RM3, with values {T, B, F} where T and B are designated values (B is understood as \"both\"). Interpret names for the natural numbers as their counterparts mod 2 and term-forming operators as their corresponding op- erators mod 2. Atomic sentences tl = tz are interpreted as taking the value B if tlmod 2 = t2mod 2, otherwise tl = t2 is interpreted as taking the value F. The set of sentences taking either of the designated values {T, B} is Meyer's theory RM3(mod 2). The theory is inconsistent since the equation 0 = 2 takes the value B while r-- (0 = 2) takes T. Meyer then proved that relevant arithmetic R# s:;; RM3(mod 2), which was the basis for his finitary nontriviality proof for R# (see [Meyer, 1976]). It is obvious that Meyer's construction can be modified to produce RM3(mod n) for any number n. Since R# is contained in any of these, we can also see that no classically false equation t l = t2 can be proved in R#. (See [Meyer and Mortensen, 1984].) Meyer's proof that R# s:;; RM3(mod 2) was finitary in Hilbert's sense, in that it relied solely on ordinary mathematical induction over the length of formulae. Since by inspection RM3(mod 2) is nontrivial, it follows that R# can be shown to be non-trivial by finitary means. By contrast, it follows from Codel's incomplete- ness theorems that there is no finitary proof of the non-triviality (equivalently, consistency) of classical Peano arithmetic. This was viewed with great pessimism by Hilbert, who felt that it spelt the end of his program to demonstrate the consis- tency of mathematics by finitary means. However, Meyer concluded that Hilbert's pessimism is unfounded, as long as we cast aside the shackles of classical logic and ECQ. A further corollary of Meyer's result was not merely that the explosive spread of contradiction in relevant arithmetic is prevented, but that no false atomic propositions (equations) can be proved in R#. Thus calculation is untouched by contradiction in relevant arithmetic. This is then a further important consequence for the philosophy of mathematics. We saw earlier that logicism might be re- habilitated from Russell's paradox by retaining naive comprehension, as long as ECQ fails. Now we see that the Hilbert program similarly has excellent prospects for rehabilitation in logics in which ECQ fails. These include logics only slightly weaker than classical logic. It is fairly easy to show that extensional part of R# (with logical operators &, v, \"\",:J, =:0, 3, \/, =, but lacking intensional operators --->, f--t) is a subset of clas- sical Peano arithmetic PA.There was for a time the hope that they coincided exactly. This would of course imply the non-triviality of PA, and hence its consis- tency. That would not of course violate Godel's second incompleteness theorem, since there is no suggestion that the proof method itself be representable in clas- sical arithmetic. But it would be a new proof all the same, perhaps using quite different techniques from the usual. It was eventually discovered by Meyer, adapt- ing Friedman, that R# is strictly weaker than PA, [Meyer-Friedman, 1992]. This
638 Chris Mortensen dashed the hopes of a consistency proof for PA. Meyer himself expressed pes- simism that R# was thereby shown to be less than adequate for arithmetic, since there are true extensional propositions unprovable in R#. But it seems that this makes R# all the more interesting: a genuine rival to PA in which all calculations can be performed; and in which, moreover, all primitive recursive functions are representable so that the incompleteness theorems apply. Moreover, it is hardly something that adherents to classical PA can rejoice in, since they, too, have had to live with the incompleteness theorems ever since they were proved: what is the G6del sentence if not a true-but-unprovable statement? The class of all mod models, for varying modulus n, has various interesting properties. Its intersection RMw has the property that its counter-theorems are recursively enumerable, but it is not known whether it is recursive or not. There are also non-standard mod models (see [Mortensen, 1987; 1995]). Recently, Priest [1997; 2000J has completely characterised the class of mod models, that is, he showed that all mod models take a certain form. Of interest is the case of RM3(mod p) where p is prime, since it is known that the natural numbers mod p form a jield; that is, division is well-defined. This raises the question of where Dunn's proof of triviality for the inconsistent real number field breaks down in mod p. The answer is that in an inconsistent mod arithmetic the equation a = b holds only if the classical difference between a and b differ by an integral multiple of the modulus. Multiplying or dividing both sides by the same integral number does not disturb that, so the inconsistency does not spread everywhere. It is well known that in the history of the calculus debate raged about whether one should take seriously the use of \"very small\" real numbers. By the early nineteenth century it seemed that disputes over the status of infinitesimals were resolved in favour of real numbers alone by means of the Cauchy-Weierstrass (e, is) technique, which quickly became the orthodoxy in mathematics departments. By 1960, however, Robinson revived infinitesimals by showing rigorously that one could develop calculus just as well with them, and that calculus based on in- finitesimals is in various ways simpler to manipulate, (see [Robinson, 1966]). Now it is notorious that in working out derivatives Newton opportunistically divided by very small numbers, yet set them to zero when it was convenient to ignore them. Perhaps then one might be able to make them inconsistently both equal to zero and not equal to zero? However, the prospect that inconsistency in the real numbers spreads uncontrollably into triviality poses an obvious problem for devel- oping inconsistent differential and integral calculus, and resorting to infinitesimals does not offer an obvious relief since the mathematical triviality proof goes over immediately to a mathematical triviality proof in the hyperreal field. One way to avoid this is to take as one's domain something with a little less than the full structure of fields. This is accomplished by beginning with the noninjinite hyperreal numbers, that is, the finite real numbers together with the infinitesimals. Selecting an infinitesimal number TI, define a ~ b to mean that (a - b)/TI is infinitesimal or zero. One may then prove that the equivalence classes
Inconsistent Mathematics 639 so generated form a ring under the induced operations. This ring serves as the domain for an inconsistent model. Taking RM3 as background logic as before, set J(tl = t2) to be T if h = t-z as real numbers, set J(h = t2) to be B if tl and t2 are distinct real numbers but [tIl = [t2], and set J(tl = t2) to be F otherwise. Then it is easy to see that both TJ2 = 0 and >- (TJ2 = 0) hold, whereas TJ itself is consistently non-zero. The prospect that infinitesimals smaller that a certain level in size (Le. infinitesimals which are even infinitesimal w.r.t. TJ) can be equated with zero, allows calculations in which they can be ignored, even though their \"effects\" remain in that division by them is retained in various contexts. Differentiation and integration can be developed, and Taylor's theorem and the fundamental theorem of the calculus can all be proved. There is more to be said about results from pure mathematics than this. Anal- ysis, topology and category theory have all been studied. For an extended dis- cussion, see [Mortensen, 1995; 2000; 2002a]. However, we now proceed with our survey by turning to make some brief remarks on geometry. 4 GEOMETRY Consider the picture below. There are many others. It is notable that the beginnings of inconsistent math- ematics avoided dealing with such pictorial puzzles, though now the situation is slowly being remedied. Interestingly, classical mathematics has also largely avoided dealing with them. In the classical mathematical literature there were to be found three approaches. The first, due to Thaddeus Cowan [1974], studied n-sided fig- ures in terms of the properties of their corners, employing the theory of braids. Second, George Francis [1987] asked what sort of consistent non-Euclidean space 2 could be inhabited by such objects. The answer, for the above figure, is R x 51. Third, Roger Penrose [1991] used the theory of cohomology groups to obtain nec- essary and sufficient conditions for a picture to be of a consistent object; a fortiori the failure of those conditions would mean that the picture was of an inconsistent object, (see also [Penrose and Penrose, 1958]).
640 Chris Mortensen These were unquestionably all very perceptive approaches. However, as argued by the present writer in [1997b; 2002b; 2002c], they all shared a common deficit: they did not explain the sense we have that we are perceiving an object with im- possible properties. This suggests a different conception of the problem, namely, to think of the brain as encoding an inconsistent geometrical theory. The problem would then become to write out such a theory (or rather theories, for there are many different impossible pictures with different properties). The theory in ques- tion would stand to the pictures in somewhat the way that projective geometry stands to the experience of perspective; and with somewhat the same justification, namely, that projective geometry is important to us because of the experience of having an eye. This kind of justification of the study of inconsistency has been described as the epistemic or cognitive justification. Such justifications appeal to a human capacity, typically the capacity to reason in a logically-anomalous environment, without in- tellectual collapse into triviality. There is of course no suggestion that inconsistent objects exist in the physical world. Rather, it is that our perceptions construct a geometrical theory while at the same time retaining geometrical principles which are incompatible with it. It seems that in inconsistent pictures we have a clear example of the mind's ability to make constructions which are inconsistent and yet persist even when the impossibility is manifest to us. The lack of cognitive penetrability of the experiences is characteristic of the modularity of perceptual capacities which has been noted by various authors, e.g. [Fodor, 1983]. The details of such mathematical theories are still in an early stage of develop- ment. The interested reader is invited to consult the above references for further elucidation. 5 APPLIED MATHEMATICS A good antidote to the error that mathematics develops in pristine logical order is to read the works ofImre Lakatos [1976]. It is particularly in applied mathematics, physics and engineering where mathematical opportunism is most apparent. Here the lack of classical rigor comes with applications built-in. Hence we can ask, as with the historical disputes over infinitesimals, whether the \"logically erroneous\" theory might be more accurately described as an inconsistent theory rich enough to permit useful calculations. A good example is Dirac's Delta \"function\", o(x). This had the twin properties: (i) o(x) = 0 for all x f. 0, and (ii) Jo(x)dx = 1, where the integration was over the whole real line. It is apparent that there is no such function on the real numbers. Yet Dirac perceived a use for it in his version of Quantum Mechanics. In this he was followed by many of the physics community. Quantum theory developed rapidly and decisively. It was not for some forty years that Laurent Schwartz managed to put things on a consistent footing by using functionals rather than functions. There was a significant cost, however, in that the new theory was considerably more complicated. There is a fairly obvious construction for the Delta function
Inconsistent Mathematics 641 which uses infinitesimals: draw a triangle of infinitesimal base (3 and infinite height 2/(3. This satisfies something close to the condition (i), namely J(x) = 0 for all real x i- 0; and clearly the second condition is satisfied since the area of the triangle is 1. This was not Robinson's construction, however, since it requires second-order principles; whereas Robinson restricted himself to first-order conditions, so that his theory amounted pretty much to a copy of Schwartz'. It turns out, however, that there is an inconsistent theory which adapts the construction above of inconsistent infinitesimals, and which has the property that J(x) = 0 for all x for which x = 0 fails to hold. Since it is the propositions that hold that are relevant to property of functionality, we can say that the construction recovers the concept of a function, albeit an inconsistent function. It is hardly surprising that Quantum Mechanics lends itself to inconsistent ap- plications, since QM has long been regarded as a source of anomaly and paradox. One more application in this area is quantum measurement. In cases where an operator has a discrete spectrum, such as the energy levels of the hydrogen atom, elementary QM postulates discontinuous changes in the wave function when a measurement is made. Now discontinuity is an enemy of causality: it would be desirable to have a theory in which quantum measurement was reducible to the other familiar quantum process of unitary evolution. This is the measurement problem, and it is fair to say that the measurement problem remains unsolved, and is even intensified given the problem of nonlocality, Bell's theorem and As- pect's experiments. An approach using inconsistent continuous functions seems to allow both for continuity/causality and at the same time discrete spectra. For more details, see [Mortensen, 1997a]. The cognitive justification of paraconsistency, discussed before, is apparent in the application to information systems. Nuel Belnap [1977] famously pointed out that any control system with more than one stream of informational inputs, must allow for the possibility that its inputs may be in conflict. Furthermore, it may be impossible to shut the system down until the problem is resolved, as with an aircraft aloft. Thus there has to be a way of operating in an anomalous informational environment, which is after all what we humans manage to do. One theory taking this approach considers the problem of solving inconsistent systems of linear equations. Inconsistent systems of linear equations have been known about for centuries, and the standard mathematical reaction has been to throw up the hands in despair. However, it proves possible to solve some such systems of equations in an inconsistent space. Now the classical theory of control systems makes heavy use of systems of linear equations. This in turn suggests that if one were able to model a malfunctioning control system in terms of an inconsistent system of linear equations, there might be a way of continuing to exercise some limited control. The modelling proved not to be so difficult. According to classical control theory, when a system is functioning correctly, its internal organisation is modelled by a transfer matrix, which transforms a (column) vector of inputs into a vector of outputs. When the system is malfunctioning, there is a difference between the expected outputs and the observed outputs. By superimposing the
642 Chris Mortensen observed outputs onto the expected transfer matrix, one obtains an inconsistent system of equations which can then be solved. In software modellings this has met with some limited success. A related approach has been taken by the Brazilian group around Abe [2000], who have demonstrated a paraconsistent robot, Emmy. It should be noted that it is not being claimed here that the control system is behaving inconsistently in the real world. It is rather that the discrepancy between expected and observed creates an epistemological gap that has to be resolved. Calculations take place in a virtual space in which all the information available is used to form a composite picture with the aim of continuing to function until proper knowledge and control can be fully restored. A final point to be noted is the shift in ontology that takes place between pure mathematics and applied mathematics. In rejecting Platonism, we were rejecting abstract truthmakers for pure mathematics. The truthmakers for applied mathe- matics, one would imagine, are its applications. These involve systems of physical objects and their physical quantities, the kinds of things which are causally active, changing and producing change. Physical quantities, such as 5 gram, 2 em, 3 sec, come as a package of a number (\"5\") and a quantity kind or dimension (\"gram\"). In the present writer's view, the best account of quantities treats them as causally relevant universals. Laws of nature come out as relations between universals (see [Armstrong, 1978]). Real numbers then emerge fairly unproblematically as ra- tios (i.e. relations of comparison) between dimensioned quantities having the same dimension (see [Forrest and Armstrong, 1987; Bigelow, 1988; Mortensen, 1998]). It is not proposed to develop this account here, the reader is directed to these references. The point being made is that there is not necessarily an equivalence between the problem of the truthmakers for pure mathematics, and truthmakers for applied mathematics. The harder problem seems to be for pure mathematics, while applied mathematics looks rather more tractable. 6 LOGICISM AND FOUNDATIONALISM REVISITED With this all-too-sketchy survey of what is known to date, we return to our flirtatious quarrel with logicism. The foregoing suggests that we can draw a (rough) line between logics and mathematics in the kinds of reasonings they em- ploy. Logics deal with universally applicable principles of reasoning, centrally (f-,1=, &, V, \"', ----+, f--7, 3, \/, =), and other constructions arising in natural language (e.g. tense, modality, adverbs). Logic applies to mathematical reasoning, certainly, but it applies to that aspect of mathematical reasoning that applies to other sub- ject matter as well. In contrast, mathematics distinctively deals with concepts like those of algebra, calculus, differential equations, analysis and geometry. Some- where in the middle between logic and mathematics lie set theory, number theory, recursion theory and parts of algebra. In the case of algebra, logicians' interests have tended to be confined to structures which can supply a plausible semantics for various sets of logical axioms, such as lattices. With only a few exceptions, logicians have not been much interested in groups, for example. This leads to
Inconsistent Mathematics 643 the challenge to logicism: in what sense is mathematics no more than logic with definitions? It all depends on which definitions. Mathematicians tend to be anti-foundationalist. The previous challenge can also be directed against foundationalism, and it explains why mathematicians have not taken logic's attempts at hegemony too seriously. Claims like \"set theory is a foundation for mathematics\" or \"mathematics reduces to logic\" look like they are saying that all there is to mathematics is set theory or logic. But this is precisely to suppress what is distinctive about mathematics. They give a false sense of what is the nature of mathematics. The point can be further illustrated by considering the \"reduction\" of geometry to algebra. It is uncontestable that Descartes' discovery of the coordinatisation of the plane enabled an immense step forward in geometry. The methods of algebra could then be applied to the study of the plane. Space could be studied by solving equations involving real numbers and their functions. Nonetheless, it is a mistake to take this as implying that geometry is nothing but real number theory, as Russell seems to have thought (see e.g. [Ayer, 1972, 43]). The two-dimensional plane is 2 not R ; space is not a collection of numbers. Its parts are points, lines, curves, and planes, not sets or real numbers. We need only pay attention to our own perceptions of space to see this: we perceive areas, lines etc., we do not perceive numbers. In short, there is no conceptual equivalence possible between geometry and set theory. This is why a mathematician can pursue the study of space paying little or no attention to foundations: mathematics has a conceptual autonomy that foundations cannot supply. From this point of view, the gap between mathematics and logic is even wider than that between mathematics and real numbers and set theory. Logicians study \"and\", \"or\", \"not\", \"implies\" and the like. Their discipline begins where mathe- matics leaves off in studying the behaviour of geometry, groups and the like. This makes logic look more like a small area in the corpus of mathematics, rather than a foundation for it. Furthermore, it exposes ECQ for what it is: a tool in a takeover bid to establish the hegemony of logic over mathematics. As a piece of personal reportage I recall years ago explaining to a visiting emi- nent mathematician why I was inclined to reject ECQ. After listening politely, he asked: \"Excuse me, but are you not denying that the null set is a subset of every set?\" This confusion embodies a subtle reversal, but it is no better motivated. We may be inclined to make a limited \"reduction\" of set theory to logic by adopting naive set theory and claiming that there is nothing to set theory but logic. Naive comprehension would then be an expression of the reduction. In favour it can be said that it is certainly less ad hoc than rival comprehension principles. However, our eminent mathematician was reversing the order of explanation: he felt that the principles of set theory were sui generis and that the legitimacy of ECQ was ensured by that!
644 Chris Mortensen 7 REVISIONISM AND DUALITY Earlier, we referred to the topological duality between incomplete theories of open set logic, and inconsistent theories of closed set logic. There is another kind of duality, Routley-* duality. This applies between theories of logics in which the laws of Double Negation A <--> rvrv A and De Morgan rv (A V B) <--> (rv A & rv B) and rv (A & B) <--> (rv A V rv B) hold. Neither open set logic nor closed set logic has these laws unrestrictedly, however many of the logics in the Anderson-Belnap class of relevant logics have them. For any set of sentences S, define S* to be {A: rv A 1- S}. Then a simple argument shows that if Th is any theory of a logic containing Double Negation and De Morgan, then Th is inconsistent iff Th* is incomplete. Since DN ensures that Th** = Th, we also have that Th is incomplete iff Th* is inconsistent. That is, incompleteness and inconsistency as properties of theories are duals of one another in two senses: they are topological duals of one another, and they are Routley-* duals of one another. Duality results are of course sources of \"theorems for free\". As a quick illustration of free theorems, we note a dualisation of Kripke's modelling of the truth predicate in an incomplete theory. Kripke [1975] showed, using a fixed point method deriving from Gilmore [1967] and Brady [1971], that the Liar proposition L and its negation are excluded from a theory satisfying the condition for a truth predicate: A <--> T(A) where A is any proposition and T(.) is the truth predicate for the name (Codel number) of A. Kripke interpreted this as showing that the Liar proposition L ought to be regarded as neither true nor false. However, applying the Routley-* to the truth theory, we can immediately conclude that there is a theory satisfying the conditions for a truth theory to which both Land rv L belong. We might also observe that the inconsistent dual theory has certain advantages over the incomplete theory. Any theory which, like Kripke's, declares that L lacks a value, suffers from a dilemma. Either we say that the instance of the T-scheme for the Liar sentence has a value (presumably True), or it does not. If it does, then we have the oddity that none of L, rv L, T(L) and T(rv L) receive a truth value even though L <--> T(L) and rv L <--> T't-- L) hold in the theory. If it does not, then it odd to say that the T-scheme holds even though some of its instances fail to hold. Note that while Kripke employed a third logical value in his construction, he was clear that this was a formal device for calculation only, and that he regarded the liar sentence as lacking a value. This is perfectly reasonable as a proof device, however it seems strange that a valueless proposition could yet contribute to making a compound hold. In contrast, in the inconsistent dual, all of L,>: L,T(L) and T(rv L) take contradictory values; which is at least some reason to hold that L <--> T (L) does too. Intuitionism and constructivism are examples of revisionist philosophies of math- ematics, in that they declare that certain principles accepted in classical mathe- matics are incorrect. They aim to revise mathematics by truncating it, based on a narrower conception of what is an acceptable proof. However, revisionism leaves unanswered an important question: why are the excluded areas yet mathe-
Inconsistent Mathematics 645 matics? In their haste to offer a theory of correct proof, revisionists neglect the central question of the philosophy of mathematics: what is mathematics? This is hardly to be answered adequately by declaring those parts of mathematics that the theorists don't like, not to be mathematics at all. The classical Hilbertian ideal of a mathematical theory is one which is com- plete and demonstrably consistent. Revisionist theories, by excluding aspects of classical theories, render themselves incomplete, a fact which has been long-noted in connection with intuitionism. By contrast, inconsistent mathematics is not revisionist at all. Taking a lead from the duality results, it aims to extend math- ematics, not weaken it. The duals of incomplete theories are inconsistent, and they include classical consistent complete theories as subtheories, and consistent incomplete theories as sub-sub-theories. Thus inconsistent mathematics supports a principle of tolerance about what counts as mathematics, an inclusive approach not an exclusive one. Both classical mathematics and revisionist mathematics emerge as special cases of a more generalised conception of mathematics, which includes inconsistent mathematics as well. 8 THE ROLE OF TEXT One further matter needs to be raised, though dealing with it fully would take much more space than we have here. If we ask what makes all of the above examples mathematics, it is apparent that the answer must have something central to do with the characteristic use of notation or symbols. That is to say, mathematics is text'Ually distinctive. Importantly, this is something it shares with symbolic logic. It is apparent that the rise of symbolic logic in the twentieth century is attributable to its use of mathematical text. The question is: just how is it that this has been so efficacious? This dovetails with the broader question of just why it is that the distinctive textual features of any mathematics do their jobs so well? We are all familiar with examples like the advantage of the change from Roman numerals to Arabic numerals: it is clear that this is a microcosm of the general question of the distinctive nature and efficacy of mathematical text. There is something important to be explained about how mathematical meaning is carried by text. There is another observation which is a kind of converse to this one. In his University of Adelaide PhD thesis TheRole of Notation in Mathematics [1988], Edwin Coleman pointed out the varieties of mathematical text. He drew attention the differences between a page from Euclid, a page from Principia Mathematica, a page from a text on business mathematics, a page from a standard calculus text, and a page from a mechanical engineering text. Consider for example the varying role of diagrams, and the presence or absence of natural language. The differences are richly textual, and yet the very stuff of mathematics. Thus, the question of the usefulness of distinctive texts in mathematics, is part of the question of how mathematical text generates meaning. It is the interplay of similarity and difference that needs to be understood.
646 Chris Mortensen Coleman argued that the right discipline to undertake such a study was the theory of signs, semiotics. Co-discovered by Peirce and Saussure, semiotics aims to study how text and other signs generate meaning. Saussure in particular had to rely somewhat more heavily on the internal differences within a code or system of signs, because, unlike Peirce, his account lacked a theory of extra-linguistic ref- erence. While this is an obvious drawback in any general account of language, it can be seized on by (we) anti-Platonists as just right for any account of mathe- matical meaning, where (according to us) there are no abstract objects to be the referents. This is nothing but an application of Saussure's concept of difference. Ockham's Razor does the rest against Platonism. A certain amount of literature which addresses these issues in the indicated ways has grown up, including Nelson Goodman [1981], Rene Thom [1980], Brian Rotman [1987; 1990], Coleman [1988; 1990; 1992], and Mortensen and Roberts [1997]. We saw earlier that Meyer's nontriviality result serves fit to re-habilitate Hilbert's program of demonstrating that mathematics does not have false consequences. But there are problems for Hilbert's program of a different sort here. Drawing on the above, Coleman attacked Hilbert's formalism. Like Brouwer, Hilbert gave way to the despair of revisionism. In order to demonstrate mathematics to be consistent and complete, or at least without error, mathematical theories must be displayed in canonical form, as formal systems, purely symbolic and devoid of all meaning (save that generated internally). But here, as with revisionisms anywhere, we can again ask why are the uncanonical parts yet mathematics? Don't get me wrong. I am certainly not against reconstruction of a theory as a first order formal the- ory, if only because then you could automate it! But notice that in producing an \"equivalent\" formal theory we are suppressing a difference that is part of what has to be explained: in what sense can notationally distinct codes be equivalent, and how can textual features contribute to distinctness of code, and thus to differences of meaning? This kind of study cuts across the inconsistency program to some extent. Nonethe- less, it serves to reinforce the point that an inclusive point of view about math- ematics is necessary if one is to understand what mathematics is. Revisionism inevitably reduces our view of what is possible for mathematics, and thus distorts our understanding of the phenomena. 9 CONCLUSIONS To summarise, the following propositions have been advanced. 1. Logicism and foundationalism may well be saved if we adopt a logic lacking ECQ. 2. Similarly, part of Hilbert's program, to prove that mathematics has no false consequences, may well be saved if such a logic is adopted. There are many suitable logics, some of them only slightly weaker than classical logic.
Inconsistent Mathematics 647 3. Nonetheless, logicism and foundationalism do not explain the conceptual autonomy of mathematics from logic. In particular, geometry is conceptually separate from logic and set theory, and does not reduce to them. 4. Revisionist philosophies of mathematics, whether they be revisionist about the truths of mathematics (intuitionism) or revisionist about notation (for- malism), are open to the objection that they do not account for the varieties of mathematics outside of approved canonical norms. 5. In contrast to revisionism, we must take an inclusive position, whereby incon- sistent mathematics is seen as extending our conception of what is possible for mathematics rather than rejecting the corpus of existing mathematics. 6. This is just as well, since inconsistent mathematics has numerous applica- tions beyond itself. 7. As part of comprehending the nature of mathematics, the distinctively tex- tual aspects of mathematics, both the similarities and the differences between textual styles, have to be understood; and semiotics seems to be the best theoretical framework for this project. Two related issues of traditional philosophy of mathematics have been placed on the backburner in this essay. One is the matter of truthmakers for pure mathemat- ics. The other is the distinctive epistemology of mathematics, and in particular the method of a priori proof. Neither can be neglected in a full account. However, we might make the very limited suggestion that if the primary phenomenon to be ex- plained for mathematics is textual, then it is not so speculative that the account ought to derive from the features of text, rather than abstract acausal objects. Certainly, the legitimacy of inconsistency ought to give pause to the Platonist. It poses the dilemma: either abandon Platonism, or admit inconsistent objects. One salient virtue in sheeting home the primary account to the theory of signs, is that it scores well on the second issue: we have a readily-understandable epistemology for signs. It can hardly be denied that getting in contact with signs, such as those on your keyboard, is a thoroughly natural activity. The same can't be said for Platonism. BIBLIOGRAPHY [Abe et al., 2000] Abe et al. Emmy, a Paraconsistent Robot, Second World Congress on Para- consistency, Juquehy Beach, 2000. [Armstrong, 1978] D. Armstrong. Universals and Scientific Realism, Cambridge, CambridgeUP, 1978 [Ayer, 1972] A. J. Ayer. Russell, Fontana Modern Masters, 1972. [Belnap, 1977J N. D. Belnap. How a Computer Should Think, in G.Ryle, ed. Contemporary Aspects of Philosophy, Stocksfield, Oriel Press, 30-55, 1977. [Bigelow, 1988J J. Bigelow. The Reality of Numbers, Oxford, The Clarendon Press, 1988. [Brady, 1971] R. Brady. The Consistency of the Axioms of Abstraction and Extensionality in a Three-Valued Logic, Notre Dame Journal of Formal Logic (NDJFL) 12,447-453,1971
648 Chris Mortensen [Brady, 1989J R Brady. The Non-triviality of Dialectical Set Theory. In [Priest et al, 1989, 437-471]. [Brady and Routley, 1989] R Brady and RRoutley. The Non-triviality of Extensional Dialec- tical Set Theory. In [Priest et al., 1989, 415-436J. [Coleman, 1988] E. Coleman. The Role of Notation in Mathematics, PhD thesis, U. of Adelaide, 1988 [Coleman, 1990] E. Coleman. Paragraphy, Information Design Journal, 6, 131-146 [Coleman, 1992] E. Coleman. Presenting Mathematical Information. In RPenman and D.Sless, eds, Designing Information for People, Canberra, ANU Press, 1992. [Cowan, 1974] Th. Cowan. The Theory of Braids and the Analysis of Impossible Pictures, Jour- nal of Mathematical Psychology, 11, 190-212, 1974. [Da Costa, 1974] N. C. A. Da Costa. On the Theory of Inconsistent Formal Systems, NDJFL, 15, 497-510, 1974 [Dunn, 1979] J. M. Dunn. A Theorem in Three-Valued Model Theory with Connections to Number Theory, Type Theory and Relevant Logic, Studia Logica, 38, 149-169, 1979. [Fodor, 1983] J. Fodor. The Modularity of Mind, MIT Press, 1983. [Forrest and Armstrong, 1987] P. Forrest and D. Armstrong. The Nature of Number, Philosoph- ical Papers, 16, 165-186, 1987. [Francis, 1987] G. Francis. A Topological Picturebook, Springer-Verlag, 1987. [Gilmore, 1967] P. Gilmore. The Consistency of Partial Set Theory Without Extensionality. In D.Scott (ed.) Axiomatic Set Theory, Proceedings of Symposia in Pure Mathematics, Los Angeles, U. of California, 1967. [Goodman, 1981] N. Goodman. Languages of Art, Brighton, Harvester, 1981. [Hatcher, 1982] W. Hatcher. The Logical Foundations of Mathematics, Amsterdam, North- Holland, Elsevier, 1982. [Kripke, 1975] S. Kripke. Outline of a Theory of Truth, The Journal of Philosophy 72, 690-716, 1975 [Lakatos, 1976] 1. Lakatos. Proofs and Refutations, Cambridge, Cambridge University Press, 1976. [Meyer, 1976] R K. Meyer. Relevant Arithmetic, Bulletin of the Section of the Polish Academy of Science, 5, 133-137, 1976. [Meyer and Friedman, 1992] R K. Meyer and H. Friedman. Whither Relevant Logic? The Jour- nal of Symbolic Logic, 57, 824-831, 1992. [Meyer and Mortensen, 1984J R K. Meyer and C. Mortensen. Inconsistent Models for Relevant Arithmetics, The Journal of Symbolic Logic, 49, 917-929, 1984. [Meyer et al., 1979] R K. Meyer, R Routley, and J. M. Dunn. Curry's Paradox, Analysis, 39, 124-128, 1979. [Mortensen, 1987] C. Mortensen. Inconsistent Nonstandard Arithmetic, The Journal of Sym- bolic Logic, 52 , 512-18, 1987. [Mortensen, 1988] C. Mortensen. Inconsistent Number Systems, Notre Dame Journal of Formal Logic, 29 (1988), 45-60, 1988. [Mortensen, 1990] C. Mortensen. Models for Inconsistent and Incomplete Differential Calculus, Notre Dame Journal of Formal Logic, 31, 274-285, 1990. [Mortensen, 1995] C. Mortensen. Inconsistent Mathematics, Kluwer Mathematics and Its Ap- plications Series, 1995. [Mortensen, 1997a] C. Mortensen. The Leibniz Continuity Condition, Inconsistency and Quan- tum Dynamics, The Journal of Philosophical Logic, 26, 377-389, 1997. [Mortensen, 1997b] C. Mortensen. Peeking at the Impossible, Notre Dame Journal of Formal Logic, Vol 38 No 4 (Fall 1997), 527-534, 1977. [Mortensen, 1998] C. Mortensen. On the Possibility of Science Without Numbers, The Aus- tralasian Journal of Philosophy, 182-197, 1998. [Mortensen, 2000] C. Mortensen. Topological Separation Principles and Logical Theories, Syn- these 125 Nos 1-2, 169-178, 2000. [Mortensen,2002a] C. Mortensen. Prospects for Inconsistency, in D.Batens (et.al.) eds. Fron- tiers of Paraconsistent Logic, London, Research Studies Press, 203-208, 2002. [Mortensen, 2002b] C. Mortensen. Towards a Mathematics of Impossible Pictures. In W. Car- nelli, M. Coniglio, and 1. D'Ottaviano, eds, Pamconsistency, The Logical Way to the Incon- sistent, Lecture Notes in Pure and Applied Mathematics Vol 228, New York, Marcel Dekker, 445-454, 2002.
Search
Read the Text Version
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 225
- 226
- 227
- 228
- 229
- 230
- 231
- 232
- 233
- 234
- 235
- 236
- 237
- 238
- 239
- 240
- 241
- 242
- 243
- 244
- 245
- 246
- 247
- 248
- 249
- 250
- 251
- 252
- 253
- 254
- 255
- 256
- 257
- 258
- 259
- 260
- 261
- 262
- 263
- 264
- 265
- 266
- 267
- 268
- 269
- 270
- 271
- 272
- 273
- 274
- 275
- 276
- 277
- 278
- 279
- 280
- 281
- 282
- 283
- 284
- 285
- 286
- 287
- 288
- 289
- 290
- 291
- 292
- 293
- 294
- 295
- 296
- 297
- 298
- 299
- 300
- 301
- 302
- 303
- 304
- 305
- 306
- 307
- 308
- 309
- 310
- 311
- 312
- 313
- 314
- 315
- 316
- 317
- 318
- 319
- 320
- 321
- 322
- 323
- 324
- 325
- 326
- 327
- 328
- 329
- 330
- 331
- 332
- 333
- 334
- 335
- 336
- 337
- 338
- 339
- 340
- 341
- 342
- 343
- 344
- 345
- 346
- 347
- 348
- 349
- 350
- 351
- 352
- 353
- 354
- 355
- 356
- 357
- 358
- 359
- 360
- 361
- 362
- 363
- 364
- 365
- 366
- 367
- 368
- 369
- 370
- 371
- 372
- 373
- 374
- 375
- 376
- 377
- 378
- 379
- 380
- 381
- 382
- 383
- 384
- 385
- 386
- 387
- 388
- 389
- 390
- 391
- 392
- 393
- 394
- 395
- 396
- 397
- 398
- 399
- 400
- 401
- 402
- 403
- 404
- 405
- 406
- 407
- 408
- 409
- 410
- 411
- 412
- 413
- 414
- 415
- 416
- 417
- 418
- 419
- 420
- 421
- 422
- 423
- 424
- 425
- 426
- 427
- 428
- 429
- 430
- 431
- 432
- 433
- 434
- 435
- 436
- 437
- 438
- 439
- 440
- 441
- 442
- 443
- 444
- 445
- 446
- 447
- 448
- 449
- 450
- 451
- 452
- 453
- 454
- 455
- 456
- 457
- 458
- 459
- 460
- 461
- 462
- 463
- 464
- 465
- 466
- 467
- 468
- 469
- 470
- 471
- 472
- 473
- 474
- 475
- 476
- 477
- 478
- 479
- 480
- 481
- 482
- 483
- 484
- 485
- 486
- 487
- 488
- 489
- 490
- 491
- 492
- 493
- 494
- 495
- 496
- 497
- 498
- 499
- 500
- 501
- 502
- 503
- 504
- 505
- 506
- 507
- 508
- 509
- 510
- 511
- 512
- 513
- 514
- 515
- 516
- 517
- 518
- 519
- 520
- 521
- 522
- 523
- 524
- 525
- 526
- 527
- 528
- 529
- 530
- 531
- 532
- 533
- 534
- 535
- 536
- 537
- 538
- 539
- 540
- 541
- 542
- 543
- 544
- 545
- 546
- 547
- 548
- 549
- 550
- 551
- 552
- 553
- 554
- 555
- 556
- 557
- 558
- 559
- 560
- 561
- 562
- 563
- 564
- 565
- 566
- 567
- 568
- 569
- 570
- 571
- 572
- 573
- 574
- 575
- 576
- 577
- 578
- 579
- 580
- 581
- 582
- 583
- 584
- 585
- 586
- 587
- 588
- 589
- 590
- 591
- 592
- 593
- 594
- 595
- 596
- 597
- 598
- 599
- 600
- 601
- 602
- 603
- 604
- 605
- 606
- 607
- 608
- 609
- 610
- 611
- 612
- 613
- 614
- 615
- 616
- 617
- 618
- 619
- 620
- 621
- 622
- 623
- 624
- 625
- 626
- 627
- 628
- 629
- 630
- 631
- 632
- 633
- 634
- 635
- 636
- 637
- 638
- 639
- 640
- 641
- 642
- 643
- 644
- 645
- 646
- 647
- 648
- 649
- 650
- 651
- 652
- 653
- 654
- 655
- 656
- 657
- 658
- 659
- 660
- 661
- 662
- 663
- 664
- 665
- 666
- 667
- 668
- 669
- 670
- 671
- 672
- 673
- 674
- 675
- 676
- 677
- 678
- 679
- 680
- 681
- 682
- 683
- 684
- 685
- 686
- 687
- 688
- 689
- 690
- 691
- 692
- 693
- 694
- 695
- 696
- 697
- 698
- 699
- 700
- 701
- 702
- 703
- 704
- 705
- 706
- 707
- 708
- 709
- 710
- 711
- 712
- 713
- 714
- 715
- 716
- 717
- 718
- 1 - 50
- 51 - 100
- 101 - 150
- 151 - 200
- 201 - 250
- 251 - 300
- 301 - 350
- 351 - 400
- 401 - 450
- 451 - 500
- 501 - 550
- 551 - 600
- 601 - 650
- 651 - 700
- 701 - 718
Pages:
