つーか突っ込む前にお前等が教えてやれよ

コンピュータ基礎理論ハンドブック (1)
http://www.amazon.co.jp/exec/obidos/ASIN/4621039210/
Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity
http://www.amazon.com/exec/obidos/tg/detail/-/0262220385/

↓も面白い。(歴史的な解説あり)
守屋悦朗
チューリングマシンと計算量の理論
http://www.amazon.co.jp/exec/obidos/ASIN/4563014923/