scientific article; zbMATH DE number 225477

From MaRDI portal
Publication:5286632





The book is intended for use as a textbook for introduction courses covering Computability Theory. The course is taught to Computer Science students nor for mathematicians. And this is the main advantage of the book in contrast to many other ones in this field. The presentation is quite informal preserving, however, the elegance of mathematical proofs. The book introduces basic models of computation: Turing machines, Post machines, unlimited register machines, Markov algorithms, nondeterministic and probabilistic Turing machines. Subjects covered include: universality, undecidability, Post Correspondence Problem (including the matrix mortality problem) and basic facts from the Recursive Function Theory such as \(s\)-\(m\)-\(n\) and Rice theorems. The last three sections present an informal look to Gödel's Incompleteness Theorem and the Church-Turing hypothesis. Computer Science students would find this book as an elegant and informal introduction to basic facts of the Computability Theory.




Cited in
(35)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5286632)