|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 自明 ： [じめい] 1. (adj-na,n,adj-no) obvious 2. self-evident 3. axiomatic 4. self-explanatory ・ 集 ： [しゅう] 【名詞】 1. collection ・ 集合 ： [しゅうごう] 1. (n,vs) (1) gathering 2. assembly 3. meeting 4. (2) (gen) (math) set ・ 合 ： [ごう] 【名詞】 1. go (approx. 0.18l or 0.33m)
数学においてある自然数の集合がK自明集合（Kじめいしゅうごう、）であるとは、 そのを2進文字列と見た時に記述しやすいことを言う。 すなわち、その接頭コルモゴロフ複雑性が可能な限り低く，計算可能集合のそれに近いことを言う。 は1975年に計算不可能なK自明集合の存在を示した。 によれば、ランダムな集合の始切片は高い複雑性を持つ。 つまり、K自明集合はランダムからかけ離れているということである。 そのため、ランダムネスの理論で研究されており、 計算可能性理論や計算機科学におけるアルゴリズム情報理論とも関わりがある。 K自明集合は計算可能に近いという性質ももつ。 例えば、それらはすべてである、つまり、そのチューリングジャンプが停止問題に真理表還元可能である。 また、を形成する、つまり、上限に関して閉じていて、チューリング還元に関して下に閉じている。 == 定義 == ''K''を接頭コルモゴロフ複雑性とする、 すなわち、ある文字列''x''に対して、''K(x)''を接頭普遍機械のもとで''x''を出力する入力の最小の長さとする。 そのような機械は、直感的には、普遍的なプログラム言語で、有効なプログラムにさらに文字列を付け加えたものは有効でないようなものを表している。 ''K''に関する背景としては、例えばチャイティンの定数などがある。 自然数の集合''A''が自然数の定数''b''によりK自明集合であるとは、 : が成立することを言う。 ある集合がK自明集合であるとは、ある定数によりK自明であることを言う〔A. Nies (2009). Computability and Randomness, Oxford Science Publications, ISBN 978-0199230761〕〔Downey, Rodney G., Hirschfeldt, Denis R. (2010), "Algorithmic Randomness and Complexity", ISBN 978-0-387-68441-3〕。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「K自明集合」の詳細全文を読む スポンサード リンク
|