Abstract

This well-written introduction to the theory of recursive functions and effective computability is an English translation of the 1960 German edition. The seven chapters deal with all the usual material, beginning with a treatment of Turing machines and their relation to the intuitive idea of computability, through general recursive functions, to a chapter on such diverse topics as the hierarchy of arithmetical predicates and Fitch's basic logic system. Rather than try to cover the whole subject sketchily, the author confines himself to a narrower range of subjects which he elucidates with admirable clarity. The treatment of Turing machines is similar to that of Davis' book in using quadruples as instruction units in machine "programs," but the treatment differs in some details which might interest the connoisseur. In between technical discussions there are numerous remarks, often of more than a page in length, dealing with the more purely philosophical aspects of the theory under development. Each chapter terminates with a short bibliography. The publishers are to be congratulated for making this valuable work available to a wider range of readers.—P. J. M.