チューリングマシンの定義とそれに関連する話

冒頭でも述べた通り，チューリングマシンは次の6つの要素の組として定義されます： $$(Q, \Sigma, \delta, q_0, q_{\mathrm{acc}}, q_{\mathrm{rej}})$$ ただし， $$\begin{aligned} &Q \cdots \text{状態の有限集合}\\ &\Sigma \cdots \text{アルファベット（テープに書かれる文字の集合）}\\ &q_0(\in Q) \cdots \text{初期状態}\\ &q_{\mathrm{acc}}(\in Q) \cdots \text{受理状態（必ず1つ）}\\ &q_{\mathrm{rej}}(\in Q) \cdots \text{拒否状態} \end{aligned}$$ また，$\delta$ は遷移関数と呼ばれる以下のような関数です： $$\delta : Q \times (\Sigma \cup \{\sharp\}) \to Q \times \Sigma \times \{L,R\}$$ チューリングマシンは，自分の「状況」を持っています。遷移関数は，「状況」を更新していくときに利用されます。

チューリングマシンは大雑把には，ある文字列を入力として受け付け，出力として「受理状態に入って停止」または「拒否状態に入って停止」を吐き出す部分関数，と言えます。部分関数と表現したのは，無限に実行が続き，停止せずに出力が帰ってこないこともあるためです。

テープについて

チューリングマシンは，記憶装置として「テープ」と呼ばれる装置を持ちます。テープは「セル」に分かれており，各セルにはアドレスが付されています。各セルにはアルファベット $\Sigma$ に含まれる文字の中の1文字を記録できます。文字が書かれていないことを，形式的に「$\sharp$」で表します（$\sharp \notin \Sigma$）。セルは仮想的に無限個あるとします。ただ，実際に実行の際に使われるのは有限個のセルであり，上限がないという意味での「無限個」です。また，テープには，「ヘッド」と呼ばれる構造があり，ヘッドはその位置のセルに書いてある文字を読んだり，書き換えたりすることができます。ヘッドは遷移関数により左右に動かすことができます。

チューリングマシンは自分の「状況」を持っています。本来であれば状態と言いたいところですが，$Q$ の元にすでに状態という名前が使われており紛らわしいので，状況という言葉を使っています。状況 $\gamma$ は次の3つの要素から成り立ちます： $$\gamma = (q, w, i)$$ $$\begin{aligned} q &\cdots \text{状態（$Q$ の元）}\\ w &\cdots \text{テープ上の文字列}\\ i &\cdots \text{ヘッド位置のアドレス} \end{aligned}$$

チューリングマシンの「実行」は，次のような状況の列のことを指します： $$\gamma_0 \quad \gamma_1 \quad \gamma_2 \quad \gamma_3 \quad \cdots$$ ここで，$\gamma_0$ は「初期状況」とよばれるものであり，これは以下のように定まっています： $$\gamma_0 = (q_0, w_0, 0)$$ $w_0$ は「入力文字列」を表します。初期状況を表すテープは次の図のようになります：

また，初期状況と遷移関数 $\delta$ によって，$\gamma_1, \gamma_2, \cdots$ は自動的に決まっていきます。例として，$\gamma_i$ から $\gamma_{i+1}$ の1ステップを計算してみます。 $$\gamma_i = (q, w, a_i)$$ とします。また，ヘッドの位置の文字を $c$ とします。遷移関数として， $$\delta (q, c) = (\tilde{q}, \tilde{c}, L)$$ なるものが与えられているとすると， $$\gamma_{i+1} = (\tilde{q}, v, a_i-1)$$ ここで，$v$ とは，$w$ のアドレス $a_i$ の文字を $\tilde{c}$ で上書きしてできる文字列のことです。

実行（状況の列）については，有限である場合，無限である場合のどちらもあります。チューリングマシンは，状況が $$\gamma_n = (q_{\mathrm{acc}}, \cdots, \cdots)$$ となったらチューリングマシンは「受理」という結果を返して能動的に停止します（文字列，アドレスはなんでも良い）。また， $$\gamma_n = (q_{\mathrm{rej}}, \cdots, \cdots)$$ となったらチューリングマシンは「拒否」という結果を返して能動的に停止します。これらの場合に実行は有限となります。このような状況に到達しなければ，チューリングマシンは永遠に稼働し続け，実行は無限となります。

チューリングマシンが認識する「言語」

チューリングマシンが認識する言語 $L(M)$ とは， $$L(M) := \left\{ w_o \in \Sigma^\ast \mid M \text{は} w_0 \text{を受理する} \right\}$$ と定義されます。ここで，$\Sigma^\ast$ は $\Sigma$ 内の文字を使って形成できる全ての文字列からなる集合です。

決定可能性の定義

言語 $L$ が「決定可能」であるとは，あるチューリングマシン $M$ が存在して， $$\begin{cases} w \in L \iff M\text{が} w \text{を受理}\\ w \notin L \iff M \text{が} w \text{を拒否} \end{cases}$$ を満たすこと $\cdots(\ast)$ を言います。どんな言語もそうなんじゃないの？と思った方もいるかもしれません。ただ，$w \notin L(M)$ のときには，次の2つの可能性があることに注意してください：

• $M$ が $w$ を拒否する場合
• 無限に実行が続く場合

ですから，特に，$M$ はどんな入力文字列 $w$ に対しても停止しなければ，$(\ast)$ を満たすとは言えないということです。

定義の妥当性

もし全ての言語が決定可能であれば，簡単に言えば 「全ての問題は有限時間でYes/Noを決定できる」 ということですから，人類にとってこれ以上に嬉しいことはありません。ただ，世界はそう甘くありませんでした。Turingは「全ての言語は決定可能か？」という問に対して，「万能チューリングマシン」という最強のチューリングマシンを仮想的に用意して，対角線論法的な証明を作り上げて，“No.” であることを示してしまいました。つまり，世の中には，YesかNoかをアルゴリズムで決定できない問題があるということが示された のです。

決定可能性は，チューリングマシンに依存して定義されるものであり，チューリングマシンとは別の計算のモデルを用意して，そのモデルで決定可能性を定義したらどうなるだろうか，という研究も行われました。この思想のもとに，非決定性チューリングマシン，マルチテープチューリングマシン，ラムダ計算，帰納的関数の理論，などなどさまざまな計算のモデルが作られました。しかし，最終的には，どのモデルを使ったとしても，得られる決定可能性はどれも同値である（つまり互いに互いをシミュレートし合うことができてしまう）ことがことごとく示されました。

このような経緯から，チューリングマシンを用いた決定可能性の定義は妥当だと，研究者たちに受け入れられるようになっていきました。

万能チューリングマシンと同様の計算能力を持つ計算メカニズムのことを，チューリング完全であると言います。簡単に言ってしまえば，計算機ができることを全て再現できるモデルのことです。チューリング完全なものの例としては，一般的なプログラミング言語はもちろん，マインクラフト，マリオメーカー等，単なるゲームのシステムにおいてもチューリング完全であるものがあることが証明されています。

長い年月をかけて，さまざまな計算モデルが定義され，チューリングマシンとの関係が解明されていきました。このような計算理論の結果を総合して，アロンゾ・チャーチ(Alonzo Church)は次の提唱をしました。

これにより，直感的であった「計算」の概念が明確に定義することができるようになりました。