現代コンピュータの背景：チューリングマシンと計算不可能性
チューリングマシンの理論は、計算可能性という重要な概念を示しており、数学やコンピュータ科学において基礎的な役割を果たしています。チューリングマシンの理論に基づくと、計算問題は「計算可能」または「計算不能」の2つに分類されます。
計算可能な問題は、アルゴリズムや手続きを使って解を求めることができる問題であり、コンピュータや計算機械によって効率的に解決できます。一方、「計算不能」な問題は、どのようなアルゴリズムや計算手法を使っても解を求めることができない問題です。
この記事では、計算不能な問題の例として、以下の4つの問題を紹介します。
これらの問題は、チューリングマシンにおいても解決することができません。これは数学的に証明されています。計算不能な問題の存在は、コンピュータの限界や計算機械の能力を理解する上で重要な指標となっています。
このような問題は、一般に「決定問題」と呼ばれ、計算可能性理論の範疇で広く研究されています。
それでは、それぞれの問題について詳しく見ていきましょう。
停止問題
停止問題は、与えられたプログラムと入力に対して、そのプログラムが停止するかどうかを判定する問題です。つまり、「ある特定のプログラムがある特定の入力に対して、実行を終了するかどうかを決定するプログラムは存在するか？」という問題です。
この問題はチューリングマシンにおいても計算不能であることが証明されています。
停止問題が計算不能であることを示すためには、次のような矛盾を導くことができます。仮に停止判定プログラムHが存在したとします。
Hは任意のプログラムPと入力a1;:::;anを受け取り、Pがa1;:::;anに対して停止する場合はYESを返し、そうでない場合はNOを返すものとします。このHを使って、次のようなプログラムQを作ります。
Q(P) = if H(P,P) = YES then loop forever else stop
Qは任意のプログラムPを受け取り、H(P,P)の結果に応じて動作します。H(P,P)がYESを返す場合は無限ループに入ります。H(P,P)がNOを返す場合は停止します。ここでQ(Q)という入力を考えます。Q(Q)が停止するかどうかはH(Q,Q)の結果に依存しますが、
- H(Q,Q)がYESを返す場合はQ(Q)は無限ループに入ります。
- H(Q,Q)がNOを返す場合はQ(Q)は停止します。
しかし、これらはHの定義に反します。Hはプログラムと入力に対して停止するかどうかを正しく判定すると仮定しましたが、Q(Q)に対しては正しく判定できません。したがって、このようなHは存在しないということになります。これは停止問題が計算不能であることを意味します。
停止問題は、計算可能性理論の基本的な問題であり、多くの他の計算不能な問題に関連しています。例えば、プログラムの正当性や最適化、暗号解読などの問題は、停止問題を含むことが多いです。
また、停止問題は哲学や論理学においても興味深い問題です。例えば、自分自身の真偽を判定することができる命題やシステムは存在するかどうかという問題は、停止問題と関係しています。
帰納的関数の停止問題
帰納的関数の停止問題は、特定の帰納的関数に対して、入力が与えられた場合にその関数の計算が停止するかどうかを判定する問題です。これも停止問題と同様に計算不能です。
帰納的関数とは、自然数から自然数への関数であり、次のような基本的な関数や演算から帰納的に作られるものです。
- 定数関数：f(x) = n なる関数
- 後者関数：f(x) = x + 1 なる関数
- 射影関数：f(x1,…,xk) = xi なる関数
- 合成演算：g(x1,…,xk) = f(h1(x1,…,xk),…,hm(x1,…,xk)) なる演算
- 帰納演算：g(0,x2,…,xk) = f(x2,…,xk), g(n+1,x2,…,xk) = h(g(n,x2,…,xk),n,x2,…,xk) なる演算
帰納的関数はチューリングマシンで計算可能な関数と等価です。つまり、任意の帰納的関数はチューリングマシンで計算できますし、任意のチューリングマシンで計算可能な関数は帰納的関数として表せます。
しかし、帰納的関数が必ずしも全域ではないことに注意が必要です。つまり、ある入力に対して帰納的関数が停止しない場合があります。
帰納的関数の停止問題は、与えられた帰納的関数fと入力a1;:::;anに対して、f(a1;:::;an)が有限回の演算で値を返すかどうかを判定する問題です。この問題もチューリングマシンで計算不能であることが証明されています。
帰納的関数の停止問題が計算不能であることを示すためには、次のような矛盾を導くことができます。仮に帰納的関数の停止判定プログラムHが存在したとします。
Hは任意の帰納的関数fと入力a1;:::;anを受け取り、f(a1;:::;an)が有限回の演算で値を返す場合はYESを返し、そうでない場合はNOを返すものとします。このHを使って、次のような帰納的関数Qを作ります。
Q(f,a1,…,an) = if H(f,a1,…,an) = YES then loop forever else stop
Qは任意の帰納的関数fと入力a1;:::;anを受け取り、H(f,a1;:::;an)の結果に応じて動作します。H(f,a1;:::;an)がYESを返す場合は無限ループに入ります。H(f,a1;:::;an)がNOを返す場合は停止します。ここでQ(Q,Q)という入力を考えます。Q(Q,Q)が停止するかどうかはH(Q,Q)の結果に依存しますが、
- H(Q,Q)がYESを返す場合はQ(Q,Q)は無限ループに入ります。
- H(Q,Q)がNOを返す場合はQ(Q,Q)は停止します。
しかし、これらはHの定義に反します。Hは帰納的関数と入力に対して停止するかどうかを正しく判定すると仮定しましたが、Q(Q,Q)に対しては正しく判定できません。
したがって、このようなHは存在しないということになります。これは帰納的関数の停止問題が計算不能であることを意味します。
帰納的関数の停止問題は、チューリングマシンで計算可能な関数と等価な帰納的関数においても解決することができません。これはチューリングマシンの理論が計算可能性の限界を示しており、数学的に証明されています。
帰納的関数の停止問題は、計算可能性理論や計算複雑性理論において重要な役割を果たしています。例えば、帰納的関数の停止問題は、P≠NP問題やハルティング問題などの有名な未解決問題と関連しています。
帰納的言語の決定問題
帰納的言語の決定問題は、ある帰納的言語（再帰的集合）が与えられたとき、特定の文字列がその言語に属するかどうかを判定する問題です。帰納的言語の決定問題も計算不能です。
帰納的言語とは、自然数から自然数への帰納的関数で表される言語です。つまり、ある自然数nが帰納的言語Lに属するかどうかは、ある帰納的関数f(n)が0以外の値を返すかどうかで判定できます。
例えば、素数からなる言語や偶数からなる言語などは帰納的言語です。
帰納的言語の決定問題は、与えられた帰納的関数fと入力nに対して、f(n)が0以外の値を返すかどうかを判定する問題です。この問題もチューリングマシンで計算不能であることが証明されています。
帰納的言語の決定問題が計算不能であることを示すためには、次のような矛盾を導くことができます。仮に帰納的言語の決定判定プログラムHが存在したとします。
Hは任意の帰納的関数fと入力nを受け取り、f(n)が0以外の値を返す場合はYESを返し、そうでない場合はNOを返すものとします。このHを使って、次のような帰納的関数Qを作ります。
Q(f,n) = if H(f,n) = YES then 0 else 1
Qは任意の帰納的関数fと入力nを受け取り、H(f,n)の結果に応じて動作します。H(f,n)がYESを返す場合は0を返します。
H(f,n)がNOを返す場合は1を返します。ここでQ(Q,Q)という入力を考えます。Q(Q,Q)が0以外の値を返すかどうかはH(Q,Q)の結果に依存しますが、
- H(Q,Q)がYESを返す場合はQ(Q,Q)は0を返します。
- H(Q,Q)がNOを返す場合はQ(Q,Q)は1を返します。
しかし、これらはHの定義に反します。Hは帰納的関数と入力に対して0以外の値を返すかどうかを正しく判定すると仮定しましたが、Q(Q,Q)に対しては正しく判定できません。
したがって、このようなHは存在しないということになります。これは帰納的言語の決定問題が計算不能であることを意味します。
帰納的言語の決定問題は、チューリングマシンで計算可能な言語と等価な帰納的言語においても解決することができません。これはチューリングマシンの理論が計算可能性の限界を示しており、数学的に証明されています。
帰納的言語の決定問題は、形式言語やオートマトン理論において重要な役割を果たしています。例えば、チューリング完全性やチャーチ・チューリングのテーゼなどの概念と関連しています。
自己参照的な問題
自己参照的な問題は、ある問題が自分自身に対して満たすべき条件を満たすかどうかを判定する問題です。例えば、「この問題の解はYESである」という問題を考えると、その解がYESかNOかを判定することは不可能です。
自己参照的な問題も計算不能です。これは次のように示すことができます。仮に自己参照的な問題の解決プログラムHが存在したとします。
Hは任意の自己参照的な問題Pを受け取り、Pが自分自身に対して満たすべき条件を満たす場合はYESを返し、そうでない場合はNOを返すものとします。このHを使って、次のような自己参照的な問題Qを作ります。
Q = 「この問題Qの解はH(Q)と異なる」
Qは自分自身に対して満たすべき条件として、その解がH(Q)と異なることを要求しています。しかし、この条件は矛盾しています。なぜなら、
- Qの解がYESである場合はH(Q)もYESである必要があります。
- Qの解がNOである場合はH(Q)もNOである必要があります。しかし、これらはHの定義に反します。
Hは自己参照的な問題に対して正しく解を返すと仮定しましたが、Qに対しては正しく解を返せません。
したがって、このようなHは存在しないということになります。これは自己参照的な問題が計算不能であることを意味します。
自己参照的な問題は、計算可能性理論だけでなく、哲学や論理学においても重要な問題です。例えば、ギリシャの哲学者エピメニデスが「クレタ人はすべて嘘つきだ」と言ったとき、その命題は真か偽かを判定することができるでしょうか？
また、数学者ベルトラン・ラッセルが提唱した「集合の逆説」は、自分自身を含む集合や含まない集合に関する矛盾を導くものです。これらの問題は、自己参照的な問題の例として知られています。
この記事では、計算不能な問題の例として、以下の4つの問題を紹介しました。
これらの問題は、チューリングマシンの理論に基づく計算モデルにおいても解決することができません。これはチューリングマシンの理論が計算可能性という重要な概念を示しており、数学的に証明されています。
計算不能な問題の存在は、コンピュータの限界や計算機械の能力を理解する上で重要な指標となっています。このような問題は、一般に「決定問題」と呼ばれ、計算可能性理論の範疇で広く研究されています。
【参考文献】
(1) チューリングマシン - Wikipedia. https://ja.wikipedia.org/wiki/%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E3%83%9E%E3%82%B7%E3%83%B3.
(2) チューリングマシンの定義とそれに関連する話 | 高校数学の .... https://manabitimes.jp/math/2128.
(3) チューリングマシンの実用的な重要性 - QA Stack. https://qastack.jp/cs/9341/practical-importance-of-turing-machines.
(4) チューリングマシン(ちゅーりんぐましん)とは？ 意味や使い方 .... https://kotobank.jp/word/%E3%83%81%E3%83%A5%E3%83%BC%E3%83%AA%E3%83%B3%E3%82%B0%E3%83%9E%E3%82%B7%E3%83%B3-5795.
(5) チューリングの停止性問題 | IIJ Engineers Blog. https://eng-blog.iij.ad.jp/archives/3095.
(6) 計算可能関数 - Wikipedia. https://ja.wikipedia.org/wiki/%E8%A8%88%E7%AE%97%E5%8F%AF%E8%83%BD%E9%96%A2%E6%95%B0.
(7) 情報数学 - 第5回 計算不可能な関数 - Keio. https://web.sfc.keio.ac.jp/~hagino/mi15/05-ppt.pdf.
