| dbo:abstract
|
- In mathematics, a set of natural numbers is called a K-trivial set if its initial segments viewed as binary strings are easy to describe: the prefix-free Kolmogorov complexity is as low as possible, close to that of a computable set. Solovay proved in 1975 that a set can be K-trivial without being computable. The says that random sets have a high initial segment complexity. Thus the K-trivials are far from random. This is why these sets are studied in the field of algorithmic randomness, which is a subfield of Computability theory and related to algorithmic information theory in computer science. At the same time, K-trivial sets are close to computable. For instance, they are all , i.e. sets whose Turing jump is computable from the Halting problem, and form a , i.e. class of sets closed under and closed downward under Turing reduction. (en)
- 数学においてある自然数の集合がK自明集合（Kじめいしゅうごう、英: K-trivial set）であるとは、その（英語: initial segment）を2進文字列と見た時に記述しやすいことを言う。すなわち、その接頭コルモゴロフ複雑性が可能な限り低く，計算可能集合のそれに近いことを言う。（英語: Robert_M._Solovay）は1975年に計算不可能なK自明集合の存在を示した。 （英語: Schnorr-Levin theorem）によれば、ランダムな集合の始切片は高い複雑性を持つ。つまり、K自明集合はランダムからかけ離れているということである。そのため、ランダムネスの理論で研究されており、計算可能性理論や計算機科学におけるアルゴリズム情報理論とも関わりがある。 K自明集合は計算可能に近いという性質ももつ。例えば、それらはすべて（英語: superlow）である、つまり、そのチューリングジャンプが停止問題にである。また、（英語: Turing ideal）を形成する、つまり、上限に関して閉じていて、チューリング還元に関して下に閉じている。 (ja)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 11423 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdfs:comment
|
- 数学においてある自然数の集合がK自明集合（Kじめいしゅうごう、英: K-trivial set）であるとは、その（英語: initial segment）を2進文字列と見た時に記述しやすいことを言う。すなわち、その接頭コルモゴロフ複雑性が可能な限り低く，計算可能集合のそれに近いことを言う。（英語: Robert_M._Solovay）は1975年に計算不可能なK自明集合の存在を示した。 （英語: Schnorr-Levin theorem）によれば、ランダムな集合の始切片は高い複雑性を持つ。つまり、K自明集合はランダムからかけ離れているということである。そのため、ランダムネスの理論で研究されており、計算可能性理論や計算機科学におけるアルゴリズム情報理論とも関わりがある。 K自明集合は計算可能に近いという性質ももつ。例えば、それらはすべて（英語: superlow）である、つまり、そのチューリングジャンプが停止問題にである。また、（英語: Turing ideal）を形成する、つまり、上限に関して閉じていて、チューリング還元に関して下に閉じている。 (ja)
- In mathematics, a set of natural numbers is called a K-trivial set if its initial segments viewed as binary strings are easy to describe: the prefix-free Kolmogorov complexity is as low as possible, close to that of a computable set. Solovay proved in 1975 that a set can be K-trivial without being computable. At the same time, K-trivial sets are close to computable. For instance, they are all , i.e. sets whose Turing jump is computable from the Halting problem, and form a , i.e. class of sets closed under and closed downward under Turing reduction. (en)
|
| rdfs:label
|
- K-trivial set (en)
- K自明集合 (ja)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
