講演資料
講義資料スライドの表紙です。スライド画像、または下の要約文中の青いページ番号リンクをクリックすると、別のタブで無駄なノイズのない、純粋なPDFビューア画面が起動し、指定されたページへ直接ジャンプして快適に閲覧できます。
全体概要
本セミナーは、計算理論の根幹をなす「チューリングマシン」という概念的装置を出発点として、「決定性」と「非決定性」という計算モデルの本質的な違いを解き明かすことを中心テーマとしています。現代のコンピュータサイエンスが直面する最大の未解決問題のひとつである「P≠NP問題」を視野に収めながら、その問いに至るまでの基礎的な理論的装置を丁寧に構築していく講義です。
チューリングマシンは、1936年にアラン・チューリングが提唱した抽象的な計算機械であり、現代のあらゆるコンピュータの計算能力を数学的にモデル化したものです。この講義では、テープとヘッドというシンプルなメカニズムの説明から始まり [p.3]、具体的なプログラム例を通じてその動作原理を直感的に理解させた上で [p.4]〜[p.13]、通常のチューリングマシン（決定性チューリングマシン、DTM）が「一本道の実行」しか持たないという性質を明確に示します [p.14]。
その対比として登場するのが「非決定性チューリングマシン（NTM）」です。NTMは複数の遷移表（命令セット）を持ち、各ステップでどちらの命令セットを適用するかが一意に定まらないという、DTMとは根本的に異なる計算モデルです。NTMの実行は「木構造」として描かれ、その受理条件は「少なくとも一つのパスがacceptに至れば受理」という非常に寛大なものとして定義されます [p.18], [p.19]。
このNTMという概念は、計算複雑性理論における「NPクラス」の定義に直結します。NPクラスとは、NTMによって多項式時間で解ける問題のクラスであり、「解の検証は多項式時間でできるが、解の発見が困難な問題群」として現実的な意味を持ちます。本講義はそのNPクラスの理論的基盤を丁寧に積み上げることで、P問題とNP問題の違い、さらにはNP完全性という概念への道筋を準備するものです。技術史的に見ても、このテーマはCook-Levinの定理（1971年）に始まるNP完全性理論の出発点であり、現代の暗号理論や最適化問題の計算困難性の根拠ともなる普遍的な議論の土台です。
講義のロードマップ
■ Part 1: 決定性チューリングマシンの基礎
- この部の核心:
通常のチューリングマシン（DTM）のメカニズムを具体的なプログラム例とともに丁寧に解説します。テープ・ヘッド・状態遷移という三要素がどのように連動するかを直感的に示し、DTMが「一つの遷移表に従って一意に動作する」決定論的機械であることを明確にします [p.2], [p.3], [p.14]。
- 論理展開:
- テープは無限長であり、ヘッドは記号の読み取り・書き込み・移動を行う [p.3]
- 遷移表（状態×テープ記号 → 書き込み記号・移動方向・次状態）によってすべての動作が一意に決定される [p.4]
- 具体的な6状態の遷移表を用いてステップごとの動作を追跡し、「停止状態H」で計算が終了する [p.5]〜[p.13]
- DTMの実行は、開始から停止まで「一本の直線状パス」として表現できる [p.14]
■ Part 2: 非決定性チューリングマシン（NTM）の導入
- この部の核心:
DTMを拡張し、「複数の遷移表を持つ」チューリングマシンという概念を導入します。各計算ステップでどの遷移表を使うかが非決定的であるため、可能な実行全体は木構造として描かれます。この「計算の木」という視点こそが、NTMの本質を捉える鍵です [p.16], [p.17]。