Algorithmic information theory (original) (raw)
La teoría algorítmica de la información, es una teoría científica de las ciencias de la computación, que en contraste con la clásica teoría de la información, se basa en la complejidad de Kolmogórov para la determinación del contenido de la información. Fue desarrollada principalmente por Gregory Chaitin, Andréi Kolmogórov y Ray Solomonoff.
| Property | Value |
|---|---|
| dbo:abstract | La teoria algorísmica de la informació és una branca de la informàtica teòrica que s'ocupa de la relació entre la computació i la informació d'objectes generats computacionalment (a diferència dels generats estocàsticament), com ara cadenes de caràcters o qualsevol altra estructura de dades. En altres paraules, es mostra dins de la teoria algorísmica de la informació que la incompressibilitat computacional "imita" (excepte una constant que només depèn del llenguatge de programació universal escollit) les relacions o desigualtats que es troben en la teoria de la informació. Segons Gregory Chaitin, és "el resultat de posar la teoria de la informació de Shannon i la (teoria de la computabilitat de Turing) en una coctelera i sacsejar amb força". A més de la formalització d'una mesura universal per al contingut d'informació irreductible d'objectes generats computacionalment, alguns dels èxits principals de la teoria algorísmica de la informació van ser mostrar que: de fet, la complexitat algorísmica segueix (en el cas ) les mateixes desigualtats (excepte una constant) que l'entropia, com en la teoria clàssica de la informació; l'aleatorietat és incompressibilitat; i, dins de l'àmbit del programari generat aleatòriament, la probabilitat d'ocurrència de qualsevol estructura de dades és de l'ordre del programa més curt que la genera quan s'executa en una màquina universal. La teoria algorísmica de la informació estudia principalment mesures del contingut d'informació irreductible de les cadenes de caràcters (o altres estructures de dades). Com que la majoria d'objectes matemàtics es poden descriure en termes de cadenes de caràcters, o com el límit d'una seqüència de cadenes, es pot utilitzar per estudiar una gran varietat d'objectes matemàtics, inclosos els nombres enters. Una de les principals motivacions darrere de la teoria algorísmica de la informació és l'estudi de la informació que transporten els objectes matemàtics com en el camp de les metamatemàtiques, per exemple, tal com mostren els resultats d'incompletesa esmentats més endavant. Altres motivacions principals provenien de: la superació de les limitacions de la teoria clàssica de la informació per a objectes individuals i fixos; formalitzar el concepte d'aleatorietat; i trobar una inferència probabilística significativa sense coneixement previ de la distribució de probabilitat (per exemple, si és independent i distribuïda de manera idèntica, markoviana o fins i tot ). D'aquesta manera, se sap que la teoria algorísmica de la informació es basa en tres conceptes matemàtics principals i les relacions entre ells: complexitat algorísmica, i . (ca) Die algorithmische Informationstheorie ist eine Theorie aus der theoretischen Informatik, die im Gegensatz zur klassischen Informationstheorie die Kolmogorow-Komplexität zur Bestimmung des Informationsgehalts verwendet. Sie wurde im Wesentlichen von Gregory Chaitin, Andrey Kolmogorov und Ray Solomonoff entwickelt. Zur Beschreibung des Informationsgehalts einer Zeichenkette betrachtet die algorithmische Informationstheorie die Größe eines kleinsten Algorithmus, der die Zeichenkette erzeugt. Gregory Chaitin präzisierte diese allgemein als Kolmogorow-Komplexität bekannte Größe durch ein spezielles Maschinenmodell, nach dem der Algorithmus ausführbar sein muss. Wie Chaitin beweisen konnte, lässt sich der algorithmische Informationsgehalt einer Zeichenkette nicht endgültig angeben, da nicht beweisbar ist, ob ein gegebenes Programm zu ihrer Erzeugung wirklich das kürzeste ist. Ebenso wie der Informationsbegriff nach Claude Shannon trifft die algorithmische Informationstheorie keinerlei Aussagen über Bedeutung, Wissen und ähnliche nicht mathematisch definierten Begriffe. (de) Algorithmic information theory (AIT) is a branch of theoretical computer science that concerns itself with the relationship between computation and information of computably generated objects (as opposed to stochastically generated), such as strings or any other data structure. In other words, it is shown within algorithmic information theory that computational incompressibility "mimics" (except for a constant that only depends on the chosen universal programming language) the relations or inequalities found in information theory. According to Gregory Chaitin, it is "the result of putting Shannon's information theory and Turing's computability theory into a cocktail shaker and shaking vigorously." Besides the formalization of a universal measure for irreducible information content of computably generated objects, some main achievements of AIT were to show that: in fact algorithmic complexity follows (in the self-delimited case) the same inequalities (except for a constant) that entropy does, as in classical information theory; randomness is incompressibility; and, within the realm of randomly generated software, the probability of occurrence of any data structure is of the order of the shortest program that generates it when running on a universal machine. AIT principally studies measures of irreducible information content of strings (or other data structures). Because most mathematical objects can be described in terms of strings, or as the limit of a sequence of strings, it can be used to study a wide variety of mathematical objects, including integers. One of the main motivations behind AIT is the very study of the information carried by mathematical objects as in the field of metamathematics, e.g., as shown by the incompleteness results mentioned below. Other main motivations came from surpassing the limitations of classical information theory for single and fixed objects, formalizing the concept of randomness, and finding a meaningful probabilistic inference without prior knowledge of the probability distribution (e.g., whether it is independent and identically distributed, Markovian, or even stationary). In this way, AIT is known to be basically founded upon three main mathematical concepts and the relations between them: algorithmic complexity, algorithmic randomness, and algorithmic probability. (en) La teoría algorítmica de la información, es una teoría científica de las ciencias de la computación, que en contraste con la clásica teoría de la información, se basa en la complejidad de Kolmogórov para la determinación del contenido de la información. Fue desarrollada principalmente por Gregory Chaitin, Andréi Kolmogórov y Ray Solomonoff. (es) La théorie algorithmique de l'information, initiée par Kolmogorov, Solomonov et Chaitin dans les années 1960, vise à quantifier et qualifier le contenu en information d'un ensemble de données, en utilisant la théorie de la calculabilité et la notion de machine universelle de Turing. Cette théorie permet également de formaliser la notion de complexité d'un objet, dans la mesure où l'on considère qu'un objet (au sens large) est d'autant plus complexe qu'il faut beaucoup d'informations pour le décrire, ou — à l'inverse — qu'un objet contient d'autant plus d'informations que sa description est longue. La théorie algorithmique de l'information est fondée sur cette équivalence : la description d'un objet est formalisée par un algorithme (autrement dit une machine de Turing), et sa complexité (autrement dit son contenu en information) est formalisé par certaines caractéristiques de l'algorithme : sa longueur ou son temps de calcul. Ces fondements sont différents de ceux de la théorie de l'information de Shannon : cette dernière n'utilise pas la notion de calculabilité et n'a de sens que par rapport à un ensemble statistique de données. Cependant, les deux théories sont compatibles et des liens formels entre elles peuvent être établis. Tandis que la théorie de l'information de Shannon a eu de nombreuses applications en informatique, télécommunications, traitement de signal et neurosciences computationnelles, la théorie algorithmique de l'information a été utilisée avec succès dans les domaines de la biologie, de la physique et même de la philosophie. (fr) アルゴリズム情報理論（あるごりずむじょうほうりろん、英: Algorithmic information theory）は、情報理論と計算機科学の一分野であり、計算理論や情報科学とも関連がある。グレゴリー・チャイティンによれば、「シャノンの情報理論とチューリングの計算複雑性理論をシェイカーに入れて、力いっぱいシェイクしてできたもの」である。 (ja) A teoria algorítmica da informação é um subcampo da teoria da informação e da ciência da computação que se preocupa com a relação entre computação e informação. De acordo com Gregory Chaitin, ela é "o resultado de colocar a teoria da informação de Shannon e teoria da computabilidade de Turing em uma coqueteleira, agitando-a vigorosamente". (pt) 算法信息论（Algorithmic information theory）是使用理论计算机科学的工具，研究复杂性概念的学科领域。它是信息理論的一環，关注計算與信息之間的關係。按照的说法，它是“把香农的信息论和图灵的放在调酒杯使劲摇晃的结果。” (zh) Алгоритмическая теория информации — это область информатики, которая пытается уловить суть сложности, используя инструменты из теоретической информатики. Главная идея — это определить сложность (или описательную сложность, колмогоровскую сложность, сложность Колмогорова-Хайтина) строки как длину кратчайшей программы, которая выводит заданную строку. Строки, которые могут выводиться короткими программами, рассматриваются как не очень сложные. Эта нотация удивительно глубока и может быть использована для постановки и доказательства невозможности некоторых результатов таким же образом, как это делает теорема Гёделя о неполноте и проблема зависания Тьюринга. Эта область была разработана Андреем Колмогоровым, и Грегори Хайтиным в конце 1960-х годов. Существуют несколько вариантов колмогоровской сложности или алгоритмической информации. Наиболее широко используемая базируется на саморазграничивающих программах и в основном следует Леониду Левину (1974). Принцип минимальной длины сообщения (МДС) статистического и индуктивного вывода и машинного обучения был разработан и D. M. Boulton в 1968 году. МДС — байесовская вероятность (она включает предыдущие мнения) и информационно-теоретическая. Она имеет желаемые свойства статистической инвариантности (вывод трансформируется с репараметризацией, например, таким же образом, как осуществляется перевод из полярных координат в декартовы), статистическую согласованность (даже для очень сложных проблем МДС будет сходиться к любой низлежащей модели) и эффективность (модель МДС будет сходиться к любой истинной низлежащей модели так быстро, как возможно). Кристофер Уоллес и D.L. Dowe показали формальную связь между МДС и алгоритмической теорией информации (или колмогоровской сложностью) в 1999 году. (ru) Алгоритмічна теорія інформації — це галузь інформатики, яка намагається вловити суть складності, використовуючи інструменти з теоретичної інформатики. Головна ідея — визначити складність (або описову складність, колмогоровську складність, складність Колмогорова — Хайтіна) рядка як довжину найкоротшої програми, яка виводить даний рядок. Рядки, які можуть виводитися короткими програмами, розглядаються як не дуже складні. Ця нотація напрочуд глибока і може бути використана для постановки і доведення неможливості деяких результатів так само, як це робить теорема Геделя про неповноту і проблема зупинки Тюрінга. Цю галузь наприкінці 1960-х років розробили Андрій Колмогоров, і Грегорі Хайтін. Існують кілька варіантів колмогоровської складності або алгоритмічної інформації. Найширше, переважно завдяки Леоніду Левіну (1974), використовується заснована на саморозмежовуваних програмах. Принцип мінімальної довжини повідомлення (МДП) статистичного та індуктивного виведення і машинного навчання розробили 1968 року і Д. Болтон (D. M. Boulton). МДП — баєсова ймовірність (вона включає попередні переконання) та інформаційно-теоретична. Вона має бажані властивості статистичної інваріантності (виведення трансформується з репараметризацією, наприклад, так само, як здійснюється перехід від полярних координат до декартових), статистичну узгодженість (навіть для дуже складних проблем МДП збігатиметься до будь-якої нижчої моделі) і ефективність (модель МДП збігатиметься до будь-якої істинної нижчої моделі швидко, наскільки можливо). 1999 року Крістофер Воллес і Девід Дав (David L Dowe) показали формальний зв'язок між МДП і алгоритмічною теорією інформації (або колмогоровською складністю). (uk) |
| dbo:wikiPageExternalLink | http://world.std.com/~rjs/z138.pdf https://archive.org/details/algorithmicinfor00chai http://www.scholarpedia.org/article/Algorithmic_information_theory https://pure.uva.nl/ws/files/2218357/27367_JSL89.pdf https://books.google.com/books%3Fid=OIHSBwAAQBAJ https://books.google.com/books%3Fid=PseqCAAAQBAJ https://books.google.com/books%3Fid=RQpQDwAAQBAJ&pg=PT60 https://web.archive.org/web/20161117200018/https:/www.cs.auckland.ac.nz/~chaitin/unknowable/ch6.html https://www.springer.com/gp/book/9780387955698 http://mi.mathnet.ru/eng/dan40265 http://mi.mathnet.ru/eng/ppi1039 http://mi.mathnet.ru/eng/ppi68 http://www.jucs.org/jucs_2_5/algorithmic_information_theory_open/calude_c.pdf |
| dbo:wikiPageID | 2829647 (xsd:integer) |
| dbo:wikiPageLength | 21307 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1124423332 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Caltech dbr:Bayesian_inference dbr:Probability_distribution dbr:Scholarpedia dbr:Metamathematics dbr:Algorithmic_probability dbc:Algorithmic_information_theory dbc:Randomized_algorithms dbr:Per_Martin-Löf dbr:Rigour dbr:Inductive_probability dbr:Limit_of_a_sequence dbr:Pseudorandom_ensemble dbr:Pseudorandom_generator dbr:Computability_theory dbr:Computationally_indistinguishable dbr:Consistent dbr:Measure_(mathematics) dbr:Claude_Shannon dbr:Entropy_(information_theory) dbr:Epistemology dbr:Andrey_Kolmogorov dbr:Leonid_Levin dbr:Likelihood dbr:Blum_axioms dbr:Stationary_process dbr:Computational_complexity_theory dbr:String_(computer_science) dbr:Theoretical_computer_science dbr:Theory_of_computation dbr:Data_compression dbr:Data_structure dbr:Distribution_ensemble dbr:Lebesgue_measure dbr:Alan_Turing dbr:Algorithmically_random_sequence dbc:Information_theory dbr:Normal_number dbr:Formal_system dbr:Kolmogorov_complexity dbr:Prefix_code dbr:Gregory_Chaitin dbr:Gödel's_incompleteness_theorem dbr:Halting_problem dbr:Intuition_(knowledge) dbr:Asymptotic_complexity dbr:Theory_(mathematical_logic) dbr:Ray_Solomonoff dbr:Axiom dbr:Solomonoff's_theory_of_inductive_inference dbr:Maxwell's_daemon dbr:Information dbr:Information_theory dbr:Integer dbr:Minimum_description_length dbr:Minimum_message_length dbr:Chaitin's_constant dbr:Shannon's_source_coding_theorem dbr:Markov_chain dbr:Universal_Turing_machine dbr:Programming_language dbr:Limits_of_knowledge dbr:Bayes'_rule dbr:Simplicity_theory dbr:Stochastic_process dbr:Invariance_theorem_(disambiguation) dbr:Uniform_ensemble dbr:Yongge_Wang dbr:Chaitin–Kolmogorov_randomness dbr:Independent_and_identically_distributed dbr:Inductive_inference dbr:Program_(computing) dbr:Wikt:nondeterminism |
| dbp:wikiPageUsesTemplate | dbt:Cite_techreport dbt:Cite_book dbt:Cite_journal dbt:Columns-list dbt:Main dbt:Refbegin dbt:Refend dbt:Reflist dbt:Short_description dbt:Use_mdy_dates dbt:Statistics |
| dcterms:subject | dbc:Algorithmic_information_theory dbc:Randomized_algorithms dbc:Information_theory |
| gold:hypernym | dbr:Subfield |
| rdf:type | dbo:Disease |
| rdfs:comment | La teoría algorítmica de la información, es una teoría científica de las ciencias de la computación, que en contraste con la clásica teoría de la información, se basa en la complejidad de Kolmogórov para la determinación del contenido de la información. Fue desarrollada principalmente por Gregory Chaitin, Andréi Kolmogórov y Ray Solomonoff. (es) アルゴリズム情報理論（あるごりずむじょうほうりろん、英: Algorithmic information theory）は、情報理論と計算機科学の一分野であり、計算理論や情報科学とも関連がある。グレゴリー・チャイティンによれば、「シャノンの情報理論とチューリングの計算複雑性理論をシェイカーに入れて、力いっぱいシェイクしてできたもの」である。 (ja) A teoria algorítmica da informação é um subcampo da teoria da informação e da ciência da computação que se preocupa com a relação entre computação e informação. De acordo com Gregory Chaitin, ela é "o resultado de colocar a teoria da informação de Shannon e teoria da computabilidade de Turing em uma coqueteleira, agitando-a vigorosamente". (pt) 算法信息论（Algorithmic information theory）是使用理论计算机科学的工具，研究复杂性概念的学科领域。它是信息理論的一環，关注計算與信息之間的關係。按照的说法，它是“把香农的信息论和图灵的放在调酒杯使劲摇晃的结果。” (zh) La teoria algorísmica de la informació és una branca de la informàtica teòrica que s'ocupa de la relació entre la computació i la informació d'objectes generats computacionalment (a diferència dels generats estocàsticament), com ara cadenes de caràcters o qualsevol altra estructura de dades. En altres paraules, es mostra dins de la teoria algorísmica de la informació que la incompressibilitat computacional "imita" (excepte una constant que només depèn del llenguatge de programació universal escollit) les relacions o desigualtats que es troben en la teoria de la informació. Segons Gregory Chaitin, és "el resultat de posar la teoria de la informació de Shannon i la (teoria de la computabilitat de Turing) en una coctelera i sacsejar amb força". (ca) Algorithmic information theory (AIT) is a branch of theoretical computer science that concerns itself with the relationship between computation and information of computably generated objects (as opposed to stochastically generated), such as strings or any other data structure. In other words, it is shown within algorithmic information theory that computational incompressibility "mimics" (except for a constant that only depends on the chosen universal programming language) the relations or inequalities found in information theory. According to Gregory Chaitin, it is "the result of putting Shannon's information theory and Turing's computability theory into a cocktail shaker and shaking vigorously." (en) Die algorithmische Informationstheorie ist eine Theorie aus der theoretischen Informatik, die im Gegensatz zur klassischen Informationstheorie die Kolmogorow-Komplexität zur Bestimmung des Informationsgehalts verwendet. Sie wurde im Wesentlichen von Gregory Chaitin, Andrey Kolmogorov und Ray Solomonoff entwickelt. (de) La théorie algorithmique de l'information, initiée par Kolmogorov, Solomonov et Chaitin dans les années 1960, vise à quantifier et qualifier le contenu en information d'un ensemble de données, en utilisant la théorie de la calculabilité et la notion de machine universelle de Turing. Ces fondements sont différents de ceux de la théorie de l'information de Shannon : cette dernière n'utilise pas la notion de calculabilité et n'a de sens que par rapport à un ensemble statistique de données. Cependant, les deux théories sont compatibles et des liens formels entre elles peuvent être établis. (fr) Алгоритмическая теория информации — это область информатики, которая пытается уловить суть сложности, используя инструменты из теоретической информатики. Главная идея — это определить сложность (или описательную сложность, колмогоровскую сложность, сложность Колмогорова-Хайтина) строки как длину кратчайшей программы, которая выводит заданную строку. Строки, которые могут выводиться короткими программами, рассматриваются как не очень сложные. Эта нотация удивительно глубока и может быть использована для постановки и доказательства невозможности некоторых результатов таким же образом, как это делает теорема Гёделя о неполноте и проблема зависания Тьюринга. (ru) Алгоритмічна теорія інформації — це галузь інформатики, яка намагається вловити суть складності, використовуючи інструменти з теоретичної інформатики. Головна ідея — визначити складність (або описову складність, колмогоровську складність, складність Колмогорова — Хайтіна) рядка як довжину найкоротшої програми, яка виводить даний рядок. Рядки, які можуть виводитися короткими програмами, розглядаються як не дуже складні. Ця нотація напрочуд глибока і може бути використана для постановки і доведення неможливості деяких результатів так само, як це робить теорема Геделя про неповноту і проблема зупинки Тюрінга. (uk) |
| rdfs:label | Algorithmic information theory (en) Teoria Algorísmica de la Informació (ca) Algorithmische Informationstheorie (de) Teoría algorítmica de la información (es) Théorie algorithmique de l'information (fr) アルゴリズム情報理論 (ja) Teoria algorítmica da informação (pt) Алгоритмическая теория информации (ru) Алгоритмічна теорія інформації (uk) 算法信息论 (zh) |
| owl:sameAs | freebase:Algorithmic information theory yago-res:Algorithmic information theory wikidata:Algorithmic information theory dbpedia-bg:Algorithmic information theory dbpedia-ca:Algorithmic information theory dbpedia-de:Algorithmic information theory dbpedia-es:Algorithmic information theory dbpedia-fa:Algorithmic information theory dbpedia-fr:Algorithmic information theory dbpedia-ja:Algorithmic information theory dbpedia-pt:Algorithmic information theory dbpedia-ru:Algorithmic information theory dbpedia-simple:Algorithmic information theory dbpedia-sr:Algorithmic information theory dbpedia-tr:Algorithmic information theory dbpedia-uk:Algorithmic information theory http://uz.dbpedia.org/resource/Algoritmik_axborot_nazariyasi dbpedia-vi:Algorithmic information theory dbpedia-zh:Algorithmic information theory https://global.dbpedia.org/id/i97o |
| prov:wasDerivedFrom | wikipedia-en:Algorithmic_information_theory?oldid=1124423332&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Algorithmic_information_theory |
| is dbo:academicDiscipline of | dbr:Peter_Gacs |
| is dbo:wikiPageDisambiguates of | dbr:AIT dbr:Algorithmic |
| is dbo:wikiPageRedirects of | dbr:History_of_algorithmic_information_theory dbr:Algorithmic_Information_Theory dbr:Algorithmic_information dbr:Kolmogorov-Chaitin_information_theory dbr:Kolmogorov–Chaitin_information_theory |
| is dbo:wikiPageWikiLink of | dbr:List_of_computability_and_complexity_topics dbr:List_of_computer_scientists dbr:Time_series dbr:Algorithmic_probability dbr:History_of_algorithmic_information_theory dbr:List_of_important_publications_in_computer_science dbr:List_of_important_publications_in_theoretical_computer_science dbr:Per_Martin-Löf dbr:Peter_Gacs dbr:Universality_probability dbr:Index_of_information_theory_articles dbr:Inductive_probability dbr:Information_and_Computation dbr:List_of_mathematical_proofs dbr:Science_and_technology_in_Romania dbr:Cristian_S._Calude dbr:Mathematical_beauty dbr:Mathematical_constant dbr:Esoteric_programming_language dbr:General_semantics dbr:Low-complexity_art dbr:Claus_P._Schnorr dbr:Glossary_of_artificial_intelligence dbr:Gottfried_Wilhelm_Leibniz dbr:Confusion_and_diffusion dbr:Andrey_Kolmogorov dbr:Complexity dbr:Computational_mathematics dbr:Computer_science dbr:Theoretical_computer_science dbr:Active_networking dbr:Data_compression dbr:Data_compression_ratio dbr:K-trivial_set dbr:Language_identification dbr:List_of_Bronx_High_School_of_Science_alumni dbr:Algorithmically_random_sequence dbr:Causal_inference dbr:Foundations_of_mathematics dbr:Hans_Grassmann dbr:History_of_randomness dbr:Kolmogorov_complexity dbr:Kolmogorov_structure_function dbr:Michael_Dinneen dbr:Ludwig_Staiger dbr:Randomness dbr:AIT dbr:Gregory_Chaitin dbr:Gödel's_incompleteness_theorems dbr:Ashot_Petrosian dbr:Aesthetics dbr:Charles_H._Bennett_(physicist) dbr:Karl_Svozil dbr:Large_numbers dbr:Ray_Solomonoff dbr:Solomonoff's_theory_of_inductive_inference dbr:Inductive_reasoning dbr:Information dbr:Information_theory dbr:Algorithmic dbr:Algorithmic_Information_Theory dbr:Algorithmic_complexity dbr:Minimum_description_length dbr:Minimum_message_length dbr:Chaitin's_constant dbr:Undecidable_problem dbr:Variety_(cybernetics) dbr:Viable_system_model dbr:Richard's_paradox dbr:Software_entropy dbr:Sophistication_(complexity_theory) dbr:Outline_of_artificial_intelligence dbr:Outline_of_computer_programming dbr:Structural_information_theory dbr:Turing_completeness dbr:Yongge_Wang dbr:Algorithmic_information dbr:Kolmogorov-Chaitin_information_theory dbr:Kolmogorov–Chaitin_information_theory |
| is foaf:primaryTopic of | wikipedia-en:Algorithmic_information_theory |