「数学コラム チューリングの停止問題の証明 パート1 （2020/05/02)」
さて。
この数学コラムでも(BX関数のときに)何回か出てきた
「チューリングの停止問題」
を証明します。
コロナ騒動の自宅待機で
時間が余ってるときに
考えてみてください。
例えば、以下のような関数があるときに
void chaotic(double limit)
{
double c = 0.5;
for (;;)
{
c = 3.8 * c * (1.0-c);
if (c<=limit) break;
}
}
{
double c = 0.5;
for (;;)
{
c = 3.8 * c * (1.0-c);
if (c<=limit) break;
}
}
いわゆるカオス関数。
見た目は簡単ですがcは
c = 0.5000 → 0.9500 → 0.1805 → 0.5620
→ 0.9353 → 0.2297 → 0.6725 → 0.8368 → ...
のように不規則に動きまくり、
与えられた引数limitに対し
if (c<=limit) break
条件が発動するかの判定は恐ろしく難しい。
実際に「しばらく動かして様子を観察する」以外に方法はなく、
事前的な予測はほぼ無理に近いです。
チューリングの停止問題は
このような場合に
「ループの有限/無限 判定は一般には不可能である」
と述べています。
(無論、chaotic関数のループ判定も頑張ればできる。
ただそれは一個一個の問題に対して、
個別の判定方法を編みだす必要があるわけで。
「1個のアルゴリズムで全てのループを判定できる」
万能判定アルゴリズムは存在しないと言っているのがチューリングの停止問題)
そもそも「プログラム」とは、
現代的な視点から考えたら
・C#言語で記述された関数コード
(C、C++、C#、Javascript、BASIC...
言語は何でもいい)
・関数に渡す引数の値
のペアと考えることができます
例：
void function(object parameter /*引数の値パート*/)
{
//関数コードのパート
int i=1;
for (;;)
{
i*=2;
if (i % 10==parameter)
break;
}
}
なぜなら、{
//関数コードのパート
int i=1;
for (;;)
{
i*=2;
if (i % 10==parameter)
break;
}
}
関数コード ＆ 関数に渡す引数の値
の2つを与えられればプログラムの挙動は
完全に確定するので。
「プログラム」 と 「関数コード ＆ 引数の値のペア」 は
等価と考えて差し支えありません。
なので。
もし仮に、プログラムに対しての
停止問題判定アルゴリズムが
存在するとすれば。
それは現代的に言えば
bool isTerminate(
string function, //関数コードのパート
object parameter //引数パートのパート
)
{
～
～判定アルゴリズム
～
～
～
}
のような判定プログラムが
C#で記述できるかと言う意味に等しいです。
・・・何を言ってるか。^_^;
だいぶ難しくなったので一例を出すとこんな感じです
//有限ループ
string functionA =
@"
void fnA(object parameter)
{
int i=1;
for (;;)
{
i*=2;
if (i%10==6) break;
}
}";
//無限ループ
string functionB =
@"
void fnB(object parameter)
{
int i=1;
for (;;)
{
i*=2;
if (i%10==3) break;
}
}";
//引数による
string functionC =
@"
void fnC(object parameter)
{
int i=1;
for (;;)
{
i*=2;
if (i%10==(int)parameter) break;
}
}";
isTerminate(functionA,null) == true;
isTerminate(functionB,null) == false;
isTerminate(functionC,6) == true;
isTerminate(functionC,3) == false;
string functionA =
@"
void fnA(object parameter)
{
int i=1;
for (;;)
{
i*=2;
if (i%10==6) break;
}
}";
//無限ループ
string functionB =
@"
void fnB(object parameter)
{
int i=1;
for (;;)
{
i*=2;
if (i%10==3) break;
}
}";
//引数による
string functionC =
@"
void fnC(object parameter)
{
int i=1;
for (;;)
{
i*=2;
if (i%10==(int)parameter) break;
}
}";
isTerminate(functionA,null) == true;
isTerminate(functionB,null) == false;
isTerminate(functionC,6) == true;
isTerminate(functionC,3) == false;
このように、
IsTerminate関数は
・C言語で記述された関数コード string function
と
・関数に渡す引数 object parameter
の2つを引数に取り、
string functionの中に記載されてる関数fn
fn(parameter)
がコンピューターで実行されたときに
それが有限時間内で終了するのか、
そろとも永久に終了しないのかを
IsTerminate関数は
string function ＆ object prameterの内容を解釈・解析・判定し、
正しい答えをboolで返してくれるはずです。
・・・だいぶ難しそうに見えますが
実は全然難しくありません。
というのもstring functionは「たかがstring型の引数」であり、
//有限ループ
string functionA =
@"
void fnA(object parameter)
{
int i=1;
for (;;)
{
i*=2;
if (i%10==6) break;
}
}";
isTerminate(functionA,null);
string functionA =
@"
void fnA(object parameter)
{
int i=1;
for (;;)
{
i*=2;
if (i%10==6) break;
}
}";
isTerminate(functionA,null);
isTerminateの入力に入ってくるfunctionAは、たかがstring。
それ以外の何者でもない。
そしてそのstring functionの内容を解釈・解析するのは
コンパイラが日常的にやってることなので
それ自体は全く問題はありません。
絶対に可能です。
(もしstring functionが不正な構文。正しいC言語になっていないケースについては
プログラムが異常停止するのでtrueを返すとする)
問題は・・・判定部分の方なんだね。^_^;
string functionの動作を考え、それが
無限ループになっているかそれとも有限時間で終わるのか。
それを判定するプログラムを書くってのは
恐ろしく難しい。
一見すると・・・もしかしたら・・・・
できる～～～かもしれない？
に見えるのですが。
じゃあ実際にやってみると、
これがとてつもない難題だと気付きます。
と言うか無理。
・・・
・・
・
実はそのような
停止問題判定アルゴリズム
isTerminate
は存在しません！
どれだけの超天才プログラマーでも
絶対に絶対に絶対にisTerminate関数は作成できない。
もし仮に作成できたとしたら、矛盾が発生する。
ゆえにisTerminate関数はこの世に存在しえない。
なぜそうなるのか
次回にそれを示します。