Turing's famous 1936 paper introduced a formal definition of a computing machine, a Turing machine. This model led to both the development of actual computers and to computability theory, the study of what machines can and cannot compute. This book presents classical computability theory from Turing and Post to current results and methods, and their use in studying the information content of algebraic structures, models, and their relation to Peano arithmetic. The author presents the subject as an art to be practiced, and an art in the aesthetic sense of inherent beauty which all...
Turing's famous 1936 paper introduced a formal definition of a computing machine, a Turing machine. This model led to both the development of actua...
...The book, written by one of the main researchers on the field, gives a complete account of the theory of r.e. degrees...The definitions, results and proofs are always clearly motivated and explained before the formal presentation; the proofs are described with remarkable clarity and conciseness. The book is highly recommended to everyone interested in logic. It also provides a useful background to computer scientists, in particular to theoretical computer scientists. Acta Scientiarum Mathematicarum, Ungarn 1988 ...The main purpose of this book is to introduce the reader to the main results...
...The book, written by one of the main researchers on the field, gives a complete account of the theory of r.e. degrees...The definitions, results an...
