計算できない問題とは？
研究室からこんにちは(短期大学)
今回は、「計算できない問題」について、特に「計算できる／できない」の意味についてお話しします。
私がComputer Scienceを学び始めた初年度に使用した教科書の中、「Undecidability（決定不能性）」という章の序に次のような記述がありました（分かりやすく多少意訳し、一部省略しています。ここでは「決定不能」、「決定可能」という言い方をしていますが、「計算不能」、「計算可能」と読み替えることができます）：
「決定不能」という言葉から生じる意外な結論の一つは、答えを求める対象が一つしかない問題は、原理的には必ず「決定可能」であるということです。
例えば、かつて長い間未解決だったフェルマー予想を考えてみましょう。
「(i>3) のとき、方程式 (x^i+y^i=z^i) を満たす正の整数解は存在しない」という命題は正しいか。
ここで重要なのは、(x)、(y)、(z)、(i) はプログラムに与える入力ではないということです。
これらは命題の中で使われている変数にすぎず、この問題全体が一つの問いなのです。
さて、どんな入力に対しても常に「はい」と答えるアルゴリズムと、どんな入力に対しても常に「いいえ」と答えるアルゴリズムを考えます。
この二つのうち、どちらか一方はフェルマー予想に対して正しい答えを返しています。
もちろん、私たちにはどちらが正しいか分かりません。
しかし、どちらか一方は必ず正しいので、その意味では、この問題を解くアルゴリズムは存在すると言えるのです。
フェルマー予想のような難問が「決定可能」であるということを、不思議に思う必要はありません。
決定可能性とは、人間が答えを知っているかどうかや、証明できるかどうかを意味する言葉ではないからです。
計算理論でいう「決定不能」とは、無数の入力に対して、それぞれ正しい答えを返すアルゴリズムが存在するかどうかという問題です。
人類がまだ解いていない一つの数学の難問と、停止問題のように「どんなアルゴリズムでも解けない問題」とは、本質的にまったく異なるものなのです。
[HOPCROFT ULLMAN, 1979]
ここで重要なポイントは、最後にある「人類がまだ解いていない一つの数学の難問と、停止問題のように「どんなアルゴリズムでも解けない問題」とは、本質的にまったく異なるものなのです。」なのですが、当時の私には何を言っているのか、（何度読み直しても）その意味を理解できませんでした。
「計算できない問題」と言われると、普通は「解くことができない問題」のことかと思ってしまうのですが、そうではないのです。
引用の例でいうと、「フェルマー予想」が解決できるか否か、はここでは重要でありません（ちなみに、その答えは「はい」であることがワイルズによって証明され解決済みです）。
数学には数多くの重要未解決問題が残されていますし、それらもいずれ証明されるかもしれませんし、されないかもしれない、中には証明不可能なものもあるかもしれない。
けれど、そういうこととは無関係に、いずれの問題も計算可能なのです。
更に言えば、「神は存在するか？」という問いも計算可能なのです。
正しい答えは分かりません、正しい答えの求め方（即ちアルゴリズム）も分からなくていい、計算可能か計算不能か、というのは、正しく答えるアルゴリズムが存在するか否か、ただそれだけが問われており、その意味で計算可能（つまり、アルゴリズムが存在する）になるのです。
なぜか？いずれの問題も答えは一つだけで、その答えは「はい」か「いいえ」のどちらかです。なので、常に「はい」と答えるアルゴリズムと常に「いいえ」と答えるアルゴリズムの二つを考えると、どちらかが正しい答えを返すといえます。
どちらのアルゴリズムが正しいのかは分かりません。
しかし、ここで問われているのは正しいアルゴリズムが存在するか否か、だけということに注意してください。
正しいアルゴリズムは見つけなくてもいい、知らなくてもいいのです。
それが存在することさえいえれば、計算可能と言えるのです。
なお、正しいアルゴリズムが存在することを示すために、実際にそのようなアルゴリズムを作り上げる、それも一つの方法ですが、それが唯一の方法ではなく、そのようなものを作れなくても存在することさえ証明できれば良いことにも注意してください。
逆にある問題が計算不可能であることを示すには、その問題を正しく解くアルゴリズムが存在しない、を示す必要があります。
ここで重要な鍵となるのが、無数（＝無限）の概念です。引用文の中でも「無数の入力」という言い方が現れます。
つまり、無数の入力をとる問題のみが計算不可能となりえて、そうでない問題、例えば
「〇〇は存在するか？ただし、〇〇に入るのは、『神』、『悪魔』、『雪男』、『ネッシー』のいずれかとする」という問題も、フェルマー予想と同様、計算可能なのです。
ということで、計算不可能性については別の議論が必要なのですが、紙幅が尽きましたので、また別の機会にさせてもらいます。
引用文献
HOPCROFTE.JOHN, ULLMAND.JEFFREY. (1979). INTRODUCTION TO AUTOMATA THEORY, LANGUAGES, and COMPUTATION.
私がComputer Scienceを学び始めた初年度に使用した教科書の中、「Undecidability（決定不能性）」という章の序に次のような記述がありました（分かりやすく多少意訳し、一部省略しています。ここでは「決定不能」、「決定可能」という言い方をしていますが、「計算不能」、「計算可能」と読み替えることができます）：
「決定不能」という言葉から生じる意外な結論の一つは、答えを求める対象が一つしかない問題は、原理的には必ず「決定可能」であるということです。
例えば、かつて長い間未解決だったフェルマー予想を考えてみましょう。
「(i>3) のとき、方程式 (x^i+y^i=z^i) を満たす正の整数解は存在しない」という命題は正しいか。
ここで重要なのは、(x)、(y)、(z)、(i) はプログラムに与える入力ではないということです。
これらは命題の中で使われている変数にすぎず、この問題全体が一つの問いなのです。
さて、どんな入力に対しても常に「はい」と答えるアルゴリズムと、どんな入力に対しても常に「いいえ」と答えるアルゴリズムを考えます。
この二つのうち、どちらか一方はフェルマー予想に対して正しい答えを返しています。
もちろん、私たちにはどちらが正しいか分かりません。
しかし、どちらか一方は必ず正しいので、その意味では、この問題を解くアルゴリズムは存在すると言えるのです。
フェルマー予想のような難問が「決定可能」であるということを、不思議に思う必要はありません。
決定可能性とは、人間が答えを知っているかどうかや、証明できるかどうかを意味する言葉ではないからです。
計算理論でいう「決定不能」とは、無数の入力に対して、それぞれ正しい答えを返すアルゴリズムが存在するかどうかという問題です。
人類がまだ解いていない一つの数学の難問と、停止問題のように「どんなアルゴリズムでも解けない問題」とは、本質的にまったく異なるものなのです。
[HOPCROFT ULLMAN, 1979]
ここで重要なポイントは、最後にある「人類がまだ解いていない一つの数学の難問と、停止問題のように「どんなアルゴリズムでも解けない問題」とは、本質的にまったく異なるものなのです。」なのですが、当時の私には何を言っているのか、（何度読み直しても）その意味を理解できませんでした。
「計算できない問題」と言われると、普通は「解くことができない問題」のことかと思ってしまうのですが、そうではないのです。
引用の例でいうと、「フェルマー予想」が解決できるか否か、はここでは重要でありません（ちなみに、その答えは「はい」であることがワイルズによって証明され解決済みです）。
数学には数多くの重要未解決問題が残されていますし、それらもいずれ証明されるかもしれませんし、されないかもしれない、中には証明不可能なものもあるかもしれない。
けれど、そういうこととは無関係に、いずれの問題も計算可能なのです。
更に言えば、「神は存在するか？」という問いも計算可能なのです。
正しい答えは分かりません、正しい答えの求め方（即ちアルゴリズム）も分からなくていい、計算可能か計算不能か、というのは、正しく答えるアルゴリズムが存在するか否か、ただそれだけが問われており、その意味で計算可能（つまり、アルゴリズムが存在する）になるのです。
なぜか？いずれの問題も答えは一つだけで、その答えは「はい」か「いいえ」のどちらかです。なので、常に「はい」と答えるアルゴリズムと常に「いいえ」と答えるアルゴリズムの二つを考えると、どちらかが正しい答えを返すといえます。
どちらのアルゴリズムが正しいのかは分かりません。
しかし、ここで問われているのは正しいアルゴリズムが存在するか否か、だけということに注意してください。
正しいアルゴリズムは見つけなくてもいい、知らなくてもいいのです。
それが存在することさえいえれば、計算可能と言えるのです。
なお、正しいアルゴリズムが存在することを示すために、実際にそのようなアルゴリズムを作り上げる、それも一つの方法ですが、それが唯一の方法ではなく、そのようなものを作れなくても存在することさえ証明できれば良いことにも注意してください。
逆にある問題が計算不可能であることを示すには、その問題を正しく解くアルゴリズムが存在しない、を示す必要があります。
ここで重要な鍵となるのが、無数（＝無限）の概念です。引用文の中でも「無数の入力」という言い方が現れます。
つまり、無数の入力をとる問題のみが計算不可能となりえて、そうでない問題、例えば
「〇〇は存在するか？ただし、〇〇に入るのは、『神』、『悪魔』、『雪男』、『ネッシー』のいずれかとする」という問題も、フェルマー予想と同様、計算可能なのです。
ということで、計算不可能性については別の議論が必要なのですが、紙幅が尽きましたので、また別の機会にさせてもらいます。
引用文献
HOPCROFTE.JOHN, ULLMAND.JEFFREY. (1979). INTRODUCTION TO AUTOMATA THEORY, LANGUAGES, and COMPUTATION.