Алгоритмическая теория информации

Алгоритмическая теория информации  — это область информатики, которая пытается уловить суть сложности, используя инструменты из теоретической информатики. Главная идея — это определить сложность (или описательную сложность, колмогоровскую сложность, сложность Колмогорова-Хайтина) строки как длину кратчайшей программы, которая выводит заданную строку. Строки, которые могут выводиться короткими программами, рассматриваются как не очень сложные. Эта нотация удивительно глубока и может быть использована для постановки и доказательства невозможности некоторых результатов таким же образом, как это делает теорема Гёделя о неполноте и проблема зависания Тьюринга.

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

Принцип минимальной длины сообщения (МДС) статистического и индуктивного вывода и машинного обучения был разработан Кристофером Уоллесом и 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.
• Algorithmic Information Theory (pdf).
• Вяткин В.Б. Задача оценки негэнтропии отражения системных объектов и традиционные подходы к количественному определению информации (материалы из диссертации)