church-1936

An Unsolvable Problem of Elementary Number Theory Alonzo Church American Journal of Mathematics, Vol. 58, No. 2. (Apr., 1936), pp. 345-363. Stable URL: http://links.jstor.org/sici?sici=0002-9327%28193604%2958%3A2%3C345%3AAUPOEN%3E2.0.CO%3B2-1 American Journal of Mathematics is currently published by The Johns Hopkins University Press. Your use of the JSTOR archive indicates your acceptance of JSTOR's Terms and Conditions of Use, available at http://www.jstor.org/about/terms.html. JSTOR's Terms and Conditions of Use provides, in part, that unless you have obtained prior permission, you may not download an entire issue of a journal or multiple copies of articles, and you may use content in the JSTOR archive only for your personal, non-commercial use. Please contact the publisher regarding any further use of this work. Publisher contact information may be obtained at http://www.jstor.org/journals/jhup.html. Each copy of any part of a JSTOR transmission must contain the same copyright notice that appears on the screen or printed page of such transmission. The JSTOR Archive is a trusted digital repository providing for long-term preservation and access to leading academic journals and scholarly literature from around the world. The Archive is supported by libraries, scholarly societies, publishers, and foundations. It is an initiative of JSTOR, a not-for-profit organization with a mission to help the scholarly community take advantage of advances in technology. For more information regarding JSTOR, please contact support@jstor.org. http://www.jstor.org Mon Mar 3 10:49:53 2008 AN UNSOLVABLE PROBLEM OF ELEMENTARY NUMBER THEORY.= 1. Introduction. There is a class of problems of elementary number theory which can be stated in the form that i t is required to find an effectively calculable function f of n positive integers, such that f (x,, x,, . . . ,x,) =2 is a necessary and sufficient condition for the truth of a certain proposition of elementary number theory involving x,, x,, . . .,x, as free variables. An example of such a problem is the problem to find a means of de- termining of any given positive integer n whether or not there exist positive integers 2, y, z, such that xn -/- yn =xn. For this may be interpreted, required t o find an effectively calculable function f, such that f ( n ) is equal to 2 if and only if there exist positive integers x, y, z, such that xn + yn =xn. Clearly the condition that the function f be effectively calculable is an essential part of the problem, since without i t the problem becomes trivial. Another example of a problem of this class is, for instance, the problem of topology, to find a complete set of effectively calculable invariants of closed three-dimensional simplicia1 manifolds under homeomorphisms. This problem can be interpreted as a problem of elementary number theory in view of the fact that topological complexes are representable by matrices of incidence. I n fact, as is well known, the property of a set of incidence matrices that i t represent a closed three-dimensional manifold, and the property of two sets of incidence matrices that they represent homeomorphic complexes, can both be described in purely number-theoretic terms. If we enumerate, in a straight- forward way, the sets of incidence matrices which represent closed three- dimensional manifolds, it will then be immediately provable that the problem under consideration (to find a complete set of effectively calculable invariants of closed three-dimensional manifolds) is equivalent to the problem, to find an effectively calculable function f of positive integers, such that f (m, lz) is equal to 2 if and only if the m-th set of incidence matrices and the lz-th set of incidence matrices in the enumeration represent homeomorphic complexes. Other examples will readily occur to the reader. Presented to the American Mathematical Society, April 19, 1935. The selection of the particular positive integer 2 instead of some other is, of course, accidental and non-essential. 345 346 ALONZO CHURCH. The purpose of the present paper is to propose a definition of effective calculability which is thought to correspond satisfactorily to the somewhat vague intuitive notion in terms of which problems of this class are often stated, and to show, by means of an example, that not every problem of this class is solvable. 2. Conversion and A-definability. We select a particular list of sym- bols, consisting of the symbols { ,), ( ,), X, [ ,1, and an enumerably infinite set of symbols a, b, c, . . . to be called variables. And we define the word formula to mean any finite sequence of symbols out of this list. The terms well-formed formula, free variable, and bound variable are then defined by induction as follows. A variable x standing alone is a well-formed formula and the occurrence of x in i t is an occurrence of x as a free variable in i t ; if the formulas F and X are well-formed, {F ) (X) is well-formed, and an occurrence of x as a free (bound) variable in F or X is an occurrence of x as a free (bound) variable in {F ) (X) ; if the formula M is well-formed and contains an occurrence of x as a free variable in M, then hx[M] is well-formed, any occurrence of x in h [ M ] is an occurrence of x as a bound variable in hx[M], and an occurrence of a variable y, other than x, as a free (bound) variable in M is an occurrence of y as a free (bound) variable in hx[M]. As will appear, this definition of effective calculability can be stated in either of two equivalent forms, ( 1 ) that a function of positive integers shall be called effectively calculable if it is h-definable in the sense of $ 2 below, ( 2 ) that a function of positive integers shall be called effectively calculable if i t is recursive in the sense of $ 4 below. The notion of h-definability is due jointly to the present author and S. C. Kleene, successive steps towards i t having been taken by the present author in the Annals of Mathematics, vol. 34 (1933), p. 863, and by Kleene in the American Journal of Mathematics, vol. 57 (1935), p. 219. The notion of recursiveness in the sense of $ 4 below is due jointly to Jacques Herbrand and Kurt Gijdel, as is there explained. And the proof of equivalence of the two notions is due chiefly to Kleene, but also partly to the present author and to J. B. Rosser, as explained below. The proposal to identify these notions with the intuitive notion of effective calculability is first made in the present paper (but see the first footnote to $ 7 below). With the aid of the methods of Kleene (American Journal of Mathematics, 1935), the considerations of the present paper could, with comparatively slight modification, be carried through entirely in terms of X-definability, without making use of the notion of recursiveness. On the other hand, since the results of the present paper were obtained, i t has been shown by Kleene (see his forthcoming paper, "General recursive functions of natural numbers") that analogous results can be obtained entirely in terms of recursiveness, without making use of X-definability. The fact, however, that two such widely different and ( in the opinion of the author) equally natural definitions of effective calculability turn out to be equivalent adds to the strength of the reasons adduced below for believing that they constitute as general a characterization of this notion as is consistent with the usual intuitive understanding of it. AN UNSOLVABLE PROBLEM OF NUMBER THEORY. 347 We shall use heavy type letters to stand for variable or undetermined formulas. And we adopt the convention that, unless otherwise stated, each heavy type letter shall represent a well-formed formula and each set of symbols standing apart which contains a heavy type letter shall represent a well- formed formula. When writing particular well-formed formulas, we adopt the following abbreviations. A formula {F) (X) may be abbreviated as F(X) in any case where F is or is represented by a single symbol. A formula {{F) (X) ) (Y) may be abbreviated as {F)(X, Y), or, if F is or is represented by a single symbol, as F(X, Y) . And {{{F) (X) ) (Y) ) ( 2 ) may be abbreviated as {F) (X, Y, Z) , or as F(X, Y, Z) , and so on. A formula Ax, [I&,[. . . Xx,[M] . . .]] may be abbreviated as Ax,x,. . . & .M or as Xx,x, . . . x,M. We also allow ourselves at any time to introduce abbreviations of the form that a particular symbol a shall stand for a particular sequence of symbols A, and indicate the introduction of such an abbreviation by the nota- tion a -+ A, to be read, " a stands for A." We introduce at once the following infinite list of abbreviations, 1 4hub. a (b) , 2 -+ Xab . a ( a ( b ) ) , 3 -+hub9 a ( a ( a ( b ) ) ) , and so on, each positive integer in Arabic notation standing for a formula of the form hab .a (a ( . . . a ( b ) . . .)). The expression S>M I is used to stand for the result of substituting N for x throughout M. We consider the three following operations on well-formed formulas : I. To replace any part h [ M ] of a formula by hy[S;M I ] , where y is a variable which does not occur in M. 11. To replace any part {Ax[M]) (N) of a formula by S;;M I , provided that the bound variables in M are distinct both from x and from the free variables i n N. 111. To replace any part S;M I (not immediately following A) of a fornzula by {Ax [MI ) (N), provided that the bound variables in M are distinct both from x and from the free variables in N. Any finite sequence of these operations is called a conversion, and if B is obtainable from A by a conversion we say that A is convertible into B, or, " A conv B." I f B is identical with A or is obtainable from A by a single 348 ALONXU CHURCH. application of one of the operations I, 11,111,we say that A is immediately convertible into B. A conversion which contains exactly one application of Operation 11,and no application of Operation 111,is called a reduction. A formula is said to be in normal form, if i t is well-formed and contains no part of the form { h x [ M ] )(N). And B is said to be a normal form of A if B is in normal form and A conv B. The originally given order a, b, c, . . . of the variables is called their natural order. And a formula is said to be in principal normal form if it is in normal form, and no variable occurs in i t both as a free variable and as a bound variable, and the variables which occur in it immediately following the symbol h are, when taken in the order i n which they occur in the formula, in natural order without repetitions, beginning with a and omitting only such variables as occur in the formula as free variable^.^ The formula B is said to be the principal normal form of A if B is in principal normal form and A conv B. Of the three following theorems, proof of the first is immediate, and the second and third have been proved by the present author and J. B. Rosser: THEOREMI. I f a formula is in normal form, no reduction of it is possible. THEOREM11. I f a formula has a normal form, this normal form is unique to within applications of Operation I, and any sequence of reductions of the formula must (if continued) terminate i n the normal form. THEOREM111. I f a formula has a normal form, every well-formed part of it has a normal form. We shall call a function a function of positive integers if the range of each independent variable is the class of positive integers and the range of the dependent variable is contained in the class of positive integers. And when it is desired to indicate the number of independent variables we shall speak of a function of one positive integer, a function of two positive integers, and so on. Thus if F is a function of n positive integers, and al, a,, . . . ,a, are positive integers, then F(al , a,, . . . ,a,) must be a positive integer. For example, he formulas Xab . 71 ( a ) and Xa . a (Xc . b (c ) ) are in principal normal form, and Xac. c ( a ) , and Xbc. c ( b ) , and ha . a(Xa. b ( a ) ) are in normal form but not in principal normal form. Use of the principal normal form was suggested by S. C. Kleene as a means of avoiding the ambiguity of determination of the normal form of a formula, which is troublesome in certain connections. Observe that the formulas 1 ,2 ,3 , . . . are all in principal normal form. Alonzo Church and J. B. Rosser, "Some properties of conversion,'? forthcoming (abstract in Bulletin of the American Mathematical Bociety, vol. 41, p. 332). AN UNSOLVABLE PROBLEM OF NUMBER THEORY. 349 A function P of one positive integer is said to be A-definable if i t is possible to find a formula F such that, if P (m ) =r and m and r are the formulas for which the positive integers m and r (written in Arabic notation) stand according to our abbreviations introduced above, then {F)(m ) conv r. Similarly, a function F of two positive integers is said to be A-definable if it is possible to find a formula F such that, whenever P (m , n) =y, the formula {F) (m, n ) is convertible into r (m, n, r being positive integers and m, n, r the corresponding formulas). And so on for functions of three or more positive integemO It is clear that, in the case of any A-definable function of positive integers, the process of reduction of formulas to normal form provides an algorithm for the effective calculation of particular values of the function. 3. The Giidel representation of a formula. Adapting to the formal notation just described a device which is due to G ~ d e l , ~ associate with we every formula a positive integer to represent it, as follows. To each of the symbols {, (, [ we let correspond the number 11, to each of the symbols ), ), ] the number 13, to the symbol A the number 1, and to the variables a, b, c,. . . the prime numbers 17, 19, 23,. . . respectively. And with a formula which is composed of the n symbols T,, T,, . . ,T, in order we associate the number 2t13tz. . .pmtn, where ti is the number corresponding to the symbol 76 , and where p, stands for the n-th prime number. This number 2t13tz. . . pmt. will be called the Gadel representation of the formula TITZ . . . 7%. Two distinct formulas may sometimes have the same Godel representation, because the numbers 11 and 13 each correspond to three different symbols, but i t is readily proved that no two distinct well-fo~med formulas can have the same Gadel yepresentation. It is clear, moreover, that there is an effective method by which, given any formula, its Godel representation can be calculated; and likewise that there is an effective method by which, given any positive integer, it is possible to determine whether i t is the Godel representation of 3 well-formed formula and, if i t is, to obtain that formula. I n this connection the Godel representation plays a r61e similar to that Cf. S. C. Kleene, "A theory of positive integers in formal logic," American Journal of Nathematics, vol. 57 (1935), pp. 153-173 and 219-244, where the A-definability of a number of familiar functions of positive integers, and of a number of important general classes of functions, is established. Kleene uses the term definable, or formally definable, in the sense in which we are here using A-definable. Kurt a d e l , "uber formal unentscheidbare SBtze der Principia hlathematica und verwandter Systeme I," Monatshefte f u r Mathematik und Physik, vol. 38 (1931), pp. 173-198. 350 ALONZO CHURCH. of the matrix of incidence in combinatorial topology (cf. 5 1 above'). For there is, in the theory of well-formed formulas, an important class of problems, each of which is equivalent to a problem of elementary number theory obtainable by means of the @del representati~n.~ 4. Recursive functions. We define a class of expressions, which we shall call elementary expressions, and which involve, besides parentheses and commas, the symbols 1, S, an infinite set of numerical variables x, y, 2 , . . a , and, for each positive integer n, an infinite set f,, g,, h,, . . . of functional variables with subscript n. This definition is by induction as follows. The symbol 1or any numerical variable, standing alone, is an elementary expres- sion. If A is an elementary expression, then S (A) is an elementary expres- sion. I f A,, A,, . . . ,A, are elementary expressions and f, is any functional variable with subscript n, then f,(A1, A,, . . . ,A,) is an elementary expression. The particular elementary expressions 1, # ( I ) , S (S ( 1 ) ), . . . are called numerals. And the positive integers I,%,3,. . are said to correspond to the numerals 1, X(1), S (S (1 ) ), . . . . An expression of the form A =B, where A and B are elementary ex- pressions, is called an elementary equation. The derived equations of a set E of elementary equations are defined by induction as follows. The equations of E themselves are derived equations. If A =B is a derived equation containing a numerical variable x, then the result of substituting a particular numeral for all the occurrences of z in A =B is a derived equation. If A =B is a derived equation containing an elementary expression C (as part of either A or B), and if either C =D or D =C is a derived equation, then the result of substituting D for a particular occurrence of C in A =B is a derived equation. Suppose that no derived equation of a certain finite set E of elementary equations has the form k =1 where k and 1 are different numerals, that the functional variables which occur in E are f,,l, f,,2,. . .,f,,' with subscripts n,, n,, . . . ,n, respectively, and that, for every value of i from 1to r inclusive, and for every set of numerals kl" k25 , . .,Ic,," there exists a unique numeral kt such that f,,"lc," k25. . .,k,," =kk" is a derived equation of E. And let F1,B2,.. . ,P be the functions of positive integers defined by the con- s This is merely a special case of the now familiar remark that, in view of the Cadel representation and the ideas associated with it, symbolic logic in general can be regarded, mathematically, as a branch of elementary number theory. This remark is essentially due to Hilbert (cf. for example, Verhandlungen des dritten internationalen Mathematikey-Kongresses in Heidelberg, 1994, p. 185; also Paul Bernays in Die Naturwissenschaften, vol. 10 (1922), pp. 97 and 98) but is most clearly formulated in terms of the GGdel representation. AN UNSOLVABLE PROBLEM OF NUMBER THEORY. 351 dition that, in all cases, Fi(mli, mz" . . . ,mn,() shall be equal to mi, where mIi, mZi, . . . ,mn,i, and m h r e the positive integers which correspond to the numerals kli, k,". . . ,knii, and ki respectively. Then the set of equa- tions E is said to define, or to be a set of recu~sion equations for, any one of the functions Fi, and the functional variable f,,% is said to denote the function Fi. A function of positive integers for which a set of recursion equations can be given is said to be recur~ive.~ It is clear that for any recursive function of positive integers there exists an algorithm using which any required particular value of the function can be effectively calculated. For the derived equations of the set of recursion equa- tions B are effectively enumerable, and the algorithm for the calculation of particular values of a function Pi, denoted by a functional variable fndi, consists in carrying out the enumeration of the derived equations of E until the required particular equation of the form fn,i(lcli, k,i, . . . ,IC,,~)=ki is f ound.1° We call an infinite sequence of positive integers recursive if the function F such that F ( n ) is the n-th term of the sequen