| 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 |
41341441 (xsd:integer) |
| dbo:wikiPageLength |
11423 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1106628728 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbr:Robert_M._Solovay dbr:Algorithmic_information_theory dbc:Algorithmic_information_theory dbr:Computability_theory dbr:Computably_enumerable dbr:Cristian_S._Calude dbr:Mathematics dbr:Arithmetical_hierarchy dbr:Computer_science dbr:Covering_problem dbr:Algorithmically_random_sequence dbr:Kolmogorov_complexity dbr:Halting_problem dbc:Computability_theory dbr:Upper_set dbr:Kolmogorov_Complexity dbr:Natural_numbers dbr:Recursive_set dbr:Chaitin's_constant dbr:Loss_function dbr:Turing_jump dbr:Turing_reduction dbr:Promptly_simple dbr:Schnorr_trivial_sets dbr:Schnorr–Levin_theorem dbr:Standard_cost_function dbr:Strongly_jump_traceable_sets dbr:Superlow dbr:Turing_ideal dbr:Turing_join |
| dbp:wikiPageUsesTemplate |
dbt:Orphan dbt:Reflist dbt:Short_description |
| dcterms:subject |
dbc:Algorithmic_information_theory dbc:Computability_theory |
| 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 |
freebase:K-trivial set wikidata:K-trivial set dbpedia-ja:K-trivial set https://global.dbpedia.org/id/bEgz |
| prov:wasDerivedFrom |
wikipedia-en:K-trivial_set?oldid=1106628728&ns=0 |
| foaf:isPrimaryTopicOf |
wikipedia-en:K-trivial_set |
| is dbo:wikiPageRedirects of |
dbr:K-trivial_sets |
| is dbo:wikiPageWikiLink of |
dbr:K-trivial_sets dbr:Algorithmically_random_sequence |
| is foaf:primaryTopic of |
wikipedia-en:K-trivial_set |