Константа Хайтина
Этот перевод раздела с другого языка требует улучшения (см. Рекомендации по переводу). |
В разделе информатики — алгоритмической теории информации, константа Хайтина или вероятность остановки — вещественное число, которое, неформально говоря, является вероятностью того, что произвольно выбранная программа остановится. Существование таких чисел было продемонстрировано Грегори Хайтином.
Хотя существует бесконечное множество вероятностей остановки, обычно используют букву
Всякое
Предпосылки
[править | править код]Определение вероятности остановки основывается на существовании префиксных универсальных вычислимых функций. Такие функции представляют собой язык программирования с тем свойством, что ни одна верная программа не может быть получена как соответствующее расширение другой верной программы.
Предположим, что функция 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. Утверждение можно перефразировать следующим образом: область определения есть префиксный код на множестве двоичных строк конечной длины. Область определения любой универсальной вычислимой функции является перечислимым множеством, но никогда не вычислимым множеством. Эта область определения всегда имеет ту же степень неразрешимости по Тьюрингу, что и проблема остановки.
Определение вероятностей остановки
[править | править код]Пусть PF — область определения префиксной универсальной вычислимой функции F. Константа тогда определяется как
- ,
где обозначает длину строки p. Эта бесконечная сумма по всем p из области определения F. То требование, что область определения префиксно, совместно с неравенством Крафта, достаточны для сходимости этой суммы к вещественному числу от 0 до 1. Если 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 состоит из бесконечного множества двоичных строк
Каждая из этих строк pi определяет собой подмножество Si Канторова пространства; множество Si содержит все последовательности в Канторовом пространстве, которые начинаются с pi. Эти множества не пересекаются, так как P — префиксное множество. Сумма
представляет меру множества
- .
Таким образом,
Свойства
[править | править код]Эта статья или раздел содержит незавершённый перевод с английского языка. |
Каждая константа Хайтина
Ω алгоритмически случайна. То есть, для каждого отдельного языка программирования существует константа C, такая что для каждого n любая останавливающаяся программа на этом языке, выводящая первые n битΩ , должна быть не короче, чем (n—C) бит.Ω — нормальное число, что означает её цифры равнораспределены, как если бы они были получены подбрасыванием уравновешенной монеты.Ω — невычислимое число; не существует вычислимой функции, перечисляющей её двоичное разложение, как описано ниже.- Множество рациональных чисел q таких, что q <
Ω — перечислимо; вещественное число с таким свойством называется left-c.e. вещественным числом в теории вычислимости. - Множество рациональных чисел q таких, что q >
Ω — неперечислимо. Ω — арифметическое число.Ω имеет ту же степень неразрешимости по Тьюрингу, что и проблема остановки, и, таким образом, находится на уровне арифметической иерархии.
Не каждое множество, имеющее ту же степень неразрешимости по Тьюрингу, что и проблема остановки, является вероятностью остановки. Лучшее соотношение эквивалентностей, Solovay equivalence, может быть использовано для характеристики вероятностей остановок среди left-c.e. вещественных чисел.[прояснить]
Невычислимость вероятностей остановок
[править | править код]Вещественное число называется вычислимым, если существует алгоритм, который для данного n возвращает первые n цифр числа. Утверждение эквивалентно существованию программы, перечисляющей цифры вещественного числа.
Никакая вероятность остановки не является вычислимой. Доказательство данного факта основывается на алгоритме, который для данных первых n чисел решает проблему остановки программ длиной до n бит. Так как проблема остановки неразрешима, то
Алгоритм действует следующим образом. Если заданы первые n чисел
Теорема неполноты для вероятностей остановки
[править | править код]Для каждой непротиворечивой достаточно богатой системы аксиом натуральных чисел, такой как аксиомы Пеано, существует константа N такая, что доказать, будет какой-либо бит
Вычисление начала Ω Хайтина
[править | править код]Calude, Dinneen, и Shu вычислили первые 64 бита
- 0,0000001000000100000110001000011010001111110010111011101000010000…
и в десятичной записи:
- 0,0078749969978123844…
Возможность верно вычислить определённую (но не любую) цифру
Сверх-Омега
[править | править код]Первые n битов константы
См. также
[править | править код]Примечания
[править | править код]- ↑ 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