「チューリングの計算理論入門」を読んだ

「チューリングの計算理論入門」を読んだ。 チューリングマシンってどんなだっけ?と思って、手に取った本。 シャノンの情報理論入門の著者と同じで、本の位置付けも入門で同じ。 チューリングについて語る前に、その頃の時代背景の説明や関係しそうなしなさそうな人物の紹介などについて述べて、その後チューリングの話に入るという展開。 チューリングマシンというものは、そもそも物理的な機械でなくて、数学的な理論の実装機械というものであり、その説明のために時代背景やチューリングが達成したかった数学的課題を説明している。そして、チューリングマシンは数学的な基礎だけでなく、現代のコンピュータの基礎としての位置付けとなった。

チューリングマシンとは、無限長のテープ(記憶装置)と状態を持った機械であり、状態遷移とテープの読み書きのルールを定義することであらゆるアルゴリズムを実行できるものです。