「チューリングの停止問題の証明 パート4 (完) （2020/06/14)」


チューリングの停止問題を証明します。
完全版。



前回のパート3で、我々は
　　bool isTerminate (string function,object parameter)

形式では
万能ループ判定関数は絶対に記述できないと証明しました。


ただし。それはあくまで
　　bool isTerminate (string function,object parameter)
形式では記述できないと言うだけで、

enum Answer
{
　　finite,
　　infinite,
　　un_answerable
}
Answer isTerminate (string function,object parameter);


のような、前回のbool矛盾を回避するような
別の形による判定関数の存在を否定したわけではありません。


それではこの
　　enum Answer isTerminate (string function,object parameter);

改良型による万能ループ判定関数は記述可能でしょうか・・・？

答え：NO
どれだけ改良してもループ判定関数は記述することができません。

証明：
仮にそのような万能ループ判定機が存在するのならば、
それは

for (;;)
{
　　　　if (円周率の[1000兆桁目] == 0)　　break;
}


が有限ループか、無限ループかを判定できるはずです。

ところが2020年の円周率世界記録は約35兆桁程度であり、
1000兆桁目の値は誰も知りません。
つまり
　　　　if (円周率の[1000兆桁目] == 0)　　break;

の判定はできるわけがない。


それどころか、もし本当に「あらゆる関数に対してループ判定が可能」であるならば
　　if (円周率の[1,000兆桁目] == 0)　　break;
　　if (円周率の[10,000兆桁目] == 0)　　break;
　　if (円周率の[100,000,000,000兆桁目] == 0)　　break;
　　if (円周率の[Tree(3)桁目] == 0)　　break;
　　if (円周率の[Rayo数桁目] == 0)　　break;

人類の科学力を遥かに超えた、どれだけ遠方の
値でも求める事ができてしまうことになる。

それはありえない。
よって万能ループ判定関数は存在しません。
証明完了。□


もちろん・・・
大量の予算とリソースと時間をかけて円周率を計算し続ければ
　　if (円周率の[100,000,000,000兆桁目] == 0)　　break;

もいずれは計算可能。判定可能ではある。

そういう意味としてはループ判定も可能なのですが・・・
そのような計算が完了するまでに
人間の科学力で何万年待つことになるか。^_^;

そんなに長く待たされる作業では
もはや計算不可能とほぼ同じ事です。

なので、やはりループ判定関数は存在しません。
証明完了。□