数学においてある自然数の集合がK自明集合(Kじめいしゅうごう、英: K-trivial set)であるとは、その(英語: initial segment)を2進文字列と見た時に記述しやすいことを言う。すなわち、その接頭コルモゴロフ複雑性が可能な限り低く,計算可能集合のそれに近いことを言う。(英語: Robert_M._Solovay)は1975年に計算不可能なK自明集合の存在を示した。 (英語: Schnorr-Levin theorem)によれば、ランダムな集合の始切片は高い複雑性を持つ。つまり、K自明集合はランダムからかけ離れているということである。そのため、ランダムネスの理論で研究されており、計算可能性理論や計算機科学におけるアルゴリズム情報理論とも関わりがある。 K自明集合は計算可能に近いという性質ももつ。例えば、それらはすべて(英語: superlow)である、つまり、そのチューリングジャンプが停止問題にである。また、(英語: Turing ideal)を形成する、つまり、上限に関して閉じていて、チューリング還元に関して下に閉じている。

Property Value
dbo:abstract
  • 数学においてある自然数の集合がK自明集合(Kじめいしゅうごう、英: K-trivial set)であるとは、その(英語: initial segment)を2進文字列と見た時に記述しやすいことを言う。すなわち、その接頭コルモゴロフ複雑性が可能な限り低く,計算可能集合のそれに近いことを言う。(英語: Robert_M._Solovay)は1975年に計算不可能なK自明集合の存在を示した。 (英語: Schnorr-Levin theorem)によれば、ランダムな集合の始切片は高い複雑性を持つ。つまり、K自明集合はランダムからかけ離れているということである。そのため、ランダムネスの理論で研究されており、計算可能性理論や計算機科学におけるアルゴリズム情報理論とも関わりがある。 K自明集合は計算可能に近いという性質ももつ。例えば、それらはすべて(英語: superlow)である、つまり、そのチューリングジャンプが停止問題にである。また、(英語: Turing ideal)を形成する、つまり、上限に関して閉じていて、チューリング還元に関して下に閉じている。 (ja)
  • 数学においてある自然数の集合がK自明集合(Kじめいしゅうごう、英: K-trivial set)であるとは、その(英語: initial segment)を2進文字列と見た時に記述しやすいことを言う。すなわち、その接頭コルモゴロフ複雑性が可能な限り低く,計算可能集合のそれに近いことを言う。(英語: Robert_M._Solovay)は1975年に計算不可能なK自明集合の存在を示した。 (英語: Schnorr-Levin theorem)によれば、ランダムな集合の始切片は高い複雑性を持つ。つまり、K自明集合はランダムからかけ離れているということである。そのため、ランダムネスの理論で研究されており、計算可能性理論や計算機科学におけるアルゴリズム情報理論とも関わりがある。 K自明集合は計算可能に近いという性質ももつ。例えば、それらはすべて(英語: superlow)である、つまり、そのチューリングジャンプが停止問題にである。また、(英語: Turing ideal)を形成する、つまり、上限に関して閉じていて、チューリング還元に関して下に閉じている。 (ja)
dbo:wikiPageID
  • 2951161 (xsd:integer)
dbo:wikiPageLength
  • 7711 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 58480007 (xsd:integer)
dbo:wikiPageWikiLink
prop-ja:wikiPageUsesTemplate
dct: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)
  • 数学においてある自然数の集合がK自明集合(Kじめいしゅうごう、英: K-trivial set)であるとは、その(英語: initial segment)を2進文字列と見た時に記述しやすいことを言う。すなわち、その接頭コルモゴロフ複雑性が可能な限り低く,計算可能集合のそれに近いことを言う。(英語: Robert_M._Solovay)は1975年に計算不可能なK自明集合の存在を示した。 (英語: Schnorr-Levin theorem)によれば、ランダムな集合の始切片は高い複雑性を持つ。つまり、K自明集合はランダムからかけ離れているということである。そのため、ランダムネスの理論で研究されており、計算可能性理論や計算機科学におけるアルゴリズム情報理論とも関わりがある。 K自明集合は計算可能に近いという性質ももつ。例えば、それらはすべて(英語: superlow)である、つまり、そのチューリングジャンプが停止問題にである。また、(英語: Turing ideal)を形成する、つまり、上限に関して閉じていて、チューリング還元に関して下に閉じている。 (ja)
rdfs:label
  • K自明集合 (ja)
  • K自明集合 (ja)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageWikiLink of
is owl:sameAs of
is foaf:primaryTopic of