チューリングマシンシミュレーター＆解説

計算不能な関数入門：チューリングマシンが計算できない問題の理論

Tags: 計算可能性理論, チューリングマシン, 計算不能, 停止問題, 理論計算機科学

チューリングマシンと計算の限界

計算機科学において、チューリングマシンは計算可能性の理論的なモデルとして非常に重要視されています。これは、現代のコンピュータが行えるあらゆる計算を原理的に実行できると考えられているからです。この性質はチューリング完全性と呼ばれ、様々なプログラミング言語や計算モデルがチューリング完全であることが知られています。

しかし、チューリングマシンは全ての関数を計算できるわけではありません。数学的に定義可能な関数の中には、いかなるチューリングマシンを用いてもその値を求めることができないものが存在します。このような関数を「計算不能な関数（Uncomputable Function）」と呼びます。

この記事では、なぜ計算不能な関数が存在するのか、代表的な計算不能な関数である「停止問題」の決定不能性、そして計算不能性の概念が計算可能性理論においてどのような意義を持つのかを解説します。シミュレーターで具体的なチューリングマシンの動作を追うことで、「計算可能」の概念を深く理解し、そこから「計算不能」の概念が際立ってくることを目指します。

計算可能性の定義：チューリングマシンによる計算

まず、チューリングマシンによる「計算可能（Computable）」の定義を改めて確認します。ある関数 $f$ が計算可能であるとは、入力 $x$ に対して、チューリングマシンが有限時間で停止し、そのテープ上に $f(x)$ に相当する値を書き出すことができる場合に言います。入力 $x$ に対して関数が定義されていない場合（例えば、ある条件を満たさない場合など）や、計算過程が無限に続く場合は、その入力に対してチューリングマシンは停止せず、関数はその入力に対して計算不能であるとみなされます。特定の入力に対して停止しない場合があるとしても、関数が「計算可能」であるためには、定義域内の全ての入力に対してチューリングマシンが停止し、正しい出力を得られる必要があります。

なぜ計算不能な関数が存在するのか？

直感的に考えると、チューリングマシンは非常に強力な計算モデルです。しかし、なぜ計算できない関数が存在するのでしょうか。その理由はいくつかあります。

  1. チューリングマシンの有限性 vs. 関数の無限性: 定義可能なチューリングマシンは、その状態数、アルファベットのサイズ、遷移規則の数など、全てが有限です。したがって、可能なチューリングマシンの設計図（プログラム）の数は、自然数と同様に枚挙可能です（可算無限個）。一方で、自然数から自然数への関数 $f: \mathbb{N} \to \mathbb{N}$ の総数は、遥かに多い（非可算無限個）ことが数学的に示されます（カントールの対角線論法に似た議論が使われます）。可算無限個しかないチューリングマシンでは、非可算無限個存在する関数全てを計算し尽くすことは原理的に不可能です。計算可能な関数は、可能なチューリングマシンの数と同じく可算無限個しか存在しないため、残りの非可算無限個の関数は計算不能ということになります。

  2. 自己参照の困難性: チューリングマシンに関するある種の特性（例えば停止性）を、万能チューリングマシン自身が判定しようとすると、論理的な矛盾が生じる場合があります。これは有名な「停止問題」の決定不能性の根拠となります。

計算不能な関数の代表例：停止問題

最も有名で、計算可能性理論において極めて重要な計算不能な問題が「停止問題（Halting Problem）」です。

停止問題とは、「任意のチューリングマシン $M$ とその入力 $w$ に対して、$M$ が入力 $w$ で開始した場合に有限時間で停止するか、それとも無限に計算を続けるかを判定するアルゴリズムは存在するか」という問題です。この問題に対する答えは「存在しない」、つまり停止問題は決定不能であることが、アラン・チューリング自身によって証明されました。

これを関数として考えると、「チューリングマシン $M$ と入力 $w$ のペア $(M, w)$ を受け取り、$M$ が $w$ で停止するならば 1 を、停止しないならば 0 を返す関数」は、計算不能な関数であるということになります。この関数を $H(M, w)$ と表すことがあります。

なぜ停止問題が決定不能なのかを直感的に説明します。もし、任意の $(M, w)$ に対して停止性を判定できる万能判定マシン $H$（チューリングマシンとして実現可能と仮定する）が存在するとします。この $H$ を利用して、新しいチューリングマシン $D$ を以下のように構築することを考えます。

このマシン $D$ を、自身の記述 $\langle D \rangle$ を入力として実行した場合に何が起こるかを考えてみましょう。

どちらのケースも矛盾が生じるため、最初の仮定である「任意の $(M, w)$ に対して停止性を判定できるチューリングマシン $H$ が存在する」という主張が誤りであることになります。したがって、停止問題を解くチューリングマシンは存在しない、つまり停止問題は決定不能であり、その特性関数 $H(M, w)$ は計算不能な関数です。

シミュレーターと計算不能性の理解

チューリングマシンシミュレーターは、計算可能な関数の動作を視覚的に追体験するために非常に有用です。例えば、シミュレーター上で簡単な加算を行うマシンや、特定のパターンを認識して停止するマシンを構築し、その動作ステップを観察することができます。

これらの停止することが保証されている（または特定の条件で停止するように設計されている）計算可能なマシンの動作を追うことで、「入力に対して有限時間で計算が完了し、結果が出力される」という計算可能性の具体的なイメージを掴むことができます。

計算不能な関数をシミュレーターで直接「計算する」ことはできません。なぜなら、もしそれができてしまうなら、それは計算可能ということになり矛盾するからです。しかし、シミュレーター上で計算可能な関数の例を体験し、それと計算不能な関数の概念（例えば、停止しない可能性があること、万能な判定器が存在しないこと）を対比させることで、計算可能性と計算不能性の境界線、そしてチューリングマシンの能力の限界について、より深い洞察を得ることができるでしょう。

例えば、停止しないチューリングマシン（無限ループに陥るように設計されたマシン）をシミュレーターで実行してみると、プログラムされた条件によってはヘッドが無限に左右に動き続けたり、同じ状態遷移を繰り返したりして、いつまで経っても停止しない様子を観察できます。これは、計算不能な関数の一部に見られる「停止しない」という性質の一端を垣間見る経験になります。

計算不能性の意義

計算不能な関数が存在するという事実は、単なる理論的な curiositas に留まりません。これは計算機科学、特に理論計算機科学において極めて重要な意義を持ちます。

停止問題以外にも、例えば「任意のチューリングマシンが与えられた入力に対して空白テープを出力するか」といった問題（ライスの定理によって、自明でないチューリングマシンの言語非自明な特性は全て決定不能であることが示される）も計算不能です。これらの計算不能な問題の存在は、コンピュータ科学者がアルゴリズムを設計する上で、あるいは新しい計算モデルを考察する上で、常に意識すべき基本的な制約となります。

まとめ

この記事では、チューリングマシンで計算できない「計算不能な関数」という概念について解説しました。数学的に定義可能な関数の全てがチューリングマシンで計算可能であるわけではないこと、その最も有名な例が停止問題であること、そして停止問題が決定不能であることの直感的な証明（対角線論法に基づく）を紹介しました。

チューリングマシンシミュレーターは計算可能な関数の動作を具体的に理解するための強力なツールです。計算可能な例を追体験することで、計算という行為がどのように行われるかを深く理解し、それと比較することで計算不能という概念の重大さを実感することができます。

計算不能な関数の存在は、計算という行為には原理的な限界があることを示しており、計算機科学の基礎理論において非常に重要な概念です。計算可能性理論を学ぶ上で、この限界の存在とその理由を理解することは、その後のより高度な理論（複雑性理論など）を学ぶための強固な基盤となります。

シミュレーターを活用し、様々な計算可能なタスクをチューリングマシンでどのように実現できるかを試しながら、同時に「では、これは計算できるのだろうか？」「なぜできないのだろうか？」といった疑問を持つことで、計算可能性と計算不能性についての理解をさらに深めていただければ幸いです。