И всё же кажется, что в каком-то смысле уравнения Максвелла проще, чем человеческий мозг, или чем швыряющий-молнии-агент.
Вот разгадка: как выяснилось, намного проще написать компьютерную программу, симулирующую уравнения Максвелла, чем компьютерную программу, симулирующую пронизанный эмоциями разумный мозг Тора.
В алгоритмической теории информации «сложность описания» измеряется длиной кратчайшей компьютерной программы, выводящей это описание. Прежде чем говорить о «кратчайшей компьютерной программе», нужно задать пространство компьютерных программ, для чего нужен язык и интерпретатор. Индукция Соломонова использует машины Тьюринга (точнее, последовательности битов, задающие машины Тьюринга). Что делать, если тебе не нравятся машины Тьюринга? Можешь заплатить некоторый фиксированный штраф за сложность и спроектировать универсальную машину Тьюринга, которая будет интерпретировать любой код на том языке, который тебе нравится. Штраф за сложность зависит лишь от размера универсального интерпретатора для выбранного языка программирования, и поэтому различные формулировки в некотором смысле совершенно равносильны.
На мой взгляд, лучшая формулировка индукции Соломонова — требующая, чтобы компьютерная программа делала не детерминистическое предсказание, а приписывала строкам вероятности. Например, программа, объясняющая поведение симметричной монеты, будет просто приписывать одинаковую вероятность всем 2N2N строкам длины NN. Как понимать «объясняющая поведение» или «не противоречащая данным»? Чем больше вероятность, которую программа приписывает полученным данным, тем лучше программа их «объясняет». И сумма всех вероятностей должна равняться единице, и поэтому, чтобы лучше «объяснить» одну возможность, программа должна забрать сколько-то вероятностной меры у другой возможности, и теперь она будет «объяснять» её хуже. Монета не может в 100% случаев выпадать орлом, и в 100% случаев выпадать решкой.
Что можно сказать про оптимальный компромисс между сложностью программы и её способностью объяснять данные? Если забыть о сложности и думать только об объяснении, то лучшими будут программы, предсказывающие данные детерминистически, то есть приписывающие им 100% вероятность. Если монета выпала «ОРРООР», то программа, заявляющая, что монета фиксирована и изначально должна была показать «ОРРООР», объясняет данные в 64 раза лучше, чем программа, считающая монету симметричной. С другой стороны, если рассматривать только сложность, то гипотеза о симметричной монете всегда проще любой другой гипотезы. Даже если монета выпадает «ОРООРОООРООООРОООООР…». Гипотеза «монета симметрична» действительно проще и объясняет эту последовательность точно также хорошо, как и любую другую последовательность из 20 бросков — не лучше и не хуже — но легко увидеть другую гипотезу, выглядящую не слишком уж сложной, и объясняющую эти наблюдение намного лучше.
Программа, которой позволили хранить дополнительный бит информации, способна в два раза урезать пространство возможностей, и, следовательно, приписать в два раза больше вероятности точкам в оставшемся пространстве. Отсюда выходит, что один бит сложности должен стоить как минимум двукратного улучшения способности объяснять. Поэтому программа, в явном виде хранящая инструкцию «приписать ОРРООР 100% и 0% всем остальным», не сможет выиграть у всех остальных программ. Шесть бит, отведённые на хранение «ОРРООР» сводят на нет всю достоверность, полученную 64-кратным улучшением способности объяснять. Иначе, рано или поздно, придётся решить, что все симметричные монеты фиксированы.
Если, конечно, эта программа не написана умно, и не пытается сжать строки данных. Во всех остальных случаях перемещение информации из данных в код не помогает укрепить достоверность программы.
Как именно работает индукция Соломонова? Нужно расcмотреть все допустимые программы (если допустима любая программа, то индукция становится невычислимой), причём каждая программа имеет априорную вероятность, равную (1/2)N(1/2)N, где NN — её длина в битах, а затем вероятность корректируется, исходя из того, насколько хорошо программа объясняет данные на текущий момент. В результате получается группа «экспертов» различной степени достоверности, могущая предсказывать следующие биты: просто просуммируй мнения, умножив их на весовой коэффициент авторитета.
Принцип минимальной длины сообщения почти эквивалентен индукции Соломонова. Сначала ты посылаешь строку, описывающую код, а затем строку, описывающую данные, используя этот код. Объяснение, создающее кратчайшее суммарное сообщение, считается лучшим. Если приравнять набор возможных кодов к пространству всех компьютерных программ и считать сообщение-с-определениями универсальным интерпретатором, то принцип минимальной длины сообщения почти эквивалентен индукции Соломонова (почти — потому, что он выбирает кратчайшую программу, а не суммирует все возможные программы).