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