was still some hope that most of mathematics could be made precise with
mechanically verifiable proofs. It was this problem that Turing and other
mathematicians of the time, particularly A. Church, S. C. Kleene, and E. Post,
addressed. In order to study the question, a variety of formal models of
computation were established. Prominent among them were the recursive
functions of Church and Kleene and Post systems, but there are many other such
systems that have been studied. In this chapter we briefly review some of the
ideas that arose out of these studies. There is a wealth of material here that we
cannot cover. We will give only a very brief presentation, referring the reader to
other references for detail. A quite accessible account of recursive functions and
Post systems can be found in Denning, Dennis, and Qualitz (1978), while a good
discussion of various other rewriting systems is given in Salomaa (1973) and
Salomaa (1985).
The models of computation we study here, as well as others that have been
proposed, have diverse origins. But it was eventually found that they were all
equivalent in their power to carry out computations. The spirit of this
observation is generally called Church's thesis. This thesis states that all
possible models of computation, if they are sufficiently broad, must be
equivalent. It also implies that there is an inherent limitation in this and that
there are functions that cannot be expressed in any way that gives an explicit
method for their computation. The claim is of course very closely related to
Turing's thesis, and the combined notion is sometimes called the Church-Turing
thesis. It provides a general principle for algorithmic computation and, while not
provable, gives strong evidence that no more powerful models can be found.
13.1 Recursive Functions
The concept of a function is fundamental to much of mathematics. As
summarized in Section 1.1, a function is a rule that assigns to an element of one
set, called the domain of the function, a unique value in another set, called the
range of the function. This is very broad and general and immediately raises the
question of how we can explicitly represent this association. There are many
ways in which functions can be defined. Some of them we use frequently, while
others are less common.
We are all familiar with functional notation in which we write expressions
like
f(n) = n 2 + 1.
mechanically verifiable proofs. It was this problem that Turing and other
mathematicians of the time, particularly A. Church, S. C. Kleene, and E. Post,
addressed. In order to study the question, a variety of formal models of
computation were established. Prominent among them were the recursive
functions of Church and Kleene and Post systems, but there are many other such
systems that have been studied. In this chapter we briefly review some of the
ideas that arose out of these studies. There is a wealth of material here that we
cannot cover. We will give only a very brief presentation, referring the reader to
other references for detail. A quite accessible account of recursive functions and
Post systems can be found in Denning, Dennis, and Qualitz (1978), while a good
discussion of various other rewriting systems is given in Salomaa (1973) and
Salomaa (1985).
The models of computation we study here, as well as others that have been
proposed, have diverse origins. But it was eventually found that they were all
equivalent in their power to carry out computations. The spirit of this
observation is generally called Church's thesis. This thesis states that all
possible models of computation, if they are sufficiently broad, must be
equivalent. It also implies that there is an inherent limitation in this and that
there are functions that cannot be expressed in any way that gives an explicit
method for their computation. The claim is of course very closely related to
Turing's thesis, and the combined notion is sometimes called the Church-Turing
thesis. It provides a general principle for algorithmic computation and, while not
provable, gives strong evidence that no more powerful models can be found.
13.1 Recursive Functions
The concept of a function is fundamental to much of mathematics. As
summarized in Section 1.1, a function is a rule that assigns to an element of one
set, called the domain of the function, a unique value in another set, called the
range of the function. This is very broad and general and immediately raises the
question of how we can explicitly represent this association. There are many
ways in which functions can be defined. Some of them we use frequently, while
others are less common.
We are all familiar with functional notation in which we write expressions
like
f(n) = n 2 + 1.