チューリングマシン

コンピュータサイエンスの基礎概念

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

オートマトンからチューリングマシンへ

  • 有限オートマトン: 記憶は有限。正規言語を扱う。
  • プッシュダウンオートマトン: スタック記憶。文脈自由言語を扱う。
  • チューリングマシン: 無限テープで実質無限の記憶。計算可能な問題をすべて解ける。

アラン・チューリングのイラスト

コンピュータサイエンスの基礎概念

チューリングマシンとは

チューリングマシンの動作図

チューリングマシン

  • 無限テープをもつ抽象機械。
  • 記号を読み書きする。
  • 任意のアルゴリズムを模擬できる。
コンピュータサイエンスの基礎概念

アナロジーで理解するチューリングマシン

チューリングマシンの比喩として、レシピで料理する台所のイラスト

台所と料理人＝チューリングマシン

  • 調理台がテープ。
  • 台の区画がセル。
  • 材料が記号。
  • 料理人はヘッドで、読む・書く。
  • レシピ本は工程を導くプログラム。
コンピュータサイエンスの基礎概念

チューリングマシンが重要な理由

チューリングマシンと計算可能性

  • あらゆるアルゴリズムを模擬できる
  • コンピュータが解ける限界を定義する
  • 停止性問題などの「決定不能問題」を導入
  • 計算機科学理論の基盤を築いた
コンピュータサイエンスの基礎概念

停止性問題

  • 問い: ある入力でプログラムが停止するか、永遠に走るかを予測できるか？
  • チューリングの洞察: すべてのプログラムに通用する万能な判定アルゴリズムは存在しない。
  • 結果: 停止性問題は決定不能。一部の問題にはアルゴリズム解がない。
  • 含意: 計算の限界は暗号・AIに影響する

停止性問題を示す図

コンピュータサイエンスの基礎概念

練習しましょう！

コンピュータサイエンスの基礎概念

Preparing Video For Download...