This HTML5 document contains 112 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dcthttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n6http://dbpedia.org/resource/File:
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
n14http://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
goldhttp://purl.org/linguistics/gold/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Kolmogorov_complexity
rdf:type
dbo:Album owl:Thing
rdfs:label
Kolmogorov complexity
rdfs:comment
In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of a shortest computer program (in a predetermined programming language) that produces the object as output. It is a measure of the computational resources needed to specify the object, and is also known as algorithmic complexity, Solomonoff–Kolmogorov–Chaitin complexity, program-size complexity, descriptive complexity, or algorithmic entropy. It is named after Andrey Kolmogorov, who first published on the subject in 1963.
rdfs:seeAlso
dbr:Algorithmically_random_sequence
owl:sameAs
freebase:m.0rqy yago-res:Kolmogorov_complexity
dbp:wikiPageUsesTemplate
dbt:Color dbt:Short_description dbt:Isbn dbt:Rp dbt:Compression_Methods dbt:Val dbt:Main dbt:Cite_web dbt:Cite_journal dbt:Reflist dbt:Cite_book dbt:See_also dbt:Slink dbt:Expand_section
dct:subject
dbc:Information_theory dbc:Measures_of_complexity dbc:Algorithmic_information_theory dbc:Computability_theory dbc:Descriptive_complexity
gold:hypernym
dbr:Length
prov:wasDerivedFrom
n14:Kolmogorov_complexity?oldid=1072608359&ns=0
dbo:wikiPageID
1635
dbo:wikiPageLength
40524
dbo:wikiPageRevisionID
1072608359
dbo:wikiPageWikiLink
dbr:Proof_by_contradiction dbr:Randomness dbr:Algorithmically_random_sequence dbr:Descriptive_complexity_theory dbr:Ray_Solomonoff dbr:Halting_problem dbr:Computer_science n6:Kolmogorov_complexity_and_computable_lower_bounds_svg.svg n6:Mandelpart2_red.png dbr:Programming_language dbc:Algorithmic_information_theory dbr:Incompressible_string dbr:Proof_of_impossibility dbc:Computability_theory dbr:Computation dbc:Descriptive_complexity dbr:Probability dbr:Interpreter_(computing) dbc:Information_theory dbr:Cantor's_diagonal_argument dbr:Lisp_(programming_language) dbr:Universal_Turing_machine dbr:Sample_entropy dbr:Multiple_discovery dbr:Discrete_uniform_distribution dbr:Blum_axioms dbr:Formal_system dbr:ASCII dbr:Grammar_induction dbr:Markov_information_source dbr:Matthew_effect dbr:Reductio_ad_absurdum dbr:Q.E.D. dbc:Measures_of_complexity dbr:Andrey_Kolmogorov dbr:Mathematics dbr:String_(computer_science) dbr:Turing_machine dbr:Leonid_Levin dbr:Full_employment_theorem dbr:Marcus_Hutter dbr:Entropy_(information_theory) dbr:Levenshtein_distance dbr:Martingale_(probability_theory) dbr:Bit dbr:Data_structure dbr:Solomonoff's_theory_of_inductive_inference dbr:Pigeonhole_principle dbr:Complexity dbr:Up_to dbr:Upper_and_lower_bounds dbr:Turing_completeness dbr:Turing_degree dbr:Code_golf dbr:Natural_number dbr:Kolmogorov_structure_function dbr:List_of_important_publications_in_theoretical_computer_science dbr:Chaitin's_constant dbr:Gödel's_incompleteness_theorems dbr:Data_compression dbr:Java_(programming_language) dbr:Computable_function dbr:Self-extracting_archive dbr:Algorithmic_information_theory dbr:Gregory_Chaitin dbr:Berry_paradox dbr:Jürgen_Schmidhuber dbr:Pascal_(programming_language) dbr:Inductive_reasoning dbr:Mutual_information dbr:Self-delimiting_program dbr:Computer_program dbr:Axiomatic_system dbr:Algorithmic_probability dbr:Bayesian_probability dbr:Chris_Wallace_(computer_scientist) dbr:Gödel_numbering dbr:Big_O_notation dbr:Measure_(mathematics)
dbo:abstract
In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of a shortest computer program (in a predetermined programming language) that produces the object as output. It is a measure of the computational resources needed to specify the object, and is also known as algorithmic complexity, Solomonoff–Kolmogorov–Chaitin complexity, program-size complexity, descriptive complexity, or algorithmic entropy. It is named after Andrey Kolmogorov, who first published on the subject in 1963. The notion of Kolmogorov complexity can be used to state and prove impossibility results akin to Cantor's diagonal argument, Gödel's incompleteness theorem, and Turing's halting problem.In particular, no program P computing a lower bound for each text's Kolmogorov complexity can return a value essentially larger than P's own length (see section ); hence no single program can compute the exact Kolmogorov complexity for infinitely many texts.
foaf:isPrimaryTopicOf
n14:Kolmogorov_complexity