コラム: チューリング機械の食べ歩き

概要

みなさんはチューリング機械の定義を何も見ずに書けますか？私は（少なくともこれを書いている時点では）ちょっと怪しいです。 Cook-Levinの定理の証明を学んだことがある人は「テープと状態があって、テープにはヘッドがあって左右に動いていって最終的には受理状態か拒否状態に落ち着く」ぐらいな粒度で覚えていると思いますが、少なくともチューリング機械そのものを真面目に研究で扱うとかでない限りは、大体それぐらいの認識で事足ります。多項式時間で停止するかどうかはワードRAMモデルと等価である（Cobham–Edmondsのテーゼ）が大事なわけであって、多くの教科書に書いてあるように実際にチューリング機械によってアルゴリズムを記述して議論をするのは苦痛以外の何者でもありません。Cook–Levinの定理を厳密に証明する講義とかだと厳密な計算機の定義を与えないと

ですが、計算の理論や計算量理論の講義をしようとすると、チューリング機械の定義は避けては通れません。 従って、こういった内容の講義をする世界中の先生はまず最初にチューリング機械をどう定義するか、現実にPythonなどで記述されるアルゴリズムとの整合性をどう説明するか、でかなり悩んだはずです。 私もその機会があり、先人たちがどのようにチューリング機械を定義したか、そして講義ではどのような粒度で扱うかを色々調べたので、まとめて紹介したいと思います。

今回の調査で調べたのは以下の本と講義資料です。講義資料に関してはネットで講義ノートが公開されているものに限定して定義を確認しました。

こうして一つ一つ講義ノートを見るとみなさん本当にすごい講義資料を作成されてて圧倒されますね。。。実は上にあげた講義資料の多くはチューリング機械のフォーマルな定義そのものは有名な教科書に丸投げしていて、講義ノート自体には厳密な定義ではなく、チューリング機械の構成や計算過程の大まかな説明にとどめる、という構成が非常に多かったです。

そもそもチューリング機械の概念自体は一つしか存在しないので、普通に考えれば定義は唯一のはずなので、いろんな資料を漁る必要がないんじゃないかと思われるかもしれません。 しかし、その講義や本が何を目的としてチューリング機械を考えているのか、に応じて定義の細かい部分の実装は様々に異なってきます。この記事では計算量理論におけるチューリング機械の定義の細かい差分について見ていこう、というわけです。ただ、結論から言うとどの定義も本質的には同じであり、細かい部分のチューニングは自分のやりたい講義にとって扱いやすいものを採用する、というだけの話です。

基本の定義

大体の書籍や講義資料に載っているチューリング機械の定義を私の個人的な主観で平均化すると以下のような感じになります：

定義1.

（1テープ）チューリング機械とは六つ組 $M = (Q,\Sigma,\delta,q_0,q_{\mathrm{accept}}, q_{\mathrm{reject}})$ であって、以下の構成要素からなる：

  • $\Sigma$はアルファベットと呼ばれる有限集合であり、「空白」を意味する特別な記号 $\Box$ および$0,1$を含む。
  • $Q$は有限集合であり、$Q$の各元を状態と呼ぶ。
  • $q_0,q_{\mathrm{accept}},q_{\mathrm{reject}}\in Q$はそれぞれ初期状態、受理状態と拒否状態と呼び、それぞれ相異なる状態である。
  • $\delta\colon Q\times \Sigma \to Q \times \Sigma \times \set{\leftarrow,\circlearrowright,\rightarrow}$は遷移関数

チューリング機械は仮想的にテープと呼ばれる特殊な構造を持っています。テープとは横一列に並んだ加算無限個のマスの連なりで、現実のコンピュータにおけるメモリに相当するものです。各マスには$0,1,2,\dots$のような番号で添字づけられています。テープの各マスには一文字を記入したり、またはそこに書かれている一文字を読み取ることができます。 このマスに記入されうる文字の集合が$\Sigma$で指定されています。特殊文字$\Box$は、そのマスが空白であることを意味します。初期時点ではまず入力がその長さと等しい個数のマスに一文字ずつ記載されており、残りのマスは全て空白$\Box$で埋められています。計算量理論ではほとんどの場合、$\Sigma=\set{0,1,\Box}$です。

また、チューリング機械は自身の状態を記憶しておくことができます。現実のコンピュータにおけるレジスタに相当する概念であり、例えば自身が停止しているか、などを記憶します。集合$Q$はチューリング機械がとりうる状態の集合を意味します。特に$q_0$は初期状態を意味し、状態$q_{\mathrm{accept}}$に入ったら入力を受理して停止、状態$q_{\mathrm{reject}}$に入ったら入力を拒否して停止します。このときの受理/拒否がチューリング機械の出力(Yes/No)に対応するというわけです。

テープの読み書きはヘッドと呼ばれる仮想的な装置を経由して実行され、各テープには一つのヘッドが付随しています。初期状態では$0$番のマスにヘッドが配置されており、各時刻で一マス左右どちらかに移動するか、もしくはステイします。ただし、$0$番のマスにいるときはそこから左に移動できないものとします。

チューリング機械は複数のステップで計算を行なっていき、（停止するものは）最終的に受理状態または拒否状態に至って停止します。各ステップは遷移関数 $\delta$ によって定まります。 具体的には、現在の状態が$q\in Q$、現在のヘッドが置かれているマスに記入されている文字が $\sigma\in \Sigma$であるときに

\[(q',\sigma',d) = \delta(q,\sigma)\]

であったとしましょう。このとき、次のステップ開始時における機械の状態は $q’$ とし、テープが置かれているマスの文字を $\sigma$ から $\sigma’$ に変更し、最後に $d\in\set{\leftarrow,\circlearrowright,\rightarrow}$ に応じてヘッドの位置を調整します（$d=\leftarrow$なら一つ左に、$d=\rightarrow$なら一つ右に、そして $d=\circlearrowright$ならテープの位置はそのままにする）。

定義1だけ眺めるとチューリング機械はYes/Noしか出力しないように見えますが、複数ビットの情報を出力したい場合が多々あります。例えばカープ帰着を定義するには多項式時間で計算可能な関数を考える必要があります。 これは簡単に解決できて、チューリング機械が終了した時点でのテープの中身をそのチューリング機械の出力とみなします。

ここからは、それぞれの書籍や講義資料で特徴的なポイントを簡潔に紹介していきます。

Sipser本の定義

実はSipser本の定義（Definition 3.3）は基本の定義で紹介した定義1とほぼ同じです。 具体的には、チューリング機械を $M = (Q,\Sigma,\Gamma,\delta,q_0,q_{\mathrm{accept}},q_{\mathrm{reject}})$ と定義しており、定義1との違いはアルファベットの扱い（$\Sigma$と$\Gamma$）とヘッドが可能な移動だけです。

  • $\Sigma$は空白記号 $\Box$ を含まない、入力文字列のアルファベット（つまりチューリング機械が受け取るのは $\Sigma^*$ の元）
  • $\Gamma$はテープのマスに記載されうる文字の集合で、$\Sigma\subseteq \Gamma$ かつ $\Box\in\Gamma$ を満たす。
  • また、定義1ではヘッドは$\set{\leftarrow,\circlearrowright,\rightarrow}$が許されていましたが、Sipser本の定義では$\set{\leftarrow,\rightarrow}$のみだった。これらの違いは瑣末なものであり、互いに変換できることをSection 3.2で述べています。

つまり、入力として受け取る文字列のアルファベットとテープ内で操作する文字のアルファベットを区別しているわけです。 定義1の流儀では入力は$(\Sigma\setminus\set{\Box})^*$の元という想定でしたので、これを別の記号で書きたかった、という感じでしょうか。

付け足すとその後の節では瑣末な定義の違いで性質はほとんど変わらない（ロバスト性）について言及してありましたので、私のように細かな定義の違いが気になる人はこれを参考にするのが良いかもしれません。

また、この本は計算の理論を俯瞰するため、オートマトンや形式言語など非常に基礎的なパートも含んでいるため、チューリング機械で「計算する」というよりはチューリング機械で「決定する(decide)」という言い回しがよく使われています。そのためチューリング機械を定義する章では複数ビットを出力するチューリング機械を考えることはありませんが、NP完全性の定義を与える章では、停止時のテープの中身をチューリング機械の出力とみなす旨の記載（定義7.28）がなされています。

Goldreich本の定義

驚くことにGoldreich本では定義1のようなフォーマルな定義はSipser本に譲っていて、定義というよりかは記号を使ってチューリング機械の説明を与えていました。 さらにこの本を使って講義を行う先生向けへのアドバイスとして

チューリング機械を使ってアルゴリズムを議論するのは百害あって一理なし（意訳）

みたいなことまで言っています。ただ、チューリング機械の説明自体は以下のようになされていました：

  • アルファベット $\Sigma$ は$0,1,\Box$を含む
  • テープの左端（0番のマス）にヘッドがいるときに左に進んだら、機械は停止するとみなす。
  • 機械が停止したとき、テープに記載されている文字列から空白文字を削除したものを、その機械の出力とみなす。

Sipser本では判定問題を重要視している一方でGoldreich本では最初から探索問題を判定問題と同列に定義し、NPの定義とFNPの定義を同じ節で与えていることから、最初から多ビット出力のチューリング機械を考えたかったのかもしれません。

Papadimitriou本の定義

Papadimitriouの本ではSection 2.1でチューリング機械の定義を与えています。特徴的なのはアルファベット集合$\Sigma$に空白文字$\Box$以外の特殊文字として、テープの先頭を意味する文字 $\triangleright$ を含む点でしょうか。この文字を定義しておくことによって、ヘッドがテープの行頭にいるかどうかを機械は知ることができる、というわけです。 例えばこの文字を導入しておくと、多テープのチューリング機械を単一テープでシミュレートするとき、複数テープの中身をそれぞれ一つのテープに記入して、それらを特殊記号$\triangleright$で区切る、みたいなことができて便利になるという感じでしょうか。

Garey-Johnson本の定義

この本はSection 2.2でチューリング機械の定義を与えていますが、実は一つだけかなり独特なポイントがあります。この本で定義したチューリング機械は、無限に左右に伸びたテープを考えており、各マスは$\mathbb{Z}$で添字づけられています。これ以外の部分は定義1と同様です。

おそらく単に「テープの先頭にヘッドがきた時に左に遷移する」という特殊ケースを排除したいというだけであり、特別な深い理由はないと思われます。

Arora-Barak本の定義

この本の定義はかなり特殊で、そもそもチューリング機械は二つ以上のテープを持つものとして定義しています。 中でも二つのテープを特別視しており、それぞれ

  • 入力テープ：読み込みのみが可能であり、入力を表す文字列が記載されており、それに続くマスは全て空白記号で埋められている。
  • 出力テープ：読み書きが自由であり、最終的には出力を記載するためのテープ
  • 作業テープ：入力と出力以外のテープで、読み書きは自由

を考えます。さらに受理状態と拒否状態の概念がなく、代わりに停止状態 $q_{\mathrm{halt}}$ の概念を導入しています。つまり、チューリング機械には受理／拒否の概念はなく、代わりに出力テープの中身が$1$か$0$かで判別するようにしているわけです。

想像ですが、おそらくこのような定義している背景にはArora-Barak本で空間計算量を扱う章があり、そこで対数領域アルゴリズムなどを議論する際、単一テープだと領域計算量をどう定義するのかが難しくなり、これを単純にするためにあえて入出力や作業テープを分離したのだと思われます。

講義資料におけるチューリング機械の扱い

冒頭でも述べましたが、上にあげた講義資料のほとんどは、チューリング機械は既知としているか、もしくは簡単な説明にとどめて形式的な定義は書籍に譲るに留めていました。体感としてはArora-Barak本の定義を採用しているものが最も多かった気がします。

最も印象に残ったものとしてDieter van Melkebeekの講義資料をあげておきます。 この講義資料では複数テープチューリング機械の形式的な定義を与えた上にランダムアクセスチューリング機械の定義も与えています。

以下にそれぞれの講義でどのようにチューリング機械を定義したかをまとめています：

講義定義
Trevisan (2002)定義しない（既知とする）
Cai (2003)$(Q,\Sigma,q_0,\delta,F)$ ($F\subseteq Q$は受理状態の集合)
O’Donnell (2013)informalな定義
van Melkebeek (2011)$(Q,\Sigma,\Gamma,q_{\mathrm{start}},q_{\mathrm{halt}},\delta)$
Aspnes (2020)$\langle \Gamma,Q,\delta\rangle$ (Arora-Barak本とほぼ同じ)
Svensson (2018)$(\Gamma,\mathcal{Q},\delta)$ (Arora-Barak本と同じ)
Montanaro (2012)$(\Sigma,K,\delta)$ (Arora-Barak本と同じ)

まとめ

本記事では、計算量理論におけるチューリング機械の定義について、複数の著名な教科書と講義資料を調査し、それぞれの定義の特徴を比較・紹介しました。基本的な定義はどの資料でも本質的に同じですが、アルファベットの扱い（入力アルファベットとテープアルファベットの区別）、テープの構造（片方向無限か両方向無限か）、ヘッドの移動（ステイ動作の有無）、複数テープの扱い（単一テープか複数テープか、入出力テープの分離）など、様々な差異があることが確認できました。 もちろん、理論上はこれらの違いは計算能力や計算量の評価にはほとんど影響しないのですが、やはり「分野全体の標準的な定義」をある程度は把握しておくのは、講義をする側になったり本を執筆するとき役立つと思ったので、記録として残しておくことにしました。

他にも独特な定義をご存知の方がいれば、こっそり教えていただけると幸いです。