セミナー紹介

全体概要

本セミナー「チューリングマシンを学ぼう！」は、2021年1月29日に開催されたマルレク基礎シリーズの一講義です。コンピュータ・サイエンスの根本的な問いである「計算とは何か」を探求するために、その理論的基盤を構成するチューリングマシンを取り上げています [p.2]。

チューリングマシンは、テープの上をヘッドが左右に移動しながら文字を読み書きするという、極めて単純なモデルです。しかしこの単純さこそが本質であり、現代のあらゆるコンピュータと「計算能力」において同等であることが知られています。講師は初学者を念頭に置きつつ、同時に過去にこのテーマを学んだことのある方にも知識の再整理として役立てることを目指しています [p.2]。

セミナーは三部構成をとっています。第一部では「テープ」と「ヘッド」という物理的部品の機能解説から始まり、チューリングマシンの最重要概念である「状態」と「状態の遷移」の仕組みを丁寧に展開します [p.3]。第二部ではいよいよプログラミングに踏み込み、命令の表記法を導入したうえで、文字列の長さの計算、偶奇判定、文字列コピーといった具体的なプログラム例を通じて、変数も配列も関数もないプリミティブな計算モデルが日常のプログラミングと本質的に同じものであることを示します [p.4]。第三部では複数のテープを持つ拡張モデルへと議論を広げ、さらに複数のチューリングマシンが協調動作する様子、コントローラとエグゼキュータによる1ステップ実行制御という発展的テーマを扱います [p.5]。

本セミナーで扱いきれなかった「計算可能性」「計算複雑性」との深い繋がりは後日の「マルゼミ」に委ねられており、本セミナーはその前提となる強固な直観と技術的基礎を構築することを目的としています [p.5]。Interactive Proofを初めて定式化したGoldwasserらの論文図は、複数のチューリングマシンと複数のテープが現実の理論研究においてどのように用いられるかを示す具体例として冒頭に紹介されており [p.6]、抽象的なモデルが最先端の計算理論に直結していることを示す好例となっています。

講義のロードマップ

■ Part I: チューリングマシンの基礎

• この部の核心:

チューリングマシンの「テープ」と「ヘッド」という二つの物理的部品がどのように機能するかを視覚的に理解させ、続いて「状態」と「状態の遷移」という概念的核心へと誘導します。ヘッドが文字を読み書きしながらテープ上を移動するにつれ、マシンの状態が変化していくという動作イメージを確立することが、この部の最重要目標です [p.9]。

• 論理展開:
• テープはマス目で区切られた無限長の帯であり、各マスには一文字が記される。文字のないマスは空白記号「␣」（Blank）で表現される [p.12], [p.19]。
• ヘッドは現在位置のマスの文字を読み取り（Read）、新たな文字を書き込み（Write）、右（R）または左（L）に一マス移動する能力を持つ [p.22], [p.52]。
• チューリングマシンは「状態」を持ち、マシンの現在状態とヘッド位置の文字の組み合わせによって次の動作が一意に決まる。状態の名称は `A`、`q0`、`Hey` など任意の文字列でよい [p.65], [p.72]。
• 状態遷移のサンプルでは、ヘッドが `10101` 上を移動するにつれて `A→B→C→D→E→B→A→HALT` と状態が変化する様子が図示される。`HALT` はマシンを停止させる特殊状態である [p.96], [p.104]。

■ Part II: チューリングマシンをプログラムする

• この部の核心:

チューリングマシンの「命令」を5要素の組（現在状態・読み文字・書き文字・移動方向・次状態）として定式化し、文字列表記 `State Read→Write:Direction NextState` を導入します。この記法のもとで具体的なプログラムを記述し、チューリングマシンが現実の計算問題を解決できることを実証します [p.112], [p.128]。

• 論理展開:
• 命令の文字列表記として `A0→1:RA` が導入される。「状態Aでヘッドが0の上にあるなら、1を書き込み、右へ進み、状態をAにする」という意味を持つ [p.128]。命令セット全体がプログラムに相当し、マシンの振る舞いを完全に規定する [p.130]。
• 例1（文字列の長さ）：`Scan 0→1:R Scan`、`Scan 1→1:R Scan`、`Scan ␣→␣:N Halt` の3命令のみで実現。結果は1の個数による「一進数」として表現される [p.160], [p.161]。
• 例2（偶奇判定）：`Even`/`Odd` という2状態を用いてパリティを追跡し、`Print_Even`/`Print_Odd` 状態で結果を出力する8命令のプログラム [p.167]。
• 例3（文字列コピー）：`Fetch`/`Copy0`/`Copy1`/`Mark0`/`Mark1`/`Back0`/`Back1` という状態群を用い、マーキングと後退を繰り返すことで複数文字のコピーを実現する [p.173], [p.176]。

■ Part III: 複数のテープと複数のマシン

• この部の核心:

命令の表記を `(n)State Read→Write:Direction (m)State'` へ拡張することで複数テープを自然に扱えるようにします。さらに二台のチューリングマシンを「並列（M1⊗M2）」または「直列（M1∘M2）」に組み合わせる理論を展開し、最後にControllerとExecuterの役割分担による1ステップ実行制御という高度なアーキテクチャを構築します [p.180], [p.187]。

• 論理展開:
• テープ1のビット列をテープ2にコピーするプログラムでは、`(1)Copy` 状態が `(2)Paste0`/`(2)Paste1` 状態に制御を渡し、テープ2への書き込み後にテープ1へ制御を返すという「テープ間の制御の往復」が核心となる [p.188], [p.216]。
• 二台のマシンの合成では、直列合成 `M1∘M2` において `[M1∘M2] = [M1]*∪*[M2]` という命令セットの書き換え・結合規則が定義される。M1の終了状態をM2の初期状態に書き換えることが鍵である [p.227]。
• Controller/Executer モデルでは、実行マシンMの命令「次の状態」をすべてコントローラの新状態 `(Contr)Si` に書き換え、コントローラ側に対応する `(Contr)Si 1→1:N (m)S'` 命令を追加することで、制御の往復を実現する [p.232], [p.233], [p.240]。
• 一時停止機構では、`^S 1→1:N S`（停止解除）と `^S 0→0:N ^S`（停止継続）をコントローラに追加し、コントローラのヘッド位置の文字（1または0）によってステップ実行のオン・オフを外部から制御できる [p.242], [p.245]。