About: K-trivial set     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : owl:Thing, within Data Space : dbpedia.org associated with source document(s)
QRcode icon
http://dbpedia.org/c/7Fb4MxPKKY

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.

AttributesValues
rdfs:label
  • K-trivial set (en)
  • K自明集合 (ja)
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)
dct:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
sameAs
dbp:wikiPageUsesTemplate
has 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)
prov:wasDerivedFrom
page length (characters) of wiki page
foaf:isPrimaryTopicOf
is Link from a Wikipage to another Wikipage of
is Wikipage redirect of
is foaf:primaryTopic of
Faceted Search & Find service v1.17_git147 as of Sep 06 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3331 as of Sep 2 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 60 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software