Алгоритмічна теорія інформації

Теорія інформації
Ентропія Диференціальна ентропія Умовна ентропія Спільна ентропія Взаємна інформація Умовна взаємна інформація Відносна ентропія Ентропійна швидкість
Властивість асимптотичної рівнорозподіленості Швидкість–спотворення
Теорема Шеннона про кодування джерела Пропускна здатність каналу Теорема про кодування для зашумленого каналу Теорема Шеннона — Гартлі Алгоритмічна теорія інформації

Алгоритмічна теорія інформації — це галузь інформатики, яка намагається вловити суть складності, використовуючи інструменти з теоретичної інформатики. Головна ідея — визначити складність (або описову складність, колмогоровську складність, складність Колмогорова — Хайтіна) рядка як довжину найкоротшої програми, яка виводить даний рядок. Рядки, які можуть виводитися короткими програмами, розглядаються як не дуже складні. Ця нотація напрочуд глибока і може бути використана для постановки і доведення неможливості деяких результатів так само, як це робить теорема Геделя про неповноту і проблема зупинки Тюрінга.

Цю галузь наприкінці 1960-х років розробили Андрій Колмогоров, Рей Соломонофф і Грегорі Хайтін. Існують кілька варіантів колмогоровської складності або алгоритмічної інформації. Найширше, переважно завдяки Леоніду Левіну (1974), використовується заснована на саморозмежовуваних програмах.

Принцип мінімальної довжини повідомлення (МДП) статистичного та індуктивного виведення і машинного навчання розробили 1968 року Крістофер Воллес і Д. Болтон (D. M. Boulton). МДП — баєсова ймовірність (вона включає попередні переконання) та інформаційно-теоретична. Вона має бажані властивості статистичної інваріантності (виведення трансформується з репараметризацією, наприклад, так само, як здійснюється перехід від полярних координат до декартових), статистичну узгодженість (навіть для дуже складних проблем МДП збігатиметься до будь-якої нижчої моделі) і ефективність (модель МДП збігатиметься до будь-якої істинної нижчої моделі швидко, наскільки можливо). 1999 року Крістофер Воллес і Девід Дав (David L Dowe) показали формальний зв'язок між МДП і алгоритмічною теорією інформації (або колмогоровською складністю).

Див. також

• Колмогоровська складність

Посилання

• The Legacy of Andrei Nikolaevich Kolmogorov
• Chaitin's online publications
• Solomonoff's IDSIA page [Архівовано 14 червня 2006 у Wayback Machine.]
• Schmidhuber's generalizations of algorithmic information [Архівовано 18 травня 2006 у Wayback Machine.]
• Li & Vitanyi's textbook [Архівовано 14 травня 2006 у Wayback Machine.]
• Tromp's lambda calculus computer model offers a concrete definition of K()
• Minimum Message Length and Kolmogorov Complexity^{[недоступне посилання з Май 2018]} (by C.S. Wallace^{[недоступне посилання з Июль 2019]} and D.L. Dowe [Архівовано 12 лютого 2006 у Wayback Machine.], Computer Journal, Vol. 42, No. 4, 1999).
• David Dowe [Архівовано 12 лютого 2006 у Wayback Machine.]'s Minimum Message Length (MML) [Архівовано 9 лютого 2006 у Wayback Machine.] and Occam's razor [Архівовано 16 травня 2006 у Wayback Machine.] pages.
• P. Grunwald, M. A. Pitt and I. J. Myung (ed.), °FF-A2ED-02 °FC49FEBE7C&ttype=2&tid=10478 Advances in Minimum Description Length: Theory and Applications^{[недоступне посилання з Май 2018]}, M.I.T. Press, April 2005, ISBN 0-262-07262-9.
• Algorithmic Information Theory (pdf).
• Вяткін В. Б. [Архівовано 28 липня 2021 у Wayback Machine.] Задача оцінки негентропії відображення системних об'єктів та традиційні підходи до кількісного визначення інформації (матеріали з дисертації) [Архівовано 28 липня 2021 у Wayback Machine.]