チャイティンの定数が計算のランダムな核を明らかにする

アラン・チューリングは1936年、どんなアルゴリズムも、任意のコンピュータープログラムが停止するかどうかを完全に予測できないことを証明しました。この「停止問題」は、根本的に決定不可能です。数十年後、数学者のグレゴリー・チャイティンはΩ（オメガ）を導入しました。これは、ランダムに生成されたプログラムが停止する確率を表す定数です。