Введение

Вероятность остановки случайной компьютерной программы

В подразделах информатики, в области алгоритмической теории информации, постоянная Чайтина (число Омега Чайтина) или вероятность остановки — это действительное число, которое, грубо говоря, представляет вероятность того, что случайно сгенерированная программа завершится. Эти числа формируются на основе построения, предложенного Грегори Чайтином. Хотя существует бесконечно много вероятностей остановки, по одной для каждого (универсального, см. ниже) метода кодирования программ, обычно используют букву Ω для обозначения их, как если бы существовала только одна. Поскольку Ω зависит от используемого кодирования программы, его иногда называют построением Чайтина, когда речь не идет о каком-либо конкретном кодировании. Каждая вероятность остановки является нормальным и трансцендентным действительным числом, которое не является вычислимым, то есть не существует алгоритма для вычисления его цифр. Каждая вероятность остановки является случайным числом Мартина Лёфа, что означает, что не существует даже алгоритма, способного надёжно предсказывать его цифры.

Предыстория

Определение вероятности остановки основывается на существовании универсальной вычислимой функции без префиксов. Такая функция, интуитивно, представляет собой язык программирования, обладающий свойством, что ни одна допустимая программа не может быть получена как собственное расширение другой допустимой программы. Предположим, что F — частичная функция, принимающая один аргумент — конечную двоичную строку, и, возможно, возвращающая одну двоичную строку в качестве результата. Функция F называется вычислимой, если существует машина Тьюринга, которая её вычисляет, в том смысле, что для любых конечных двоичных строк x и y, F(x) = y тогда и только тогда, когда машина Тьюринга останавливается с y на своей ленте при вводе x. Функция F называется универсальной, если выполняется следующее свойство: для каждой вычислимой функции f от одной переменной существует строка w, такая что для всех x, F(w x) = f(x); здесь w x представляет собой конкатенацию строк w и x. Это означает, что F может быть использована для моделирования любой вычислимой функции одной переменной. Неформально, w представляет собой «скрипт» для вычислимой функции f, а F представляет собой «интерпретатор», который разбирает скрипт как префикс своего ввода, а затем выполняет его на оставшейся части ввода. Область определения F — это множество всех входных данных p, на которых она определена. Для универсальных F такое p обычно можно рассматривать как конкатенацию части программы и части данных, а также как единую программу для функции F. Функция F называется свободной от префиксов, если в её области определения не существует двух элементов p и p′, таких что p′ является собственным расширением p. Это можно перефразировать так: область определения F является кодом без префиксов (мгновенным кодом) на множестве конечных двоичных строк. Простой способ обеспечить отсутствие префиксов — использовать машины, вход которых представляет собой двоичный поток, из которого биты можно считывать по одному за раз. Маркера конца потока нет; конец ввода определяется моментом, когда универсальная машина решает прекратить чтение дополнительных битов, а оставшиеся биты не считаются частью принятой строки. Здесь становится ясной разница между двумя понятиями программы, упомянутыми в последнем абзаце: одно легко распознается некоторой грамматикой, а другое требует произвольных вычислений для распознавания. Область определения любой универсальной вычислимой функции является вычислимо перечислимым множеством, но никогда — вычислимым множеством. Область определения всегда Тьюрингово эквивалентна задаче остановки.

Связь с проблемой остановки

Зная первые N битов Ω, можно решить проблему остановки для всех программ размером не более N. Пусть программа p, для которой требуется решить проблему остановки, имеет длину N битов. Все программы всех длин запускаются последовательно, переключаясь между ними, пока не остановится достаточное количество программ, чтобы их совместный вклад в вероятность остановки соответствовал этим первым N битам. Если программа p к этому моменту не остановилась, то она никогда не остановится, поскольку её вклад в вероятность остановки повлиял бы на первые N битов. Таким образом, проблема остановки была бы решена для p.

Поскольку многие нерешенные проблемы в теории чисел, такие как гипотеза Гольдбаха, эквивалентны решению проблемы остановки для специальных программ (которые, по сути, будут искать контрпримеры и останавливаться при их обнаружении), знание достаточного количества битов постоянной Чейтина также означало бы знание ответа на эти проблемы. Но поскольку проблема остановки в общем случае неразрешима, а значит, вычислить что-либо, кроме первых нескольких битов постоянной Чейтина, невозможно на достаточно компактном языке, это лишь сводит сложные проблемы к неразрешимым, подобно попытке построить оракульную машину для проблемы остановки.

Невычислимость

Реальное число называется вычислимым, если существует алгоритм, который, получив на вход n, возвращает первые n цифр этого числа. Это эквивалентно существованию программы, перечисляющей цифры реального числа. Вероятность остановки не является вычислимой. Доказательство этого факта опирается на алгоритм, который, имея первые n цифр Ω, решает проблему остановки Тьюринга для программ длиной не более n. Поскольку проблема остановки неразрешима, Ω не может быть вычислена. Алгоритм работает следующим образом: получив первые n цифр Ω и некоторое k ≤ n, алгоритм перечисляет область определения F до тех пор, пока не будет найдено достаточно элементов этой области, чтобы вероятность, которую они представляют, отличалась от Ω не более чем на 2−(k+1). После этого в область определения не может быть добавлена ни одна дополнительная программа длиной k, поскольку каждая из них увеличит меру на 2−k, что невозможно. Таким образом, множество строк длиной k, принадлежащих области определения, совпадает с множеством уже перечисленных строк такой длины.

Алгоритмическая случайность

Реальное число считается случайным, если двоичная последовательность, представляющая это число, является алгоритмически случайной последовательностью. Калуде, Гертлинг, Хуссейнов и Ван показали, что рекурсивно перечислимое реальное число является алгоритмически случайной последовательностью тогда и только тогда, когда оно является числом Чайтина Ω.

Теорема неполноты для остановки вероятностей

Для каждой конкретной непротиворечивой эффективно представимой аксиоматической системы для натуральных чисел, такой как арифметика Пеано, существует константа N, такая, что ни один бит Ω после N-го не может быть доказан равным 1 или 0 в рамках этой системы. Константа N зависит от способа эффективного представления формальной системы и, следовательно, не отражает напрямую сложность аксиоматической системы. Этот результат о неполноте аналогичен теореме Гёделя о неполноте, поскольку он показывает, что никакая непротиворечивая формальная теория арифметики не может быть полной.

Супер Омега

Как упоминалось выше, первые n бит константы Грегори Чейтина Ω случайны или несжимаемы в том смысле, что мы не можем вычислить их с помощью алгоритма остановки, требующего менее n O(1) бит. Однако рассмотрим короткий, но никогда не останавливающийся алгоритм, который систематически перечисляет и запускает все возможные программы; каждый раз, когда одна из них останавливается, её вероятность добавляется к выходным данным (изначально равным нулю). Через конечное время первые n бит выходных данных больше не будут изменяться (неважно, что само это время не вычислимо программой остановки). Таким образом, существует короткий, не останавливающийся алгоритм, выход которого сходится (через конечное время) к первым n битам Ω. Иными словами, перечислимые первые n битов Ω высоко сжимаемы в том смысле, что они предельно вычислимы очень коротким алгоритмом; они не случайны относительно множества перечисляющих алгоритмов. Юрген Шмидхубер (2000) построил предельно вычислимый "Супер Ω", который в некотором смысле намного более случаен, чем исходный предельно вычислимый Ω, поскольку Супер Ω нельзя существенно сжать каким-либо перечисляющим, не останавливающимся алгоритмом. В качестве альтернативного "Супер Ω" можно рассматривать вероятность универсальности префикс-свободной универсальной машины Тьюринга (UTM), то есть вероятность того, что она останется универсальной, даже если каждый её вход (в виде двоичной строки) будет дополнен случайной двоичной строкой. Это можно интерпретировать как не останавливающуюся вероятность машины с оракулом, представляющим третью итерацию проблемы остановки (т.е. с использованием обозначений Turing Jump).