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

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

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

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

Предпосылки

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

Предположим, что функция 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′, таких что p′ является соответствующем расширением p. Утверждение можно перефразировать следующим образом: область определения есть префиксный код на множестве двоичных строк конечной длины. Область определения любой универсальной вычислимой функции является перечислимым множеством, но никогда не вычислимым множеством. Эта область определения всегда имеет ту же степень неразрешимости по Тьюрингу, что и проблема остановки.

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

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

${\displaystyle \Omega _{F}=\sum _{p\in P_{F}}2^{-|p|}}$,

где ${\displaystyle |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 состоит из бесконечного множества двоичных строк

${\displaystyle P=\{p_{1},p_{2},\ldots \}}$

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

${\displaystyle \sum _{p\in P}2^{-|p|}}$

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

${\displaystyle \bigcup _{i\in \mathbb {N} }S_{i}}$.

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

Свойства

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

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

Не каждое множество, имеющее ту же степень неразрешимости по Тьюрингу, что и проблема остановки, является вероятностью остановки. Лучшее соотношение эквивалентностей, 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
• Пределы доказуемости Грегори Чейтин «В мире науки» №6, 2006 http://elementy.ru/lib/430319