| 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)
|
| 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)
|