チャイティンのオメガΩ - 小人さんの妄想「チャイティンのオメガΩ」とは何か。 それは「真の乱数」だ。 真の乱数、というのは「その数字そのものをもってしか表現することができない数」のことである。 例えば円周率3.141592...は、一見するとでたらめな数字の並びのようだが、「直径に対する円周の長さ」という簡潔な表現を持つ。 黄金比 1.618033... は、実は「正五角形の一辺と対角線との比」のことである。 ところが「チャイティンのオメガΩ」は、このような簡潔な表現を持つことができない。 他に例えようのない「真の乱数」なのである。 以下の説明の前に、予備知識として 不完全性定理の最短理解 d:id:rikunora:20080524 チューリングマシンは何を示したのか d:id:rikunora:20080525 を読んでおいた方がよいでしょう。 「チャイティンのオメガΩ」とは、「チューリングマシンの停止確率を表す数」のことで
