数論の未解決問題への応用

ウィキペディア小見出し辞書

数論の未解決問題への応用

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/03/29 09:02 UTC 版)

「チャイティンの定数」の記事における「数論の未解決問題への応用」の解説

チャイティンの定数は、原理的には、ゴールドバッハ予想やリーマン予想といった数論の未解決問題を解くのに用いることが出来る。ゴールドバッハ予想とは、2より大きい全ての偶数は2つの素数の和で表せる、というものである。ある偶数が与えられたとき、それを2つの素数の和に分解するプログラムを考える。ゴールドバッハ予想が正しければ、このプログラムは偶数を次々に2つの素数に分解していくだろう。素数に分解できない偶数という反例が見つかった場合、プログラムは停止し、ゴールドバッハ予想は間違いだったことが示される。このプログラムの長さを N ビットとする。計算資源と時間に制限がない場合、チャイティンの定数を使ってゴールドバッハ予想を次のように証明できる。同時並行的に、長さが N + 1 ビット以下であるような全てのプログラムを実行する。Nビットであるゴールドバッハプログラムが停止すれば、予想は偽であったと証明される。もしこの逆に、他のプログラムがどんどん停止してあと一つでも停止すればチャイティンの定数を超えてしまう状況となり、その時点でまだゴールドバッハプログラムが停止していないなら、最早ゴールドバッハプログラムは停止し得ないので、ゴールドバッハ予想が正しいことが証明される。この方法を用いる上では、チャイティンの定数の先頭から N + 1 ビットまでの値さえ分かればよい。 同様に、リーマン予想などの数学上の未解決問題の多くも、チャイティンの定数を使って証明（または反証）できる。 上の説明は再帰的公理化可能理論の可証性述語がチャイティン定数から相対的に計算可能であるということを示しているに過ぎない。上記の方法で未解決問題の可証性を判定するために必要なビット長は長大であり、チャイティン定数の正確な値を必要なだけ求めることは困難である。仮に必要なだけのビットが求められたとしても、上のアルゴリズムの計算量は膨大である。したがって上記の方法で未解決問題の可証性を判定することが実際的な意味で可能であるというわけではない。