講演資料
講義資料スライドの表紙です。上のスライド画像をクリックすると、同じ画面のまま全編の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]。
■ Part 2: 非決定性チューリングマシン（NTM）の導入
DTMを拡張し、「複数の遷移表を持つ」チューリングマシンという概念を導入します。各計算ステップでどの遷移表を使うかが非決定的であるため、可能な実行全体は木構造として描かれます。この「計算の木」という視点こそが、NTMの本質を捉える鍵です [p.16, p.17]。
ページのナビゲート