Алгоритмічна теорія інформації
Алгоритмічна теорія інформації — це галузь інформатики, яка намагається вловити суть складності, використовуючи інструменти з теоретичної інформатики. Головна ідея — визначити складність (або описову складність, колмогоровську складність, складність Колмогорова — Хайтіна) рядка як довжину найкоротшої програми, яка виводить даний рядок. Рядки, які можуть виводитися короткими програмами, розглядаються як не дуже складні. Ця нотація напрочуд глибока і може бути використана для постановки і доведення неможливості деяких результатів так само, як це робить теорема Геделя про неповноту і проблема зупинки Тюрінга.
Цю галузь наприкінці 1960-х років розробили Андрій Колмогоров, Рей Соломонофф[en] і Грегорі Хайтін. Існують кілька варіантів колмогоровської складності або алгоритмічної інформації. Найширше, переважно завдяки Леоніду Левіну (1974), використовується заснована на саморозмежовуваних програмах.
Принцип мінімальної довжини повідомлення (МДП) статистичного та індуктивного виведення і машинного навчання розробили 1968 року Крістофер Воллес[en] і Д. Болтон (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.]
В іншому мовному розділі є повніша стаття Algorithmic information theory(англ.). Ви можете допомогти, розширивши поточну статтю за допомогою перекладу з англійської.
|