|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 的 ： [まと, てき] 【名詞】 1. mark 2. target ・ ラン ： [らん] 【名詞】 1. (1) run 2. (2) LAN (local area network) 3. (P), (n) (1) run/(2) LAN (local area network) ・ 列 ： [れつ] 【名詞】 1. queue 2. line 3. row
アルゴリズム的ランダムな無限列（あるごりずむてきらんだむなむげんれつ、）、あるいは単にランダムな列は、直感的にはどんなアルゴリズムにとってもランダムに見える二進無限列のことを言う。この定義は有限文字の列にも上手く適用される。ランダムな列はアルゴリズム情報理論において中心となる対象である。実行時間に特定の上限のあるアルゴリズムや神託への伺いを許したアルゴリズムなど、いくつかの異なった種類のアルゴリズムが考えられ、それに応じて異なったランダムネスの概念が存在する。もっとも良く知られているのはマルティンレーフランダムネス（1ランダムネスとも言う）であるが、もっと強いランダムネスや弱いランダムネスも存在する。単に「ランダム」と言った場合には、マルティンレーフランダムであることを意味することが多い。二進無限列は単位区間の実数と同一視できるので、ランダムな2進無限列はランダムな実数と呼ばれることもある。さらに、二進無限列は自然数の集合の特性関数とも同一視されるので、自然数の集合と見ることもある。二進のマルティンレーフランダムの無限列のクラスはRANDやMLRで表される。 == 歴史 == 適切なランダムな列の定義を最初に与えたのはペール・マルティン＝レーフであり、1966年のことであった。リヒャルト・フォン・ミーゼスなどの先行研究者もランダムネスのためにテストの概念を定式化して、ランダムネスのテストをすべて通過する列をランダムな列と定義しようとしたが、正確なランダムネスのテストの概念を与えることはできなかった。マルティンレーフによる重要な貢献は計算理論を使ってランダムネスのテストの概念を定式化したことにあった。この定義は、確率論のランダムネスの考え方とは対照的である。つまり、確率論では標本空間のどの特定の元もランダムとは言えないからである。 マルティンレーフランダムネスはその後、多くの同値な特徴付けが可能であることが示された。データ圧縮、ランダムネスのテスト、ギャンブルなどどれも元の定義には似ていないように思われるが、同時にどれもランダムな列が持つべき直感的な特徴を満たしている。ランダムな列は圧縮不可能であるだろうし、確率的なテストを通過するであろうし、賭をして儲けるのは難しいであろう。複数の定義が存在し異なる計算のモデルの異なる定義が一致することから、マルティンレーフランダムネスは数学において基本的な性質であって、マルティンレーフの特別なモデルではないと言える。 マルティンレーフランダムネスがランダムネスの直感的概念を「正しく」捕らえているというテーゼは、マルティンレーフ＝チャイティンのテーゼと呼ばれている。これは「チャーチ＝チューリングのテーゼ」と似たようなものである〔Jean-Paul Delahaye, Randomness, Unpredictability and Absence of Order , in ''Philosophy of Probability'', p. 145-167, Springer 1993.〕。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「アルゴリズム的ランダムな無限列」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Algorithmically random sequence 」があります。 スポンサード リンク
|