書記の読書記録#43「チューリングの計算理論入門」

高岡詠子「チューリングの計算理論入門」のレビューと読書記録

チューリングの計算理論入門　チューリング・マシンからコンピュータへ (ブルーバックス)

レビュー

計算理論の根幹とも言えるチューリングマシンとその周辺の話題について軽くさらったような本。初心者向け。

読書記録

＃ 1p10〜103
・基本構造：順次，分岐，反復・判断や予測・アルゴリズム・計算機の歴史：パスカリーヌ，バベッジの「階差機関「解析機関」・決定問題・チューリングマシン：アルゴリズムを表す理論的な計算モデル・万能チューリングマシン・オートマトン：状態と入力による判断・チャーチ=チューリングの提唱

＃ 2p106〜218
・計算可能=アルゴリズムで記述できる・停止性判定チューリングマシンは作れない・万能チューリングマシン・関数，引数・計算量，オーダー・多項式時間計算可能なクラス（クラスP）・NP問題・P=NP問題・NP完全，NP困難・ブール代数，論理演算

本記事のもくじはこちら：

書記の読書記録まとめ｜Writer_Rinka｜note