I need help with finding literature about Turing machine and undecidability. First book I was suggested is Introduction to Automata Theory, Languages, and Computation by Hopcroft, Motwani and Ullman. I also found some notes (from different courses) about this topic online, but not books that have something specific about this. Any suggestions?
2026-04-02 15:32:36.1775143956
On
Books about Turing machines and undecidability
2.4k Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
2
There are 2 best solutions below
1
On
A short wonderful (cheap) exposition can be found in the Dover book "Computability and Unsolvability" by Martin Davis. http://www.amazon.com/Computability-Unsolvability-Prof-Martin-Davis/dp/0486614719
The previous book is a famous and classic one. Let me add one other tittle which I really like (it is a complementary one, it should not be used as a main book to understand these topics) and it is not so well-known: "Cornerstones of undecidability" by G. Rozenberg and A. Salomaa. http://www.amazon.com/Cornerstones-Undecidability-Prentice-International-Computer/dp/0132974258
Hopcroft is pretty much a standard book for Automata Theory and Formal Languages. It's pretty good.
Michael Sipser's Theory of Computation will be good for Automata Theory as well. It's a little easier than Hopcroft.
If you're dealing with Turing Machines, Undecidability, and NP generally, you will find Computers and Intractability by Garey and Johnson useful as well.