チューリングマシン

author: 371tti

textbook, formal-science, computer-science, computability, turing-machine

チューリングマシン（Turing machine）とは、計算という行為を数学的に扱うために考えられた抽象的な計算モデルである。

現代のコンピュータそのものをそのまま表したものではない。むしろ、

「機械的な手続きで計算する」とは何か

を、できるだけ単純な部品だけで定義したモデルである。

この素朴さがかなり強い。実際、普通のプログラムで計算できるものは、原理的にはチューリングマシンでも計算できると考えられている。

構成要素

標準的なチューリングマシンは、次の部品からなる。

テープ
ヘッド
状態
遷移規則

テープ

テープは、記号を書き込めるマスが一列に並んだ記憶装置である。理論上は必要に応じて無限に伸びると考える。

各マスには、あらかじめ決められた記号集合のうち1つが入る。何も書かれていないマスには、空白記号が入っているとみなす。

現実のコンピュータのメモリは有限だが、チューリングマシンではメモリ上限を本質的な問題から切り離すため、無限のテープを仮定する。

ヘッド

ヘッドは、テープ上の1マスを指している読み書き装置である。

1ステップごとに、ヘッドは次のことを行う。

現在のマスの記号を読む
必要なら記号を書き換える
左または右へ1マス移動する
内部状態を変える

ヘッドは一度に1マスしか見ない。にもかかわらず、遷移規則を積み重ねることで複雑な計算を表現できる。

状態

状態は、機械が現在どの段階にいるかを表す有限個の内部記憶である。

たとえば、

開始状態
計算中の状態
受理状態
拒否状態

のような状態を持つ。

重要なのは、状態の数は有限であることだ。チューリングマシンの記憶能力は、有限個の状態だけでなく、無限に伸びるテープによって支えられている。

遷移規則

遷移規則は、チューリングマシンのプログラムに相当する。

現在の状態と、ヘッドが読んだ記号から、次の動作を決める。

たとえば、

現在の状態	読んだ記号	書く記号	移動	次の状態
`q0`	`1`	`1`	R	`q0`
`q0`	`_`	`1`	N	`q_accept`

のように書ける。

これは、

q0 状態で 1 を読んだら、そのまま右へ進む
q0 状態で空白を読んだら、そこに 1 を書いて受理する

という意味である。

形式的な定義

標準的な決定性チューリングマシンは、しばしば次の7つ組で定義される。

M = (Q, Σ, Γ, δ, q_{0}, q_{a c c e p t}, q_{r e j e c t})

それぞれの意味は次の通り。

$Q$ : 状態の有限集合
$Σ$ : 入力アルファベット
$Γ$ : テープアルファベット
$δ$ : 遷移関数
$q_{0}$ : 開始状態
$q_{a c c e p t}$ : 受理状態
$q_{r e j e c t}$ : 拒否状態

遷移関数 $δ$ は、現在の状態と現在読んでいる記号から、次の状態、書く記号、移動方向を返す。

δ : (Q ∖ {q_{a c c e p t}, q_{r e j e c t}}) \times Γ \to Q \times Γ \times {L, R}

移動方向には、定義によってはその場に止まる N を許すこともある。ただし、許しても許さなくても計算できる範囲は変わらない。

計算の流れ

チューリングマシンに入力を与えるとき、入力文字列をテープ上に並べ、ヘッドを先頭に置く。そして開始状態 $q_{0}$ から計算を始める。

機械は遷移規則に従って、1ステップずつ動く。

計算は、次のどれかになる。

受理状態に到達して停止する
拒否状態に到達して停止する
永遠に停止しない

この「停止しない場合がある」という点が重要である。すべての入力に対して必ず止まるとは限らない。

言語を認識する

チューリングマシンは、文字列の集合を判定する機械として扱える。この文字列集合を言語という。

あるチューリングマシン $M$ が入力 $w$ を受理するなら、 $w$ は $M$ の認識する言語に属する。

L (M) = {w ∣ M accepts w}

たとえば、

{0^{n} 1^{n} ∣ n \geq 0}

のような言語は、「0がいくつか並び、その後に同じ数だけ1が並ぶ文字列」の集合である。チューリングマシンは、このような規則を持つ文字列集合を判定するために使える。

認識可能と決定可能

チューリングマシンで扱う重要な区別として、認識可能と決定可能がある。

ある言語がチューリング認識可能であるとは、その言語に属する入力については、いつか必ず受理するチューリングマシンが存在するという意味である。

ただし、言語に属さない入力では、拒否するとは限らない。永遠に止まらないかもしれない。

一方、ある言語がチューリング決定可能であるとは、すべての入力について必ず停止し、属するなら受理、属さないなら拒否するチューリングマシンが存在するという意味である。

つまり、

認識可能: 正解ならいつか「はい」と言える
決定可能: 必ず止まって「はい」か「いいえ」を言える

という違いである。

万能チューリングマシン

万能チューリングマシンとは、他のチューリングマシンの記述と入力を受け取り、その動作をシミュレートできるチューリングマシンである。

これはかなり重要なアイデアである。

なぜなら、「機械そのものをデータとして扱う」ことができるからである。

現代のコンピュータで、プログラムをファイルとして保存し、別のプログラムがそれを読み込んで実行できるのも、この考え方と深く関係している。

万能チューリングマシンは、ソフトウェア、インタプリタ、コンパイラ、仮想マシンといった概念の理論的な祖先と見なせる。

停止性問題との関係

チューリングマシンは、計算できるものを定義するだけでなく、計算できないものを示すためにも使われる。

代表例が停止性問題である。

停止性問題とは、

任意のチューリングマシン $M$ と入力 $w$ が与えられたとき、 $M$ が $w$ 上で停止するかどうかを判定できるか

という問題である。

この問題は決定不可能である。

つまり、どんなチューリングマシンについても、その停止・非停止を必ず正しく判定する万能な判定器は存在しない。

これは単に「実装が難しい」という話ではない。理論的に不可能である、という話である。

現実のコンピュータとの違い

チューリングマシンは現実のコンピュータではない。

主な違いは次の通り。

テープが無限である
1ステップが極端に単純である
入出力やOSのような現実的な仕組みを持たない
計算時間やメモリ階層などを直接扱わない

それでも、計算可能性を考える上では十分に強い。

現実のコンピュータは有限メモリしか持たないが、理論上の計算モデルとしては、チューリングマシンは「アルゴリズムで計算できるもの」の範囲をうまく捉えている。

まとめ

チューリングマシンは、非常に単純な部品だけで構成された抽象機械である。

しかし、その単純な機械によって、

アルゴリズムとは何か
計算できるとは何か
決定できる問題とできない問題の境界はどこか
プログラムをデータとして扱うとはどういうことか

を厳密に考えられるようになった。

計算可能性理論において、チューリングマシンはただの古典的なモデルではなく、「計算」という概念そのものを測るための基準である。