Алгоритмічна теорія інформації
Алгоритмічна теорія інформації — це галузь інформатики, яка намагається вловити суть складності, використовуючи інструменти з теоретичної інформатики. Головна ідея — визначити складність (або описову складність, колмогоровську складність, складність Колмогорова — Хайтіна) рядка як довжину найкоротшої програми, яка виводить даний рядок. Рядки, які можуть виводитися короткими програмами, розглядаються як не дуже складні. Ця нотація напрочуд глибока і може бути використана для постановки і доведення неможливості деяких результатів так само, як це робить теорема Геделя про неповноту і проблема зупинки Тюрінга.
| Теорія інформації |
|---|
 |
|
|
|
Цю галузь наприкінці 1960-х років розробили Андрій Колмогоров, Рей Соломонофф і Грегорі Хайтін. Існують кілька варіантів колмогоровської складності або алгоритмічної інформації. Найширше, переважно завдяки Леоніду Левіну (1974), використовується заснована на саморозмежовуваних програмах.
Принцип мінімальної довжини повідомлення (МДП) статистичного та індуктивного виведення і машинного навчання розробили 1968 року Крістофер Воллес і Д. Болтон (D. M. Boulton). МДП — баєсова ймовірність (вона включає попередні переконання) та інформаційно-теоретична. Вона має бажані властивості статистичної інваріантності (виведення трансформується з репараметризацією, наприклад, так само, як здійснюється перехід від полярних координат до декартових), статистичну узгодженість (навіть для дуже складних проблем МДП збігатиметься до будь-якої нижчої моделі) і ефективність (модель МДП збігатиметься до будь-якої істинної нижчої моделі швидко, наскільки можливо). 1999 року Крістофер Воллес і Девід Дав (David L Dowe) показали формальний зв'язок між МДП і алгоритмічною теорією інформації (або колмогоровською складністю).
Див. також
- Колмогоровська складність
- Важливі публікації з алгоритмічної теорії інформації
Посилання
- The Legacy of Andrei Nikolaevich Kolmogorov
- Chaitin's online publications
- Solomonoff's IDSIA page
- Schmidhuber's generalizations of algorithmic information
- Li & Vitanyi's textbook
- 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, Computer Journal, Vol. 42, No. 4, 1999).
- David Dowe's Minimum Message Length (MML) and Occam's razor 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).
- Вяткін В. Б. Задача оцінки негентропії відображення системних об'єктів та традиційні підходи до кількісного визначення інформації (матеріали з дисертації)