Алгоритмическая теория информации — это область информатики, которая пытается уловить суть сложности, используя инструменты из теоретической информатики. Главная идея — это определить сложность (или описательную сложность, колмогоровскую сложность, сложность Колмогорова-Хайтина) строки как длину кратчайшей программы, которая выводит заданную строку. Строки, которые могут выводиться короткими программами, рассматриваются как не очень сложные. Эта нотация удивительно глубока и может быть использована для постановки и доказательства невозможности некоторых результатов таким же образом, как это делает теорема Гёделя о неполноте и проблема остановки Тьюринга.
Эта область была разработана Андреем Колмогоровым, и Грегори Хайтиным в конце 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). Вяткин В.Б. Задача оценки негэнтропии отражения системных объектов и традиционные подходы к количественному определению информации (материалы из диссертации)
*