「数学コラム 巨大有限数のお話(20) Uncomputableカテゴリの意味 (2019/08/31)」
前回のおさらい
ランク21 Uncomputableに属する巨大数は値を計算する事ができません。
Q.何故に計算出来ないのか?
A.無限ループの判定が出てくるから
例えば
BX関数(100) = 100文字で記述できるC言語コードを全て調べて、その中で最大の数を返す
この関数の値は・・・・実は計算できません。(^_^A;
なぜなら、100文字のCコードと言うことは↓のコードを含みます。
(int は無限桁を保持できるものとする)
int i=1;
for(;;)
{
i*=2;
if (i%10==1) break;
}
return i;
ところがこれは無限ループであり、for(;;)
{
i*=2;
if (i%10==1) break;
}
return i;
プログラムが永遠に終わらないのでiを取り出すことができません。
つまりソースコードの中から
無限ループだけは
事前に取り除いておかなければならない。
しかし「無限ループの判定」と言うのは
恐ろしく難しい。
別のループの例を出すと
int i=1;
double x=0.5;
for(;;)
{
i*=2;
x = 3.9 * x* (1-x);
if (x < 0.1) break;
}
return i;
double x=0.5;
for(;;)
{
i*=2;
x = 3.9 * x* (1-x);
if (x < 0.1) break;
}
return i;
これはカオス関数の一例であり、
xは
0.5000
0.9500
0.1805
0.5620
0.9353
0.2297
0.6725
0.8368
0.5188
0.9486
0.1850
0.5731
...
のように激しく揺れ動く挙動を示し0.9500
0.1805
0.5620
0.9353
0.2297
0.6725
0.8368
0.5188
0.9486
0.1850
0.5731
...
xがどうなるのか非常~~~に読みづらい。
果たして
if (x < 0.1) break;
の条件は達成されるのか。
判定および証明はかなりの困難です。
少なくともコンピューター自身は黙々と計算してるだけで、自分が無限ループに入ってるのかわかってない。
だから人間がループの性質を研究し、手動で判定し、取り除いてやる必要がある。
いや、実際問題あらゆるソースコードを生成するということは
int i=1;
for(;;)
{
i= i*2;
if (XXX は素数か==true) break;
}
return i;
for(;;)
{
i= i*2;
if (XXX は素数か==true) break;
}
return i;
このような素数判定問題まで含めることができてしまう。
つまり無限ループの判定には「あらゆる数学的命題」についてYES/NOで答えられる
神の能力が解く必要になる。
それは不可能である。
一例としてBX関数を出しましたが、他のランク21 Uncomputableカテゴリ。
BB関数、Rayo数、ふぃっしゅ数なども
全部「n文字で記述できる全ての式を試し、その中で最大を探す」
総当り&MAX方式を取ってます。
それらは全て
全ての式を生成 → 無限ループ問題を含む
事になるので、無限ループ判定問題が発生する。
だが無限ループの判定は"ほぼ"不可能である。
(完全に不可能ではない。
n文字で記述できる数学的問題を全て解き明かせば
ループの無限/有限は判定できるので計算可能になるが、
それはあまりにも難易度が高すぎて実質的には無理なのである)
よって
ランク21 Uncomputableに属する巨大数は値を計算する事ができません。
と、なります。

