Алгоритмическая теория информации
Материал из Википедии — свободной энциклопедии
В информатике, алгоритмическая теория информации — это область знаний, которая пытается уловить суть сложности используя инструменты из теоретической информатики. Главная идея — это определить сложность (или описательная сложность, Колмогоровская сложность или также сложность Колмогорова-Чейтина) строки как длину кратчайшей программы, которая выводит заданную строку. Строки, которые могут выводиться короткими программами рассматриваются, как не очень сложные. Эта нотация удивительно глубока и может быть использована для постановки и доказательства невозможности некоторых результатов, таким-же образом как это делает теорема Гёделя о неполноте и проблема зависания Тьюринга.
Эта область была разработана Андреем Колмогоровым, Рэем Соломоновым и Григорием Чейтиным в конце 1960-х годов. Существуют несколько вариантов Колмогоровской сложности или алгоритмической информации. Наиболее широко используемая базируется на саморазграничивающих программах и в в основном следует Леониду Левину (1974).
Для формализации данного выше определения сложности определим какие типы программ являются допустимыми. К счастью это не имеет особого значения: как мы увидим позже, любой может выбрать особую нотацию для машины Тьюринга, или программы на языке LISP, или программы на языке Pascal, или в байткоде виртуальной машины Java.
Принцип минимальной длины сообщения (МДС) статистического и индуктивного вывода и машинного обучения был разработан Кристофером Уоллесом и D.M. Boulton в 1968 году. МДС — байесовская вероятность (она включает предыдущие мнения) и информационно-теоретическая. Она имеет желаемые свойства статистической инвариантности (вывод трансформируется с репараметризацией, например, таким-же образом как осуществляется перевод из полярных координат в декартовы), статистическую согласованность (даже для очень сложных проблем, МДС будет сходиться к любой низлежащей модели) и эффективность (модель МДС будет сходиться к любой истинной низлежащей модели так быстро как возможно). Кристофер Уоллес и D.L. Dowe показали формальную связь между МДС и алгоритмической теорией информации (или Колмогоровской сложностью) в 1999 году.
[править] См. также
- Колмогоровская сложность
- Важные публикации в алгоритмической теории информации (англ.)
- минимальная длина сообщения
[править] Внешние ссылки
- 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.
- Kolmogorov Complexity provides a simple explanation of Kolmogorov complexity.
- Algorithmic Information Theory (pdf).
