「0以上1未満の範囲から、一様分布に従って乱数を1つ取り出し、表示する」ことを「有限の時間内に」「厳密な意味で」(つまり、選択される数字のほとんどは超越数となる)行えるアルゴリズムは「存在しない」と自分は理解しているのですが、その理解で正しいですか?
また、自分の理解が正しかった場合、そんなアルゴリズムは「存在しないと証明されている」のか「まだ発見されていない」のか「選択できると仮定して話を進める(公理として認める)しかない」のか、どれでしょう?
仰る通り、完全な自然乱数を算術的に発生させるアルゴリズムは存在しません。
そもそも、乱数とは、「過去の履歴から次の値を予測することが不可能な数列」です。アルゴリズムが存在したら、それはつまり次の値を予測することが可能という事になります。算術的に発生させられるのはあくまで「疑似乱数」です。
ちなみに、近代コンピュータの父と呼ばれるジョン・フォン・ノイマン博士は、「算術的に自然乱数を発生させようとするのは、神に挑戦しているという事だ」と言っていたそうです。
乱数を算術的に発生させるのは無理ですが、物理的に発生させるぶんには自然のノイズを利用すれば容易に実現できますので、最近はCPUに物理乱数を発生させる機構が搭載されています。
コメント(2件)
証明の有無については、
hissssaさん
「アルゴリズムが存在したら、それはつまり次の値を予測することが可能という事になります。」
以上、証明終わり。
っていうこと? で、いいのかな?
しかし、どこを切り取るかをアルゴリズム化したら、値が予測可能だからやっぱりダメ。
出てきた数字を並べて、「ああ、乱数だったね」と呟くのが精一杯。