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

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

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

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

Предпосылки

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

Предположим, что функция 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 может быть обозначена просто как Ω, хотя различные префиксные универсальные вычислимые функции приводят к различным значениям Ω.

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

Константа Хайтина, в принципе, может быть использована для решения многих выдающихся проблем теории чисел, включая проблему Гольдбаха и гипотезы Римана. Формулировка проблемы Гольдбаха утверждает, что любое четное число является суммой двух простых. Пусть для заданного четного числа компьютерная программа ищет соответствующие простые числа. Если догадка Гольдбаха верна, программа переходит к следующему четному числу и поиск продолжается. Если не существует двух простых чисел, в сумме дающих требуемое четное число, то будет найден контрпример, программа остановится и догадка Гольдбаха будет опровергнута. Пусть длина этой программы 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.
• Ω имеет ту же степень неразрешимости по Тьюрингу, что и проблема остановки, и, таким образом, находится на уровне $\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 году построил ограничено-вычислимую «Сверх Омегу», которая в определенном смысле гораздо более случайна, нежели изначальная ограничено-вычислимая Ω, так как нельзя существенно сжать Сверх Омегу каким бы то ни было перечисляющим не останавливающимся алгоритмом.

См также

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

Примечания

• 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

---

Эта страница использует содержимое раздела Википедии на русском языке. Оригинальная статья находится по адресу: Константа Хайтина. Список первоначальных авторов статьи можно посмотреть в истории правок. Эта статья так же, как и статья, размещённая в Википедии, доступна на условиях CC-BY-SA .

---