Fifty years of computability (Q923077)

The author gives a brief historical account of recursive function theory. Most of the topics mentioned are well known to mathematical logicians. Included in the discussion are: the elementary theory of recursive functions and recursively enumerable sets, the priority argument, some examples of higher-order recursion theory (e.g., Kleene functionals of higher type, \(\alpha\)-recursion theory and the work of Kechris and Moschovakis), effective algebra, effective analysis and polynomial time computability. A nice aspect of this work is the inclusion of historical material not often found in brief accounts. For example, the author discusses the origin of the word ``algorithm'' and its relation to the Hindu-Arabic numerals. Also included are some remarks on the role of algorithms in Chinese mathematics. As may be expected, however, most of the material in this paper is concerned with more recent work. The bibliography contains papers devoted to reminiscences and other historical matters, as well as to research. In general, this material is very familiar to logicians. A possible exception is \textit{W. F. Aspray}'s Ph. D. thesis [``From mathematical constructivity to computer science: Alan Turing, John von Neumann, and the origins of computer science in mathematical logic'', Univ. Wisconsin, Madison, WI, 1980]. In the epilogue, the author reminds us that the advent of the computer ``has revitalized the search for computable solutions''. He concludes that ``we should be teaching our students more discrete mathematics, and a little less nonconstructive analysis''. The reviewer agrees only partly with this viewpoint. Certainly our students should learn more discrete mathematics. But they should also learn analysis. For analysis - with the help of the computer - is used today to solve problems in engineering and science. Besides, the history of mathematics tells us that there are mathematical results, originally obtained without regard to usefulness, which have unexpectedly found application at a later date.