Алгоритмическая теория информации: вычисления, сложность и случайность.
Algorithmic information theory
Алгоритмическая теория информации: связь вычислений и информации. Изучает сложность данных, сжимаемость, случайность и роль универсальных машин Тьюринга.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Подполе теории информации и информатики.
Subfield of information theory and computer science
Алгоритмическая теория информации (AIT) — это раздел теоретической информатики, изучающий взаимосвязь между вычислениями и информацией, содержащейся в вычислимо генерируемых объектах (в отличие от стохастически генерируемых), таких как строки или любые другие структуры данных. Иными словами, в алгоритмической теории информации показано, что вычислимая несжимаемость "имитирует" (с точностью до константы, зависящей только от выбранного универсального языка программирования) соотношения или неравенства, встречающиеся в теории информации. По словам Грегори Чейтина, это "результат смешивания теории информации Шеннона и теории вычислимости Тьюринга в коктейльном шейкере и энергичного взбалтывания". Помимо формализации универсальной меры для несводимого информационного содержания вычислимо генерируемых объектов, основными достижениями AIT стали доказательства того, что: алгоритмическая сложность, в самоограниченном случае, подчиняется тем же неравенствам (с точностью до константы), что и энтропия в классической теории информации; и в области случайно генерируемого программного обеспечения вероятность появления любой структуры данных пропорциональна длине кратчайшей программы, генерирующей её на универсальной машине. AIT в основном изучает меры несводимого информационного содержания строк (или других структур данных). Поскольку большинство математических объектов можно описать в терминах строк или как предел последовательности строк, она может быть использована для изучения широкого спектра математических объектов, включая целые числа. Одной из главных мотиваций для развития AIT является изучение информации, содержащейся в математических объектах, в области метаматематики, как это демонстрируют, например, результаты о неполноте, упомянутые ниже. Другие важные мотивы возникли из-за преодоления ограничений классической теории информации применительно к отдельным и фиксированным объектам, формализации понятия случайности и поиска осмысленного вероятностного вывода без априорных знаний о распределении вероятностей (например, независимо от того, является ли оно независимым и одинаково распределенным, марковским или даже стационарным). Таким образом, AIT базируется на трех основных математических концепциях и связях между ними: алгоритмической сложности, алгоритмической случайности и алгоритмической вероятности. Идеи, лежащие в основе этой области, были впервые опубликованы в связи с изобретением алгоритмической вероятности — метода преодоления серьезных проблем, связанных с применением правил Байеса в статистике. Он впервые представил свои результаты на конференции в Калтехе в 1960 году и в отчете за февраль 1960 года под названием "Предварительный доклад об общей теории индуктивного вывода". Алгоритмическая теория информации была позже независимо разработана Андреем Колмогоровым в 1965 году и Грегорием Чейтиным около 1966 года. Существует несколько вариантов сложности Колмогорова или алгоритмической информации; наиболее распространенный основан на самоограничивающих программах и в значительной степени связан с именем Леонида Левина (1974). Пер Мартин Лёф также внес значительный вклад в теорию информации бесконечных последовательностей. Аксиоматический подход к алгоритмической теории информации, основанный на аксиомах Блума (Blum 1967), был предложен Марком Бургином в статье, представленной для публикации Андреем Колмогоровым (Burgin 1982). Аксиоматический подход охватывает другие подходы в алгоритмической теории информации. Различные меры алгоритмической информации можно рассматривать как частные случаи аксиоматически определенных мер алгоритмической информации. Вместо доказательства подобных теорем, таких как основная теорема инвариантности, для каждой конкретной меры, можно легко вывести все такие результаты из одной соответствующей теоремы, доказанной в аксиоматическом контексте. Это общее преимущество аксиоматического подхода в математике. Аксиоматический подход к алгоритмической теории информации был далее развит в книге (Burgin 2005) и применен к метрикам программного обеспечения (Burgin and Debnath, 2003; Debnath and Burgin, 2003).
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; 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. who published the basic ideas on which the field is based as part of his invention of algorithmic probability—a way to overcome serious problems associated with the application of Bayes' rules in statistics. He first described his results at a Conference at Caltech in 1960, and in a report, February 1960, "A Preliminary Report on a General Theory of Inductive Inference." Algorithmic information theory was later developed independently by Andrey Kolmogorov, in 1965 and Gregory Chaitin, around 1966. There are several variants of Kolmogorov complexity or algorithmic information; the most widely used one is based on self delimiting programs and is mainly due to Leonid Levin (1974). Per Martin Löf also contributed significantly to the information theory of infinite sequences. An axiomatic approach to algorithmic information theory based on the Blum axioms (Blum 1967) was introduced by Mark Burgin in a paper presented for publication by Andrey Kolmogorov (Burgin 1982). The axiomatic approach encompasses other approaches in the algorithmic information theory. It is possible to treat different measures of algorithmic information as particular cases of axiomatically defined measures of algorithmic information. Instead of proving similar theorems, such as the basic invariance theorem, for each particular measure, it is possible to easily deduce all such results from one corresponding theorem proved in the axiomatic setting. This is a general advantage of the axiomatic approach in mathematics. The axiomatic approach to algorithmic information theory was further developed in the book (Burgin 2005) and applied to software metrics (Burgin and Debnath, 2003; Debnath and Burgin, 2003).
Точные определения
Двоичная строка называется случайной, если сложность Колмогорова строки не меньше длины строки. Простой аргумент подсчёта показывает, что некоторые строки любой заданной длины являются случайными, и почти все строки очень близки к случайности. Поскольку сложность Колмогорова зависит от фиксированного выбора универсальной машины Тьюринга (неформально, фиксированного "языка описания", на котором даются "описания"), множество случайных строк действительно зависит от выбора фиксированной универсальной машины. Тем не менее, множество случайных строк в целом обладает схожими свойствами независимо от выбранной машины, поэтому можно (и часто делают) говорить о свойствах случайных строк как о группе, не указывая предварительно универсальную машину. Бесконечная двоичная последовательность называется случайной, если для некоторой константы c, для всех n, сложность Колмогорова начального сегмента длины n последовательности не меньше n − c. Можно показать, что почти каждая последовательность (с точки зрения стандартной меры – меры "честной монеты" или меры Лебега на пространстве бесконечных двоичных последовательностей) является случайной. Также, поскольку можно показать, что сложность Колмогорова относительно двух различных универсальных машин отличается не более чем на константу, множество случайных бесконечных последовательностей не зависит от выбора универсальной машины (в отличие от конечных строк). Это определение случайности обычно называют случайностью Мартина Лёфа, в честь Пера Мартина Лёфа, чтобы отличать его от других подобных понятий случайности. Иногда его также называют 1-случайностью, чтобы отличать его от других более сильных понятий случайности (2-случайность, 3-случайность и т. д.). Помимо концепций случайности Мартина Лёфа, существуют также рекурсивная случайность, случайность Шнорра и случайность Курца и т. д. Юнге Ванг показал, что все эти концепции случайности различны. (Связанные определения могут быть сформулированы для алфавитов, отличных от данного множества.)
A binary string is said to be random if the Kolmogorov complexity of the string is at least the length of the string. A simple counting argument shows that some strings of any given length are random, and almost all strings are very close to being random. Since Kolmogorov complexity depends on a fixed choice of universal Turing machine (informally, a fixed "description language" in which the "descriptions" are given), the collection of random strings does depend on the choice of fixed universal machine. Nevertheless, the collection of random strings, as a whole, has similar properties regardless of the fixed machine, so one can (and often does) talk about the properties of random strings as a group without having to first specify a universal machine. An infinite binary sequence is said to be random if, for some constant c, for all n, the Kolmogorov complexity of the initial segment of length n of the sequence is at least n − c. It can be shown that almost every sequence (from the point of view of the standard measure—"fair coin" or Lebesgue measure—on the space of infinite binary sequences) is random. Also, since it can be shown that the Kolmogorov complexity relative to two different universal machines differs by at most a constant, the collection of random infinite sequences does not depend on the choice of universal machine (in contrast to finite strings). This definition of randomness is usually called Martin Löf randomness, after Per Martin Löf, to distinguish it from other similar notions of randomness. It is also sometimes called 1 randomness to distinguish it from other stronger notions of randomness (2 randomness, 3 randomness, etc.). In addition to Martin Löf randomness concepts, there are also recursive randomness, Schnorr randomness, and Kurtz randomness etc. Yongge Wang showed that all of these randomness concepts are different. (Related definitions can be made for alphabets other than the set .)