Войти
Теория алгоритмической информации (AIT) - это раздел теоретической информатики, который занимается связь между вычислением и информацией вычислимо сгенерированных объектов (в отличие от стохастически сгенерированных), таких как строки или любая другая структура данных. Другими словами, в рамках алгоритмической теории информации показано, что вычислительная несжимаемость «имитирует» (за исключением константы, которая зависит только от выбранного универсального языка программирования) отношения или неравенства, обнаруженные в теории информации. Согласно Грегори Чейтину, это «результат помещения теории информации Шеннона и теории вычислимости Тьюринга в коктейль-шейкер и сильного тряски».
Теория алгоритмической информации в основном изучает меры несводимого информационного содержания строк (или других структур данных ). Поскольку большинство математических объектов можно описать в терминах строк или как предел последовательности строк, его можно использовать для изучения широкого спектра математических объектов, включая целые числа. В самом деле, одним из основных мотивов AIT является само изучение информации, переносимой математическими объектами, как, например, в области метаматематики, как, например, показывают результаты неполноты, упомянутые ниже. Другие основные мотивы исходили от: преодоления ограничений классической теории информации для отдельных и фиксированных объектов; формализация понятия случайности ; и нахождение значимого вероятностного вывода без предварительного знания распределения вероятностей (например, является ли оно независимым и одинаково распределенным, марковским, или даже стационарный ).
Таким образом, известно, что в основе AIT лежат три основных математических понятия и взаимосвязи между ними: алгоритмическая сложность, алгоритмическая случайность и алгоритмическая вероятность.
Помимо формализации универсальной меры несводимого информационного содержания вычислимых объектов, некоторые основные достижения AIT заключались в том, чтобы показать, что: на самом деле алгоритмическая сложность следует (в случае саморазграничения ) те же неравенства (кроме константы), которые выполняет энтропия, как в классической теории информации; случайность - несжимаемость; а в области случайно сгенерированного программного обеспечения вероятность появления любой структуры данных имеет порядок кратчайшей программы, которая ее генерирует при запуске на универсальной машине.
Теория алгоритмической информации в основном изучает сложность измеряет строки (или другие структуры данных ). Поскольку большинство математических объектов можно описать в терминах строк или как предел последовательности строк, его можно использовать для изучения широкого спектра математических объектов, включая целые числа.
Неформально, с точки зрения алгоритмической теории информации, информационное содержание строки эквивалентно длине наиболее- сжатого возможного автономного представления этой строки. Автономное представление - это, по сути, программа - в некотором фиксированном, но в остальном несущественном универсальном языке программирования - которая при запуске выводит исходную строку.
С этой точки зрения энциклопедия на 3000 страниц на самом деле содержит меньше информации, чем 3000 страниц полностью случайных букв, несмотря на то, что энциклопедия намного полезнее. Это потому, что для восстановления всей последовательности случайных букв нужно более или менее знать, что такое каждая буква. С другой стороны, если бы все гласные были удалены из энциклопедии, кто-то с достаточным знанием английского языка мог бы восстановить их, так же как можно было бы восстановить предложение «Ths sntnc hs lw nfrmtn cntnt» из контекста и присутствующих согласных.
В отличие от классической теории информации, алгоритмическая теория информации дает формальные, строгие определения случайной строки и случайной бесконечной последовательности, которые не зависят от физической или философской интуиции о недетерминизме или вероятности. (Набор случайных строк зависит от выбора универсальной машины Тьюринга, используемой для определения сложности Колмогорова, но любой выбор дает идентичные асимптотические результаты, потому что сложность Колмогорова строки инвариантна до к аддитивной константе, зависящей только от выбора универсальной машины Тьюринга. По этой причине набор случайных бесконечных последовательностей не зависит от выбора универсальной машины.)
Некоторые результаты алгоритмической теории информации, такие как Теорема Чайтина о неполноте, похоже, бросает вызов общепринятым математическим и философским интуициям. Наиболее примечательным среди них является построение константы Чейтина Ω, действительного числа, которое выражает вероятность того, что саморазграничивающая универсальная машина Тьюринга остановит, когда ее вход будет обеспечен переворотом ярмарки. монета (иногда рассматривается как вероятность того, что случайная компьютерная программа в конечном итоге остановится). Хотя Ω легко определить, в любой согласованной аксиоматизируемой теории можно вычислить только конечное количество цифр Ω, так что это в некотором смысле непознаваемо, обеспечивая абсолютный предел знания, который напоминает теорему Гёделя о неполноте. Хотя цифры Ω не могут быть определены, многие свойства Ω известны; например, это алгоритмически случайная последовательность, и поэтому ее двоичные цифры распределены равномерно (на самом деле это нормальный ).
Теория алгоритмической информации была основана Рэем Соломонофф, который опубликовал основные идеи, на которых основана эта область, как часть своего изобретения алгоритмической вероятности. - способ преодоления серьезных проблем, связанных с применением правил Байеса в статистике. Впервые он описал свои результаты на конференции в Калифорнийском технологическом институте в 1960 г. и в отчете в феврале 1960 г. «Предварительный отчет по общей теории индуктивного вывода». Позднее алгоритмическая теория информации была независимо разработана Андреем Колмогоровым в 1965 году и Григорием Чайтиным примерно в 1966 году.
Существует несколько вариантов колмогоровской сложности или алгоритмической информации; наиболее широко используемый основан на программах с саморазграничением и в основном связан с Леонидом Левином (1974). Пер Мартин-Лёф также внес значительный вклад в теорию информации бесконечных последовательностей. Аксиоматический подход к алгоритмической теории информации, основанный на аксиомах Блюма (Blum 1967), был представлен Марком Бургином в статье, представленной для публикации Андреем Колмогоровым (Burgin 1982). Аксиоматический подход охватывает другие подходы в алгоритмической теории информации. Можно трактовать различные меры алгоритмической информации как частные случаи аксиоматически определенных мер алгоритмической информации. Вместо того, чтобы доказывать аналогичные теоремы, такие как основная теорема инвариантности, для каждой конкретной меры, можно легко вывести все такие результаты из одной соответствующей теоремы, доказанной в аксиоматической ситуации. Это общее преимущество аксиоматического подхода в математике. Аксиоматический подход к алгоритмической теории информации получил дальнейшее развитие в книге (Burgin 2005) и применен к программным метрикам (Burgin and Debnath, 2003; Debnath and Burgin, 2003).
Двоичная строка называется случайной, если колмогоровская сложность строки равна по крайней мере длине строки. Простой аргумент подсчета показывает, что некоторые строки любой заданной длины случайны, и почти все строки очень близки к случайным. Поскольку сложность Колмогорова зависит от фиксированного выбора универсальной машины Тьюринга (неформально фиксированного «языка описания», на котором даются «описания»), набор случайных строк действительно зависит от выбора фиксированной универсальной машины. Тем не менее, набор случайных строк в целом имеет одинаковые свойства независимо от фиксированной машины, поэтому можно (и часто так и происходит) говорить о свойствах случайных строк как группы без необходимости сначала указывать универсальную машину.
Бесконечная двоичная последовательность называется случайной, если для некоторой константы c для всех n сложность Колмогорова начального сегмента длины n последовательности не менее n - c. Можно показать, что почти каждая последовательность (с точки зрения стандартной меры - «честная монета» или меры Лебега - в пространстве бесконечных двоичных последовательностей) случайна. Кроме того, поскольку можно показать, что сложность Колмогорова относительно двух разных универсальных машин отличается не более чем на константу, набор случайных бесконечных последовательностей не зависит от выбора универсальной машины (в отличие от конечных строк). Это определение случайности обычно называется случайностью Мартина-Лёфа после Пер Мартин-Лёф, чтобы отличить его от других подобных понятий случайности. Его также иногда называют 1-случайностью, чтобы отличить его от других более сильных представлений о случайности (2-случайность, 3-случайность и т. Д.). Помимо концепций случайности Мартина-Лёфа, существуют также рекурсивная случайность, случайность Шнорра, случайность Курца и т. Д. Юнгге Ван показал, что все эти концепции случайности различны.
(Связанные определения могут быть сделаны для алфавитов, отличных от набора 
Теория алгоритмической информации (AIT) - это теория информации об отдельных объектах, основанная на информатике и рассматривающая взаимосвязь между вычислениями, информацией и случайностью.
Информационное содержание или сложность объекта можно измерить длиной его кратчайшего описания. Например, строка
«01010101010101010101010101010101010101010101010101010101010101»
имеет краткое описание «32 повторения '01'», а
«110010000110000111011110111011001111101000010010010101, кроме самого простого описания», кроме самого простого.
Более формально алгоритмическая сложность (AC) строки x определяется как длина самой короткой программы, которая вычисляет или выводит x, где программа выполняется на некотором фиксированном эталонном универсальном компьютере.
Тесно связанное с этим понятие - вероятность того, что универсальный компьютер выдаст некоторую строку x, когда ему подадут произвольно выбранную программу. Эта алгоритмическая «вероятность Соломонова» (AP) является ключом к формальному решению старой философской проблемы индукции.
Главный недостаток AC и AP - их несовместимость. Ограниченная по времени сложность «Левина» наказывает медленную программу, добавляя логарифм времени ее выполнения к ее длине. Это приводит к вычислимым вариантам AC и AP, а универсальный поиск «Левин» (США) решает все задачи инверсии за оптимальное время (за исключением некоторой нереально большой мультипликативной постоянной).
AC и AP также позволяют формальное и строгое определение случайности отдельных строк, чтобы не зависеть от физических или философских интуиций о недетерминировании или вероятности. Грубо говоря, строка является алгоритмической случайностью Мартина-Лёфа (AR), если она несжимаема в том смысле, что ее алгоритмическая сложность равна ее длине.
AC, AP и AR являются основными дисциплинами AIT, но AIT появляется во многих других областях. Он служит основой принципа минимальной длины описания (MDL), может упростить доказательства в теории вычислительной сложности, использовался для определения универсальной метрики сходства между объектами, решает проблему демона Максвелла и многие другие..
