Computability and Unsolvability

by Martin D. Davis

Classic text considers general theory of computability, computable functions, operations on computable functions, Turing machines self-applied, unsolvable decision problems, applications of general theory, mathematical logic, Kleene hierarchy, computable functionals, classification of unsolvable decision problems and more.

Genres: Computer Science, Mathematics, Reference, Science, Philosophy

248 pages, Paperback

First published January 1, 1958

About the author

Martin David Davis (born 1928) is Professor Emeritus at New York University's Computer Science Department.

Reviews

[Roberto Rigolin F Lopes]

We are in 1958, Davis is writing from the border between mathematics and computer science. He assumes that you know a great deal about Turing machines, Godel's numbers + incompleteness theorems, and is familiar with their original notations. Non-mathematicians like myself might get scared with the notation (e.g. while wrestling with the "arithmetization theory of Turing machines", what?!); it may even make you cry. Then he goes incrementally showing operations with computable functions, recursive functions and difficulties with decision problems. One proof after another. The cross-references among the several theorems in this book will make you behave like a Turing machine going furiously back and forth trying to "compute" this book. A great challenge indeed.

[Ben Meyers]

Fascinating but damn dense.