Константа Хайтина

Эта статья или раздел — грубый перевод статьи на другом языке (см. Проверка переводов). Он мог быть сгенерирован программой-переводчиком или сделан человеком со слабыми познаниями в языке оригинала. Вы можете помочь улучшить перевод. Оригинал можно найти слева в списке «на других языках». Статья, целиком являющаяся машинным переводом, может быть удалена на основании критерия быстрого удаления С2.

В разделе информатики — алгоритмической теории информации, константа Хайтина или вероятность остановки — вещественное число, которое, неформально говоря, является вероятностью того, что произвольно выбранная программа остановится. Существование таких чисел было продемонстрировано Грегори Хайтином.

Хотя существует бесконечное множество вероятностей остановки, обычно используют букву Ω для обозначения их всех, как если бы существовало только одно такое число. Так как численное значение Ω зависит от используемого языка программирования, то если не ссылаются на какой-то определённый язык, её часто называют построением Хайтина, а не константой Хайтина.

Всякое Ω является нормальным трансцендентным числом, которое определимо, но невычислимо, что означает отсутствие алгоритма, который перечислял бы его цифры.

Предпосылки

Определение вероятности остановки основывается на существовании префиксных универсальных вычислимых функций. Такие функции, если наглядно, представляют собой язык программирования с тем свойством, что ни одна верная программа не может быть получена как соответствующее расширение другой верной программы.

Предположим, что функция F зависит от двух аргументов, каждый из которых является конечной двоичной строкой, и возвращает одну двоичную строку на выходе. Функция F называется вычислимой, если существует машина Тьюринга, которая её вычисляет.

Функция F называется универсальной, если выполняются следующие условия: для каждой вычислимой функции f одной переменной x существует постоянная p, такая что для любого x, F(p,x) = f(x). То есть, F может быть использована для моделирования любой вычислимой функции одной переменной. Нестрого, p представляет «программу» для вычислимой функции f, а F представляет эмулятор, которому на вход поступает программа и он её выполняет. Следует заметить, что для любого фиксированного p функция f(x) = F(p,x) является вычислимой; таким образом, свойство универсальности утверждает, что таким путём могут быть получены все вычислимые функции одной переменной.

Областью определения F является множество всех программ p, таких что хотя бы для одного значения x значение F(p,x) определённо. Функция называется префиксной, если в её области определения не существует двух элементов p, p&prime, таких что p&prime является соответствующем расширением p. Утверждение можно перефразировать следующим образом: область определения есть префиксный код на множестве двоичных строк конечной длины. Областью определения любой универсальной вычислимой функции является перечислимым множеством, но никогда не вычислимым множеством. Эта область определения всегда имеет ту же степень неразрешимости по Тьюрингу, что и проблема остановки.

Определение вероятностей остановки

Пусть P_F — область определения префиксной универсальной вычислимой функции F. Константа $\Omega_F$ тогда определяется как

$\Omega_F = \sum_{p \in P_F} 2^{-|p|}$,

где $|p|$ обозначает длину строки p. Эта бесконечная сумма по всем p из области определения F. То требование, что область определения префиксно, совместно с неравенством Крафта, достаточны для сходимости этой суммы к вещественному числу от 0 до 1. Если F ясно из контекста, тогда Ω_F может быть обозначена просто как Ω, хотя различные префиксные универсальные вычислимые функции приводят к различным значениям Ω.

Применение Ω к доказательству нерешённых проблем теории чисел

Константа Хайтина, в принципе, может быть использована для решения многих выдающихся проблем теории чисел, включая проблему Гольдбаха и гипотезы Римана.^[1] Формулировка проблемы Гольдбаха утверждает, что любое четное число больше 2 является суммой двух простых. Пусть для заданного четного числа компьютерная программа ищет соответствующие простые числа. Если гипотеза Гольдбаха верна, программа переходит к следующему четному числу и поиск продолжается. Если не существует двух простых чисел, в сумме дающих требуемое четное число, то будет найден контрпример, программа остановится и гипотеза Гольдбаха будет опровергнута. Пусть длина этой программы N бит. Если имеются неограниченные ресурсы и время, константа Хайтина может быть использована для доказательства гипотезы Гольдбаха следующим образом. Пусть параллельно запущены все программы длиной N+1 бит или менее. Если такая N-битная программа останавливается, тогда будет доказано, что гипотеза Гольдбаха неверна. Если же, с другой стороны, достаточное число других программ остановятся, так что ещё одна остановившаяся программа приведет к числу, превышающему константу Хайтина, тогда если программа не остановилась, то она никогда не остановится и доказано. Для того, чтобы применить этот метод нам необходимы лишь первые N бит константы Хайтина.

Та же константа Хайтина может быть использована для доказательства гипотезы Римана и множества других нерешённых проблем математики.

Интерпретация как вероятности

Канторовым пространством называется совокупность всех бесконечных последовательностей нулей и единиц. Вероятность остановки можно интерпретировать как меру определённого подмножества Канторова пространства при обычной вероятностной мере на Канторовом пространстве. Именно из этой интерпретации возникло название вероятностей остановки.

Вероятностная мера на Канторовом пространстве, иногда называется мерой уравновешенной монеты, определяется так, что для любой двоичной строки x, множество последовательностей, начинающихся с x имеют меру 2^-|x|. Данное утверждение подразумевает, что для любого натурального числа n, множество последовательностей f в Канторовом пространстве, таких что f(n) = 1 имеет меру 1/2, и множество последовательностей чей n-й член есть 0 также имеют меру 1/2.

Пусть F — префиксная универсальная вычислимая функция. Её область определения P состоит из бесконечного множества двоичных строк

$P = \{p_1,p_2,\ldots\}$

Каждая из этих строк p_i определяет собой подмножество S_i Канторова пространства; множество S_i содержит все последовательности в Канторовом пространстве, которые начинаются с p_i. Эти множества не пересекаются, так как P — префиксное множество. Сумма

$\sum_{p \in P} 2^{-|p|}$

представляет меру множества

$\bigcup_{i \in \mathbb{N}} S_i$.

Таким образом, Ω_F представляет вероятность того, что случайно выбранная бесконечная последовательность нулей и единиц начинается со строки битов (некоторой конечной длины), которая принадлежит области определения F. Именно по этой причине Ω_F называется вероятностью остановки.

Свойства

Каждая константа Хайтина Ω обладает следующими свойствами:

• Ω алгоритмически случайна. То есть, для каждой отдельного языка программирования существует константа C, такая что для каждого n любая останавливающаяся программа на этом языке, выводящая первые n бит Ω, должна быть не короче, чем (n—C) бит.
• Ω — нормальное число, что означает её цифры равнораспределены, как если бы они были получены подбрасыванием уравновешенной монеты.
• Ω — невычислимое число; не существует вычислимой функции, перечисляющей её двоичное разложение, как описано ниже.
• Множество рациональных чисел q таких, что q < Ω — перечислимо; вещественное число с таким свойством называется left-c.e. вещественным числом в recursion theory.
• Множество рациональных чисел q таких, что q > Ω — неперечислимо.
• Ω — арифметическое число.
• Ω имеет ту же степень неразрешимости по Тьюрингу, что и проблема остановки, и, таким образом, находится на уровне $\Sigma^0_1$ арифметической иерархии.

Не каждое множество, имеющее ту же степень неразрешимости по Тьюрингу, что и проблема остановки, является вероятностью остановки. Лучшее соотношение эквивалентностей, Solovay equivalence, может быть использовано для характеристики вероятностей остановок среди left-c.e. вещественных чисел.

Невычислимость вероятностей остановок

Вещественное число называется вычислимым, если существует алгоритм, который для данного n возвращает первые n цифр числа. Утверждение эквивалентно существованию программы, перечисляющей цифры вещественного числа.

Никакая вероятность остановки невычислима. Доказательство данного факта основывается на алгоритме, который для данных первых n чисел решает проблему остановки программ длиной до n бит. Так как проблема остановки неразрешима, то Ω не может быть вычислено.

Алгоритм действует следующим образом. Если заданы первые n чисел Ω и k≤n, то алгоритм перебирает область определения F до тех пор, пока достаточное число найденных элементов области определения представляют вероятность, лежащую в 2^-(k+1) Ω. После этого ни одна программа длины k не может находиться в рассматриваемой области. Таким образом, множество строк длины k в точности есть множество уже перечисленных таких строк.

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

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

Вычисление начала Ω Хайтина

Calude, Dinneen, и Shu вычислили первые 64 бит Ω_U Хайтина для конкретной машины. Вот они, в двоичной записи

0.0000001000000100000110001000011010001111110010111011101000010000…

или в десятичной записи

0.0078749969978123844…

Следует отметить, что возможность верно вычислить определённую цифру Ω отличается от понятия вычислимости: любая определённая цифра любого числа вычислима в силу того, что для любого целого числа существует программа, печатающая его.

Сверх Омега

Как было упомянуто выше, первые n бит константы Ω Хайтина случайны или несжимаемы в том смысле, что мы не можем вычислить их алгоритмом короче, чем n-O(1) бит. Однако, рассмотрим короткий, но никогда не останавливающийся алгоритм, который методично перечисляет и выполняет все возможные программы; как только одна из них останавливается, её вероятность прибавляется к результату (изначально равному нулю). После конечного времени первые n бит результата больше не изменятся (не имеет значения, что само это время невычислимо). Так что существует короткий не останавливающийся алгоритм, чей результат сходится (за конечное время) к первым n битам Ω для любого n. Другими словами, перечисление первых n бит Ω хорошо сжимаемо в том смысле, что они ограничено вычислимы очень коротким алгоритмом; они не случайны по отношению к множеству перечисляющих алгоритмов. Юрген Шмидхубер в 2000 году построил ограничено-вычислимую «Сверх Омегу», которая в определённом смысле гораздо более случайна, нежели изначальная ограничено-вычислимая Ω, так как нельзя существенно сжать Сверх Омегу каким бы то ни было перечисляющим не останавливающимся алгоритмом.

См. также

• Колмогоровская сложность
• Теоремы Гёделя о неполноте

Примечания

1. ↑ Thomas M. Cover and Joy A. Thomas, Elements of Information Theory, 2nd Edition, Wiley-Interscience, 2006.

Источники

• Cristian S. Calude (2002). Information and Randomness: An Algorithmic Perspective, second edition. Springer. ISBN 3-5404-3466-6
• Cristian S. Calude, Michael J. Dinneen, and Chi-Kou Shu. Computing a Glimpse of Randomness.
• R. Downey, and D. Hirschfeldt (200?), Algorithmic Randomness and Complexity, monograph in preparation, Springer-Verlag. Preliminary version can be found online.
• Ming Li and Paul Vitányi (1997). An Introduction to Kolmogorov Complexity and Its Applications. Springer. Introduction chapter full-text.
• Jürgen Schmidhuber (2000). Algorithmic Theories of Everything (arXiv: quant-ph/ 0011122). Journal reference: J. Schmidhuber (2002). Hierarchies of generalized Kolmogorov complexities and nonenumerable universal measures computable in the limit. International Journal of Foundations of Computer Science 13(4):587-612.

Ссылки

• Omega and why math has no TOEs article based on one written by Gregory Chaitin which appeared in the August 2004 edition of Mathematics Today, on the occasion of the 50th anniversary of Alan Turing’s death.
• The Limits of Reason, Gregory Chaitin, originally appeared in Scientific American, March 2006.(есть русский перевод)
• Limit-computable Super Omega more random than Omega and generalizations of algorithmic information, by Jürgen Schmidhuber