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 it 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
to 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 it 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.
In fact, as is well known, the property of a set of incidence matrices that it
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 it is an occurrence of
x
as a free variable in it;
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 it 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 it 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, it 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,
14
hub. 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 in
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."
If
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 it is well-formed and contains
no part of the form
{hx[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 it 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 in 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:
THEOREM
I.
If a formula is in normal form, no reduction of it is
possible.
THEOREM
11.
If 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 in the normal form.
THEOREM
111.
If 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 it 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~del,~ 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 it 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 it is the Godel representation of
3
well-formed formula and, if it is, to obtain that formula.
In 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
adel, "uber formal unentscheidbare SBtze der Principia hlathematica und
verwandter Systeme
I,"
Monatshefte fur 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
1
or any numerical variable, standing alone, is an elementary expres-
sion. If A is an elementary expression, then S(A) is an elementary expres-
sion. If 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
1
to 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 mhre 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 sequence is recursive.
We call a propositional function of positive integers recursive if the
function whose value is
2
or
1,
according to whether the propositional function
is true or false, is recursive. By a recursive property of positive integers we
shall mean a recursive propositional function of one positive integer, and by
a
recursive relation between positive integers we shall mean a recursive
propositional function of two or more positive integers.
This definition is closely related to, and was suggested by, a definition of recursive
functions which was proposed by Kurt Gbdel, in lectures at Princeton,
N.
J.,
1934, and
credited by him in part to an unpublished suggestion of Jacques Herbrand. The
principal features in which the present definition of recursiveness differs from Gbdel's
are due to
S.
C.
Kleene.
In a forthcoming paper by Kleene to be entitled, "General recursive functions of
natural numbers," (abstract in
Bulletin
of
the American Mathematical society,
vol. 41),
several definitions of recursiveness will be discussed and equivalences among them
obtained. In particular, it follows readily from Kleene's results in that paper that
every function recursive in the present sense is also recursive in the sense of
Godel
(1934) and conversely.
10
The reader may object that this algorithm cannot be held to provide an effective
calculation of the required particular value of
Pi
unless the proof is constructive that
the required equation
f,,d((k,i, k,c,.
.
.
,
knii)
=
ki
will ultimately be found. But if so
this merely means that he should take the existential quantifier which appears in our
definition of a set of recursion equations in a constructive sense. What the criterion
of constructiveness shall be is left to the reader.
The same remark applies in connection with the existence of an algorithm for
calculating the values of a X-definable function of positive integers.
352
ALONZO
CHURCH.
A
function
F,
for which the range of the dependent variable is contained
in the class of positive integers and the range of the independent variable,
or of each independent variable, is a subset (not necessarily the whole) of the
class of positive integers, will be called potentially ~ecu~sive,
if it is possible
to find a recursive function
8''
of positive integers (for which the range of the
independent variable, or of each independent variable, is the whole of the class
of positive integers), such that the value of
P
agrees with the value of
P
in
all cases where the latter is defined.
By an operation on well-formed formulas we shall mean a function for
which the range of the dependent variable is contained in the class of well-
formed formulas and the range of the independent variable, or of each in-
dependent variable, is the whole class of well-formed formulas. And we call
such an operation recursive if the corresponding function obtained by replacing
all formulas by their Cb;del representatioiis is potentially recursive.
Similarly any function for which the range of the dependent variable is
contained either in the class of positive integers or in the class of well-formed
formulas, and for which the range of each independent variable is identical
either with the class of positive integers or with the class of well-formed
formulas (allowing the case that some of the ranges are identical with one
class and some with the other), will be said to be recursive if the corresponding
function obtained by replacing all formulas by their Godel representations is
potentially recursive. We call an infinite sequence of well-formed formulas
recursive if the corresponding infinite sequence of Godel representations is
recursive. And we call a property of, or relation between, well-formed
formulas recursive if the corresponding property of, or relation between, their
Godel representations is potentially recursive.
A
set of well-formed formulas
is said to be recursively enumerable if there exists a recursive infinite sequence
which consists entirely of formulas of the set and contains every formula of
the set at least once.ll
In terms of the notion of recursiveness we may also define a proposition,
of elementary number theory, by induction as follows.
If
+
is a recursive
propositional function of n positive integers (defined by giving a particular
set of recursion equations for the corresponding function whose values are
2
and
1)
and if x,, x2,.
. .
,
x, are variables which take on positive integers as
values, then +(x,, x2,
. . .
,
x,) is a proposition of elementary number theory.
If
P
is a proposition of elementary number theory involving x as a free
It can be shown, in view of Theorem
V
below, that, if an infinite set of formulas
is recursively enumerable in this sense, it is also recursively enumerable in the sense
that there exists a recursive infiilite sequence which consists entirely of formulas of
the set and contains every formula of the set exactly once.
353
AN UNSOLVABLE PROBLEM
OF
NUMBER
THEORY.
variable, then the result of substituting a particular positive integer for all
occurrences of
x
as a free variable in
P
is a proposition of elementary number
theory, and (x)
P
and
(3
x)P
are propositions of elementary number theory,
where
(x)
and
(3s)
are respectively the universal and existential quantifiers
of x over the class of positive integers.
It
is then readily seen that the negation of a proposition of elementary
number theory or the logical product or the logical sum of two propositions
of elementary number theory is equivalent, in a simple way, to another proposi-
tion of elementary number theory.
5.
Recursiveness of the Kleene @-function.
We prove two theorems
which establish the recursiveness of certain functions which are definable in
words by means of the phrase, "The least positive integer such that," or,
"
The n-th positive integer such that."
THEOREM
IT.
If
P
is
a
recursive function of two positive integers, and
if
for every positive integer x there exists a positive integer y such that
F(x, y)
>
1,
then the function F*, such that, for every positive integer x,
F4(x) is equal to the least positive integer y for which F(x, y)
>
1,
is
recursive.
For a set of recursion equations for
P*
consists of the recursion equations
for
F
together with the equations,
where the functional variables
fz
and
f,
denote the functions
P
and
P*
re-
spectively, and
2
and
3
are abbreviations for S(1) and X(S(1)) respectively.12
THEOREM
6:.
If F is a recursive function of one positive integer, and
if
there exist an infinite number of positive integers x for which
F(x)
>
1,
then the function Po, such that, for every positive integer n, FO(n) is equal
to the n-th positive integer x (in order of increasi~ag magnitude) for which
F(x)
>
1,
is recursive.
llSince this result was obtained, it has been pointed out to the author by S.
C.
Kleene that it can be proved more simply by using the methods of the latter in
American
Journal of Mathematics,
vol. 57
(1935), p. 231
et
seq.
His proof will be given in his
forthcoming paper already referred to.
8
354
ALONZO CHURCH.
For a set of recursion equations for
F0
consists of the recursion equations
for
P
together with the equations,
92(1,Y) =g2(f1(fl(y)), S(Y)),
g2(fl(x), Y)
=
Y,
gl(l> =k,
~l(fl(~))
=
gz(1, gl(Y)
1,
where the functional variables g, and f, denote the functions
Po
and
F
respectively, and where k is the numeral to which corresponds the least positive
integer x for which P(x)
>
l.ls
6.
Recursiveness of certain functions of formulas.
We list now a
number of theorems which will be proved in detail in a forthcoming paper
by
8.
C.
Kleene
l4
or follow immediately from considerations there given.
We
omit proofs here, except for brief indications in some instances.
Our statement of the theorems and our notation differ from Kleene's in
that we employ the set of positive integers (I,&, 3,.
.
.)
in the r81e in which
he employs the set of natural llumbers (O,l,&,.
-
.).
This difference is, of
course, unessential.
We have selected what is, from some points of view, the
less natural alternative, in order to preserve the convenience and naturalness
of the identification of the formula
hub
.
a(b) with
1
rather than with 0.
THEOREM VI. The property of a positive integer, that there exists a
well-formed formula of which it is the Godel representation is recursive.
THEOREMVII.
The set of well-formed
form.ulas is recursively enumerable.
This follows from Theorems V and VI.
THEOREMVIII. The function of two variables, whose value, when takefa
of the well-formed formulas
F
and X, is the formula {F)(X), is recursive.
THEOREM IX. The function, whose value for each of the positive integers
1,2,3,
.
.
.
is the corresponding formula 1,2, 3,
.
.
.
,
is recursive.
THEOREM
X.
A
function, whose value for each of the formulas
I,&,
3,
.
.
.
is the corresponding positive integer, and whose value for other well-formed
formulas is a fixed positive integer, is recursive. Likewise the function, whose
value for each of the formulas 1,2,3,.
.
.
is the corresponding positive integer
l8
This proof is due to Kleene.
l4
5.
C.
Kleene,
"
A-definability and recursiveness," forthcoming (abstract in
Bulletilt
of
the Amerioult Mathematical Sooietu,
vol.
41).
In connection with many
of the theorems listed, see also Kurt GGdel,
Monatshefte fur Muthematik und I'hysik,
vol. 38 (1931), p. 181
et seq.,
observing that every function which is recursive in the
sense in which the word is there used by Godel is also recursive in the present more
general sense.
355
AN
UNSOLVABLE PROBLFM
OF
NUMBER THEORY.
wlus one, and whose value for other well-formed formulas is the positive
integer
1,
is recursive.
THEOREM
XI.
The relation of immediate convertibility, between well-
formed formulas, is recursive.
THEOREM
XII. It is possible to associate simultaneously with every well-
formed formula an enumeration of the forw~ulus obtainable from
it
by con-
version,
in
such a way that the function of two variables, whose value, when
taken of a well-formed formula
A
and a positive integer
n,
is the n-th formula
i~z
tlze enumeration of the formulas obtainable from
A
by conversion, is recursive.
THEOREM
XIII.
The p~operty of a well-formed formula, that
it
is in
principal normal form, is recursive.
THEOREM
The set of well-formed formulas which are
in
p~i~zcipalXIV.
normal form is recursivejy e~zumerable.
This follows from Theorems
V,
VII, XIII.
THEOREM
XV.
The set of well-formed formulas which have a normal
form is recursively enumerab1e.l5
For by Theorems
XI1
and
XIV
this set can be arranged in an infinite
square array which is recursively defined (i. e. defined by a recursive function
of two variables). And the familiar process by which this square array is
reduced to a single infinite sequence is recursive (i. e. can be expressed by
means of recursive functions).
THEOREM
XVI. Every recursive fu~zction of positive integers is
A-definable.16
THEOREM
XVII. Every A-definable function of positive integers is
re~ursive.~~
For functions of one positive integer this follows from Theorems
IX,
VIII, XII, XIII, IV, X.
For functions of more than one positive integer
l6
This theorem was first proposed by the present author, with the outline of proof
here indicated. Details of its proof are due to Kleene and will be given by him in his
forthcoming paper,
"
A-definability and recursiveness."
10This,theorem can be proved as a straightforward application of the methods
introduced by Kleene in the
Ameriea~z Jour~tal of Mathematics (loc. cit.).
In the form
here given it was first obtained by Kleene.
The related result had previously been
obtained by
J.
B.
Rosser that, if we modify the definition of
well-formed
by omitting
the requirement that M contain
~x
as a free variable in order that Xx[M] be well-
formed, then every recursive function of positive integers is X-definable in the resulting
modified sense.
I'
This result was obtained independently by the present author and
S.
C.
Kleene
at about the same time.
3S6
ALONZO
CHURCH.
it follows by the same method, using a generalization of Theorem
IV
to
functions of more than two positive integers.
7.
The
notion of effective calculability.
We now define the notion,
already discussed, of an effectively c~~lculable function of positive integers by
identifying it with the notion of a recursive function of positive integers
l8
(or of a A-definable function of positive integers).
This definition is thought
to be justified by the considerations which follow, so far as positive justification
can ever be obtained for the selection of a formal definition to correspond to
an intuitive notion.
It
has already been pointed out that, for every function of positive
integers which is effectively calculable in the sense just defined, there exists
an algorithm for the calculation of its values.
Conversely it is true, under the same definition of effective calculability,
that every function, an algorithm for the calculation of the values of which
exists, is effectively calculable. For example, in the case of a function
P of
one positive integer, an algorithm consists in a method by which, given any
positive integer n, a sequence of expressions (in some notation)
E,,,
E,,,
.
.
.
,
E,,,,,
can be obtained; where Enl is effectively calculable when n is given;
where
E,i
is effectively calculable when n and the expressions
Enj,
j
<
i,
are given;
and where, when n and all the expressions
En(
up to and including
E,,,
are
given, the fact that the algorithm has terminated becomes effectively known
and the value of
P(n) is effectively calculable. Suppose that we set up
a
system of Godel representations for the notation employed in the expressions
Eni, and that we then further adopt the method of Gdel of representing a
finite sequence of expressions
Em,,
E,,,
. . .
,
E,i
by the single positive integer
i?en13enz.
. . pienz where
e,,,
e,,,
.
.
.
,
en< are respectively the Godel representa-
tions of
E,,, E,,,
. .
.
,
E,i
(in particular representing a vacuous sequence of
expressions by the positive integer 1). Then we may define a function G
of two positive integers such that, if x represents the finite sequence.
E,,,
E,,,
.
.
.
,
Erik,
then G(n, 2) is equal to the Godel representation of
E%i,
where
i
=
k
+
1,
or is equal to 10 if
k
=
r,
(that is if the algorithm has
terminated with E,&), and in any other case G(n, x) is equal to
1.
And
we may define a function
H
of two positive integers, such that the value of
H(n, x) is the same as that of G(n, x), except in the case that G(n, x)
=
10,
in which case H(n,
x)
=
P(n). If the interpretation is allowed that the
The question of the relationship betwen effective calculability and recursiveness
(which it is here proposed to answer by identifying the two notions) was raised by
Gdel in conversation with the author.
The corresponding question of the relationship
between effective calculability and A-definability had previously been proposed by the
author independently.
BN UNSOLVABLE PROBLEM OF NUMBER THEORY.
35'1
requirement of effective calculability which appears in our description of an
algorithm means the effective caIculabiIity of the functions
G
and H,19 and
if we take the effective calculability of
G
and
H
to mean recursiveness
(A-definability), then the recursiveness (A-definability) of
F
follows by
a
straightforward argument.
Suppose that we are dealing with some particular system of symbolic logic,
which contains a symbol,
=,
for equality of positive integers, a symbol
{
}
(
) for the application of a function of one positive integer to its argu-
ment, and expressions
1,
2,
3,.
. .
to stand for the positive integers. The
theorems of the system consist of
a finite, or enumerably infinite, list of
expressions, the formal axioms, together with all the expressions obtainable
from them by a finite succession of applications of operations chosen out of
a given finite, or enumerably infinite, list of operations, the rules of procedure.
If the system is to serve at all the purposes for which a system of symbolic
logic is usually intended, it is necessary that each rule of procedure be an
effectively calculable operation, that the complete set of rules of procedure
(if infinite) be effectively enumerable, that the complete set of formal axioms
(if infinite) be effectively enumerable, and that the relation between a positive
integer and the expression which stands for it be effectively determinable.
Suppose that we interpret this to mean that, in terms of a system of
Godel
representations for the expressions of the logic, each rule of procedure must
be a recursive operation,2O the complete set of rules of procedure must be
recursively enumerable (in the sense that there exists a recursive function
@
such that @(n, x) is the representation of the result of applying the n-th rule
of procedure to the ordered finite set of formulas represented by x), the
complete set of formal axioms must be recursively enumerable, and the relation
between a positive integer and the expression which stands for it must be
recursive.21
And
let us call a function
F
of one positive integer
22
calculable
within the logic if there exists an expression f in the logic such that {f)
("p)
=
v
is a theorem when and only when F(m)
=
n is true,
p
and
v
being the ex-
pressions which stand for the positive integers m and n. Then, since the
l8
If
this interpretation or some similar one is not allowed,
it
is difficult to see
how the notion of an algorithm can be given any exact meaning at all.
AS a matter of fact, in known systems of symbolic logic, e. g. in that of
P~incipia
Mathernatica,
the stronger statement holds, that the relation of
immediate consequence
(unmittelba~e B'olge)
is recursive.
Cf. Gjjdel,
loc. cit.,
p.
185.
In any case where the
relation of immediate consequence is recursive it is possible to find a set of rules
of procedure, equivalent to the original ones, such that each rule is a (one-valued)
recursive operation, and the complete set of rules is recursively enumerable.
The author is here indebted to GSdel, who, in his
1934
lectures already referred
to, proposed substantially theae conditions, but in terms of the more restricted notion
358
-4LONZO
CHURCH.
complete set of theorems of the logic is recursively enumerable, it follows by
Theorem IV above that every function of one positive integer which is
calculable within the logic is also effectively calculable (in the sense of our
definition).
Thus it is shown that no more general definition of effective calculability
than that proposed above can be obtained by either of two methods which
naturally suggest themselves
(1) by defining a function to be effectively
calculable if there exists an algorithm for the calculation of its values
(2)
by
defining a function
P
(of one positive integer) to be effectively calculable if,
for every positive integer
rn,
there exists a positive integer n such that
P(m)
=
n is a provable theorem.
8.
Invariants
of
conversion.
The problem naturally suggests itself to
find invariants of that transformation of formuIas which we have called con-
version.
The only effectively calculable invariants at present known are the
immediately obvious ones (e. g. the set of free variables contained in a formula).
Others of importance very probably exist. But we shall prove (in Theorem
XIX) that, under the definition of effective calculability proposed in
$
7,
no complete set of efectively calculable invariants of conversion exists (cf.
$
1).
The resuIts of Kleene (American Journal of Nathematics,
1935) make
it clear that, if the problem of finding a complete,set of effectively calculable
invariants of conversion were solved, most of the familiar unsolved problems of
elementary number theory would thereby also be solved. And from Theorem
XVI above it follows further that to find a complete set of effectively calculable
invariants of conversion would imply the solution of the Entscheidungsproblem
for any system of symbolic logic whatever (subject to the very general re-
strictions of
$
7). In the light of this it is hardly surprising that the problem
to find such a set of invariants should be unsolvable.
It
is to be remembered, however, that, if we consider only the statement
of the problem (and ignore things which can be proved about it by more or
less lengthy arguments), it appears to be a problem of the same class as the
problems of number theory and topoIogy to which it was compared in
$
1,
having no striking characteristic by which it can be distinguished from them.
The temptation is strong to reason by analogy that other important problems
of this class may also be unsolvable.
of recursiveness which he had employed in
1931,
and using the condition that the
relation of immadiate consequence be recursive instead of the present conditions on the
rules of procedure.
22
We confine ourselves for convenience to the case of functions of one positive
integer. The extension to functions of several positive integers is immediate.
AN UNSOLVABLE PROBLEM OF NUMBER THEORY.
359
LEMMA.
The problem, to find a recursive function of two formulas
A
and B whose value is 2 or
1
according as
A
conv B
or
not, is equivalent
to the problem, to find a recursive function of one formula C whose value is
2 or
1
according as
C
has a normal form
or
not.23
For, by Theorem X, the formula
a
(the formula b), which stands for the
positive integer which is the Godel representation of the formula
A
(the
formula B), can be expressed as a recursive function of the formula
A
(the
formula B). Moreover, by Theorems VI and XII, there exists a recursive
function
F
of two positive integers such that, if m is the Godel representation
of a well-formed formula
M,
then P(m, n) is the Godel representation of the
n-th formula in an enumeration of the formulas obtainable from
M
by con-
version.
And, by Theorem
XVI,
P
is A-definable, by a formula
f.
If we define,
21-
S(Ax. x(I), I),
Zz+S (Axy. S(X) --y,I),
where
2
is the formula defined by Kleene (American Journal of Mathematics,
vol. 57 (1935)) p. 226)) then Z1 and Z2 A-define the functions of one positive
integer whose values, for a positive integer n, are the n-th terms respectively
of the infinite sequences
1,1,
2,1, 2, 3,
.
.
.
and 1,2,1, 3, 2,1,
.
. .
.
By Theorem
VIII the formula,
where
and
8
are defined as by Kleene (loc. cit., p. 173 and p. 231), is a
recursive function of
A
and B, and this formula has a normal form if and
only if
A
conv B.
Again, by Theorem X, the formula
c,
which stands for the positive
integer which is the Godel representation of the formula C, can be expressed
as a recursive function of the formula
C.
By Theorems VI and XIII, there
exists a recursive function G of one positive integer such that G(m)
=
2
if m is the Godel representation of a formula in principal normal form, and
G(m)
=
1
in any other case. And, by Theorem XVI, G is A-definable, by a
formula
g.
By Theorem VIII the formula,
25
These two problems, in the forms,
(1
)
to find an effective method of determining
of any two formulas
A
and
B
whether
A
conv
B,
(2)
to find an effective method of
determining of any formula
C
whether it has a normal form, were both proposed by
Kleene to the author, in the course of a discussion of the properties of the p-function,
about
1932.
Some attempts towards solution of
(1)
by means of numerical invariants
were actually made by Kleene at about that time.
360
ALONZO CHURCH.
where
f
is the formula
f
used in the preceding paragraph, is a recursive func-
tion of C, and this formula is convertible into the formula
1
if and only if
C has a normal form.
Thus we have proved that a formula C can be found as a recursive
function of formulas
A
and
B,
such that C has a normal form if and only
if
A
conv
B;
and that a formula
A
can be found as a recursive function of
a
formula
C,
such that
A
conv
1
if and only if C has a normal form. From this
the lemma follows.
THEOREM XVIII, There
is
no recursive function of a formula C, whose
value
is 2 or
1
according
as
C has a normal form or ~zot.
That is, the property of a well-formed formula, that it has a normal form,
is not recursive.
For assume the contrary.
Then there exists a recursive function
H
of one positive integer such
that H(m)
=
2 if m is the Giidel representation of a formula which has
a.
normal form, and H(m)
=
1
in any other case. And, by Theorem XVI,
H
is A-definable by a formula
Ij.
By Theorem XV, there exists an enumeration of the well-formed formulas
which have a normal form, and a recursive function
A
of one positive integer
such that A(n)
is the Godel representation of the n-th formula in this
enumeration.
And, by Theorem XVI,
A
is A-definable, by a formula
a.
By Theorems VI and VIII, there exists a recursive function
B
of two
positive integers such that, if m and n are GBdel representations of well-
formed formulas
M
and N, then B(m,
n)
is the Godel representation of
{M)
(N).
And, by Theorem XVI, B is A-definable, by a formula
6.
By Theorems VI and X, there exists a recursive function C of one positive
integer such that, if m is the Gdel representation of one of the formulas
1,2, 3,.
.
.
,
then C(,m) is the corresponding positive integer plus one, and
in any other case C(m)
=
1.
And, by Theorem XVI, C is A-definable, by
a
formula
c.
By Theorem IX there exists a recursive function
Z-I
of one positive
integer, whose value for each of the positive integers
1,
2, 3,.
. .
is the God~l
representation of the c~~responding And, by Theorem formula 1,2, 3, .
.
..
XVI,
Z-I
is A-definable, by a formula
g.
Let
f
and
g
be the formulas
f
and
g
used in the proof of the Lemma.
By Kleene 15111 Cor. (loc. cit., p. 220), a formula
b
can be found such that,
b
(1) conv Ax
.
x(1)
b(2)
convAu.c(f(u,$(hm.g(f(u,m)),
1))).
AN UNSOLVABLE PROBLEM OF NUMBER THEORY.
We define,
e+hn. b(C(6(a(n),3(n))), b(a(n),a,(n))).
Then if n is one of the formulas 1,2, 3,.
. .
,
e(n) is convertible into one
of the formulas 1,2, 3,.
.
.
in accordance with the following rules: (1) if
6 (a (n), 3 (n)
)
conv a formula which stands for the Qodel representation of a
formula which has no normal form,
e
(n) conv
1,
(2) if 6 (a (n), 3 (n)
)
conv
a
formula which stands for the Gijdel representation of a formula which has a
principal normal form which is not one of the formulas 1,2,3,.
.
.
,
e
(n) conv
1,
(3) if 6 (a(n),
a,
(n)
)
conv a formula which stands for the Gijdel representation
of a formula which has a principal normal form which is one of the formulas
1,2,3,
.
.
.
,
e(n) conv the next following formula in the list 1,2,3,.
. .
.
By Theorem
111,
since e(1) has a normal form, the formula
e
has
a
normal form. Let
C$
be the formula which stands for the G6del representation
of
e.
Then, if n is any one of the formulas
1,
2, 3,.
.
.
,
C$
is not convertible
into the formula a
(n),
because 6 (6,3 (n)
)
is, by the definition of
6,
con-
vertible into the formula which stands for the Ciidel representation of e(n),
while 6 (a (n),
a,
(n)
)
is, by the preceding paragraph, convertible into
the
formula stands for the Godel representation of a formula definitely not con-
vertible into e(n) (Theorem 11). But, by our definition of a, it must be true
of one of the formulas n in the list 1,2,3,
. . .
that a(n) conv
C$.
Thus, since our assumption to the contrary has led to a contradiction, the
theorem must be true.
In order to present the essential ideas without any attempt at exact
statement, the preceding proof may be outlined as follows. We are to deduce
a contradiction from the assumption that it is effectively determinable of
every well-formed formula whether or not it has a normal form. If this
assumption holds, it is effectively determinable of every well-formed formula
whether or not it is convertible into one of the formulas
l,2,3,.
. .
;
for,
given a well-formed formula R, we can first determine whether or not it has
a normal form, and if it has we can obtain the principal normal form by
enumerating the formulas into which R is convertible (Theorem XII) and
picking out the first formula in principal normal form which occurs in the
enumeration, and we can then determine whether the principal normal form
is one of the formulas
1,2, 3,.
.
.
.
Let A,, A,,
A,,
. .
.
be an effective enumera-
tion of the well-formed formulas which have a normal form (Theorem
XV).
Let
E
be a function of one positive integer, defined by the rule that, where
m
and n are the formulas which stand for the positive integers
m
and n
respectively,
E
(n)
=
1
if {A,) (n) is not convertible into one of the formulas
1,2,3,
-
and E(n)
=
m
+
1
if
{A,)
(n) conv
m
and
m
is one of the
.
a,
formulas
1,
2, 3,.
.
.
.
The function
E
is effectively calculable and is there-
362
ALONZO
CHURCH.
fore A-definable, by a formula e. The formula
e
has a normal form, since
e(1) has a normal form. But e is not any one of the formulas A,, A,, A,,
.
. .
,
because, for every
n,
e(n) is a formula which is not convertible into {A,)
(n).
And this contradicts the property of the enumeration A,, A,, A,,
. .
.
that it
contains all well-formed formulas which have a normal form.
COROLLARY
1.
The set of well-formed formulas which have no normal
form is' not recursively en~merable.~~
For, to outline the argument, .the set of well-formed formulas which have
a normal form is recursively enumerable, by Theorem XV. If the set of those
which do not have a
normal form were aslo recursively enumerable,
it
would
be possible to tell effectively of any well-formed formula whether it had a
normal form, by the process of searching through the two enumerations until
it was found in ons or the other. This, however, is contrary to Theorem XVIII.
This corollary gives us an example of an effectively enumerable set (the
set of well-formed formulas) which is divided into two non-overlapping sub-
sets of which one is effectively enumerable and the other not. Indeed, in view
of the difficulty of attaching any reasonable meaning to the assertion that a
set is enumerable but not effectively enumerable, it may even be permissible
to go a step further and say that here is an example of an enumerable set
which is divided into two non-overlapping subsets of which one is enumerable
and the other non-en~merable.,~
COROLLARY
2.
Let a function
F
of one positive integer be defined by
the rule that
P(7z)
shall equal
2
or
1
according as
n
is or is not the Godel
representation of a formula which has a normal form. Then
F
(if
its definition
be admitted as valid at all) is an example of a non-recursive function of posi-
tive integers.26
This follows at once from Theorem XVIII.
"This corollary was proposed by
J.
B. Rosser.
The outline of proof here given for it is open to the objection, recently called to
the author's attention by Paul Bernays, that it ostensibly requires a non-constructive
use of the principle of excluded middle. This objection is met by a revision of the
proof, the revised proof to consist in taking any recursive enumeration of formulas
which have no normal form and showing that this enumeration is not a complete
enumeration of such formulas, by constructing a formula
e(n)
such that
(1)
the
supposition that
e(n)
occurs in the enumeration leads to contradiction
(2)
the sup-
position that
e
(n)
has a normal form leads to contradiction.
IVf. the remarks of the author in
The American Mathematical Monthlu,
vol.
41
(1934),
pp.
356-361.
26
Other examples
of non-recursive functions have since been obtained by
S.
C.
Kleene in a different connection.
See his forthcoming paper, "General recursive func-
tions of natural numbers."
AN
UNSOLVABLE
PROBLEM
OF
NUMBER THEORY.
363
Consider the infinite sequence of positive integers, F(l), P(2), P(3),
.
. .
.
It
is impossible to specify effectively a method by which, given any n, the
n-th term of this sequence could be calculated. But it is also impossible ever
to select a particular term of this sequence and prove about that term that
its value cannot be calculated (because of the obvious theorem that if this
sequence has terms whose values cannot be calculated then the value of each
of those terms 1). Therefore
it
is natural to raise the question whether, in
spite of the fact that there is no systematic method of effectively calculating
the terms of this sequence, it might not be true of each term individually that
there existed a method of calculating its value. To this question perhaps the
best answer is that the question itself has
no meaning, on the ground that the
universal quantifier which
it
contains is intended to express a mere infinite
succession of accidents rather than anything systematic.
There is in consequence some room for doubt whether the assertion that
the function
F
exists can be given a reasonable meaning.
THEOREMXIX. There is no recursive function of two formulas
A
and
B,
whose value is
2
or
1
according as
A
conv
B
or not.
This follows at once from Theorem XVIII and the Lemma preceding it.
As a corollary of Theorem XIX, it follows that the Entscheidungs-
problem is unsolvable in the case of any system of symbolic logic which is
w-consistent (w-widerspruchsfrei) in the sense of Godel (loc. cit., p. 187) and
is strong enough to allow certain comparatively simple methods of definition
and proof. For in any such system the proposition will be expressible about
two positive integers a and
b
that they are Godel representations of formulas
A
and
B
such that
A
is immediately convertible into
B.
Hence, utilizing the
fact that a conversion is a finite sequence of immediate conversions, the proposi-
tion @(a, b) will be expressible that a and
b
are G'ijdel representations of
formulas
A
and
B
such that
A
conv
B.
Moreover if
A
conv
B,
and a and
b
are the Gbdel representations of
A
and
B
respectively, the proposition *(a, b)
will be provable in the system, by a proof which amounts to exhibiting, in terms
of Godel representations, a particular finite sequence of immediate conversions,
leading from
A
to B; and if
A
is not convertible into
B,
the w-consistency
of the system means that *(a, b) will not be provable. If the Entscheidungs-
problem for the system were solved, there would be a means of determining
effectively of every proposition
@(a, b) whether it was provable, and hence
a means of determining effectively of every pair of formulas
A
and
B
whether
A
conv
B,
contrary to Theorem XIX.
In particular, if the system of Principia iklathematica be w-consistent,
its Entscheidungsproblem is unsolvable.