Алгоритмічна теорія інформації — це галузь інформатики, яка намагається вловити суть складності, використовуючи інструменти з теоретичної інформатики. Головна ідея — визначити складність (або описову складність, колмогоровську складність, складність Колмогорова — Хайтіна) рядка як довжину найкоротшої програми, яка виводить даний рядок. Рядки, які можуть виводитися короткими програмами, розглядаються як не дуже складні. Ця нотація напрочуд глибока і може бути використана для постановки і доведення неможливості деяких результатів так само, як це робить теорема Геделя про неповноту і проблема зупинки Тюрінга.
Цю галузь наприкінці 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 (by C.S. Wallace 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, M.I.T. Press, April 2005, ISBN 0-262-07262-9. Algorithmic Information Theory (pdf). Вяткін В. Б. Задача оцінки негентропії відображення системних об'єктів та традиційні підходи до кількісного визначення інформації (матеріали з дисертації)