Fifty years of computability
type: Item
instance of: scholarly article
title: Fifty years of computability
zbMATH Open document ID: 0712.03028
author: John N. Crossley
published in: Southeast Asian Bulletin of Mathematics
publication date: 1988-01-01T00:00:00Z
review text: 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 …
Mathematics Subject Classification ID: 03Dxx
Mathematics Subject Classification ID: 01A60
Mathematics Subject Classification ID: 03-01
Mathematics Subject Classification ID: 03-03
zbMATH DE Number: 4170886
zbMATH Keywords: historical account of recursive function theory
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 4170886