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

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

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

Принцип минимальной длины сообщения (МДС) статистического и индуктивного вывода и машинного обучения был разработан и D. M. Boulton в 1968 году . МДС — байесовская вероятность (она включает предыдущие мнения) и информационно-теоретическая. Она имеет желаемые свойства статистической инвариантности (вывод трансформируется с репараметризацией, например, таким же образом, как осуществляется перевод из полярных координат в декартовы), статистическую согласованность (даже для очень сложных проблем МДС будет сходиться к любой низлежащей модели) и эффективность (модель МДС будет сходиться к любой истинной низлежащей модели так быстро, как возможно). Кристофер Уоллес и D.L. Dowe показали формальную связь между МДС и алгоритмической теорией информации (или колмогоровской сложностью) в 1999 году .

См. также

Колмогоровская сложность
(англ.)

Ссылки

(недоступная ссылка) (by (недоступная ссылка) and , Computer Journal, Vol. 42, No. 4, 1999).
's and pages.
P. Grunwald, M. A. Pitt and I. J. Myung (ed.), (недоступная ссылка) , M.I.T. Press, April 2005, ISBN 0-262-07262-9 .
(pdf).