停止確率の計算不可能性

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

停止確率の計算不可能性

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

「チャイティンの定数」の記事における「停止確率の計算不可能性」の解説

ある実数が計算可能であるとは、n を入力として与えられたとき、その実数の先頭から n 桁を出力するアルゴリズムが存在する場合である。これは、実数の数字を列挙するプログラムの存在と等価である。 停止確率は計算可能ではない。この事実の証明は、Ω の先頭 n 桁を与えるアルゴリズムがあるとすれば、そのアルゴリズムを用いれば長さ n までのプログラムの停止問題が解けてしまうことに拠る。停止問題は決定不能であるため、矛盾が生じ、Ω が計算できないことが示される。 このアルゴリズムは次のように進行する。Ω の先頭 n 桁と k ≤ n が与えられているとして、アルゴリズムは F の定義域を数え上げていき、数え上げた要素群が表す確率が Ω の 2-(k+1) 以内である限り続ける。この時点を過ぎると、最早長さ k であるような如何なるプログラムも定義域に存在し得ない。何故なら、もしそのようなプログラムがあれば、それぞれが測度に 2-k を追加することになってしまい、これは不可能だからである。従って、定義域内の長さ k の文字列の集合は、まさに既に列挙した文字列の集合である。