Michael Sipser (2005)
Introduction to the Theory of Computation
PWS, 2. ed.
Aus Sicht eines Theoretikers eine der besten Einführungen in die theoretische Informatik. Es verwendet in der abstrakten Berechenbarkeitstheorie allerdings eine Notation, die unserer Erfahrung nach nicht sehr intuitiv ist. Leider ist es in Deutschland recht teuer, aber vielleicht gebraucht zu bekommen (die erste Auflage von 1997 ist übrigens fast identisch).
