ランダム性を使用した不完全性定理チャイティンの不完全性定理

有限数列がランダムであるとは、それを生成するための簡便な方法がなく、数列そのものをデータに用いない限りは生成できないようなものである。チャイティンは、どんな無矛盾な理論でも「s がランダムである」という命題は有限個の数列 s についてしか証明できないこと、換言すれば「s がランダムである」という真な命題で証明できないものが無限個あることを示した。さらに、彼はプログラムの停止確率を与えるような無限ビット列Ω（オメガ）を定義し、それと不完全性定理との関わりも論じている。