About: K-trivial set

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

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/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FK-trivial_set

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.

Attributes	Values
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)
dcterms:subject	Algorithmic information theory Computability theory
Wikipage page ID	41341441 (xsd:integer)
Wikipage revision ID	1106628728 (xsd:integer)
Link from a Wikipage to another Wikipage	Robert M. Solovay Algorithmic information theory Algorithmic information theory Computability theory Computably enumerable Cristian S. Calude Mathematics Arithmetical hierarchy Computer science Covering problem Algorithmically random sequence Kolmogorov complexity Halting problem Computability theory Upper set Kolmogorov Complexity Natural numbers Recursive set Chaitin's constant Loss function Turing jump 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
sameAs	K-trivial set K-trivial set K-trivial set K-trivial set
dbp:wikiPageUsesTemplate	dbt:Orphan dbt:Reflist dbt:Short_description
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	wikipedia-en:K-trivial_set?oldid=1106628728&ns=0
page length (characters) of wiki page	11423 (xsd:nonNegativeInteger)
foaf:isPrimaryTopicOf	wikipedia-en:K-trivial_set
is Link from a Wikipage to another Wikipage of	K-trivial sets Algorithmically random sequence
is Wikipage redirect of	K-trivial sets
is foaf:primaryTopic of	wikipedia-en:K-trivial_set

Faceted Search & Find service v1.17_git139 as of Feb 29 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (62 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