In this paper I shall discuss the prospects for a mathematical science of computation. In a mathematical science, it is possible to deduce from the basic assumptions, the important properties of the entities treated by the science. Thus, from Newton's law of gravitation and his laws of motion, one can deduce that the planetary orbits obey Kepler's laws.

What are the entities with which the science of computation deals?

What kinds of facts about these entities would we like to derive?

What are the basic assumptions from which we should start?

What important results have already been obtained? How can the mathematical science help in the solution of practical problems?

I would like to propose some partial answers to these questions. These partial answers suggest some problems for future work. First I shall give some very sketchy general answers to the questions. Then I shall present some recent results on three specific questions. Finally, I shall try to draw some conclusions about practical applications and problems for future work.

This paper should be considered together with my earlier paper [McC63]. The main results of the present paper are new but there is some overlap so that this paper would be self-contained. However some of the topics in this paper such as conditional expressions, recursive definition of functions, and proof by recursion induction are considered in much greater detail in the earlier paper.

Tue May 14 13:32:03 PDT 1996