「数学コラム チューリングの停止問題の証明 パート2 （2020/05/10)」
チューリングの停止問題の証明。パート2です。
前回の続きから。
仮に万能ループ判定機
isTerminate(string function ,object parameter)
が存在するならば、
IsTerminate関数は
string functionの中に
記述された関数fnにつき
fn(parameter)
がコンピューターで実行されたときに、
それが有限時間内で終了するのか、
しないのかをboolで返すはずでした
もしそのような関数が存在する時、
我々は以下の関数コードfunctionX、およびその中に記述された
関数fnXを考察します。
string functionX =
@"
void fnX(string fn)
{
for (;;)
{
if (! isTerminate(fn,fn)) break;
}
}
";
@"
void fnX(string fn)
{
for (;;)
{
if (! isTerminate(fn,fn)) break;
}
}
";
さて、fnX(string function)
はどのように動くのでしょうか。
一例として単純な関数コード
//有限ループ
string functionA =
@"
void fnA(object parameter)
{
int i=1;
for (;;)
{
i*=2;
if (i%10==6) break;
}
}";
string functionA =
@"
void fnA(object parameter)
{
int i=1;
for (;;)
{
i*=2;
if (i%10==6) break;
}
}";
を用意し、
fnX(functionA)
がどのような挙動をするか考察してみましょう。
fnX(functionA)
↓
bool fnX(string fn = functionA)
{
for (;;)
{
if (! isTerminate(fn,fn)) break;
}
}
↓{
for (;;)
{
if (! isTerminate(fn,fn)) break;
}
}
bool fnX(object fn = functionA)
{
for (;;)
{
if (! isTerminate(functionA,funcionA)) break;
}
}
{
for (;;)
{
if (! isTerminate(functionA,funcionA)) break;
}
}
functionAは有限ループ。つまり
isTerminate(functionA,functionA) == true
を返すはずだからして、
↓
bool fnX(object fn = functionA)
{
for (;;)
{
if (! true) break;
}
}
{
for (;;)
{
if (! true) break;
}
}
↓
bool fnX(object fn = functionA)
{
for (;;)
{
;
}
}
{
for (;;)
{
;
}
}
つまり
fnX(functionA)
をコンピューター上で走らせた時は無限ループになります！
うーん・・・^_^;A
関数コードstring functionX (関数の設計図)と、
その中に記述されてる関数fnX (実際にコンピューター上で実行される演算)
のメタ関係が頭の中でこんがらがる。
しかも両者が
fnX(functionA)
みたいにミックスされて出てくるので、
相当、かなり、めっちゃややこしく感じと思いますが。^_^;
注意深くタイプを観察してると
どこにも文法違反は発生してません。
大丈夫。実際こうなります。
以上の結果を踏まえ、
fnX(functionX)
をコンピューター上で実行したらどうなるか。
これが本命であり
チューリング停止問題のコア。
この物体を考察することで、我々は最初の命題
万能ループ判定機
isTerminate(string function ,object parameter)
は存在しない。を証明します
(次回に続く。)