Постоянная Чайтина - Chaitin's constant

В информатике подполе алгоритмической теории информации , константа Хайтина ( Хайтина количество омега ) , или вероятность остановки является вещественным числом , что, говоря неформально, представляет собой вероятность того, что случайно построенная программа будет остановить. Эти числа образованы из конструкции Григория Чайтина .

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

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

Задний план

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

Предположим, что F - это частичная функция, которая принимает один аргумент, конечную двоичную строку и, возможно, возвращает одну двоичную строку в качестве вывода. Функция F называется вычислимой, если существует машина Тьюринга, которая ее вычисляет (в том смысле, что для любых конечных двоичных строк x и y, F (x) = y тогда и только тогда, когда машина Тьюринга останавливается с y на своей ленте, когда задано вход x ).

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

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

Функция F называется безпрефиксной, если в ее области нет двух элементов p , p ′, таких что p ′ является собственным расширением p . Это можно перефразировать так: область F - это код без префиксов (мгновенный код) на множестве конечных двоичных строк. Простой способ обеспечить отсутствие префиксов - использовать машины, средства ввода которых представляют собой двоичный поток, из которого биты могут считываться по одному. Нет маркера конца потока; конец ввода определяется, когда универсальная машина решает прекратить чтение дополнительных бит, а оставшиеся биты не считаются частью принятой строки. Здесь становится очевидным различие между двумя понятиями программы, упомянутыми в последнем абзаце; один легко распознается некоторой грамматикой, а другой требует произвольных вычислений для распознавания.

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

Определение

Пусть P _F - область определения универсальной вычислимой функции F без префиксов . Тогда постоянная Ω _F определяется как

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

,

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

Отношение к проблеме остановки

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

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

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

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

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

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

{\ 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 _ {я \ в \ mathbb {N}} S_ {я}}

.

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

Характеристики

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

Он является алгоритмически случайным (также известен как случайный случай Мартина-Лёфа или 1-случайный). Это означает, что самая короткая программа для вывода первых n битов Ω должна иметь размер не менее n -O (1). Это связано с тем, что, как и в примере Гольдбаха, эти n битов позволяют нам точно определить, какие программы останавливаются среди всех программ, длина которых не превышает n .
Как следствие, это нормальное число , а это означает, что его цифры равномерно распределены, как если бы они были получены в результате подбрасывания честной монеты.
Это не вычислимое число ; не существует вычислимой функции, которая перечисляет его двоичное расширение, как обсуждается ниже.
Множество рациональных чисел q таких, что q <Ω, вычислимо перечислимо ; действительное число с таким свойством называется левым вещественным числом в теории рекурсии .
Множество рациональных чисел q таких, что q > Ω невычислимо. (Причина: каждое левое число перечислимых чисел с этим свойством вычислимо, а Ω - нет.)
Ω - арифметическое число .
Это Тьюринг эквивалентно к проблемам остановки и , таким образом , на уровне в арифметической иерархии . ${\ displaystyle \ Delta _ {2} ^ {0}}$

Не каждый набор, эквивалентный задаче остановки по Тьюрингу, является вероятностью остановки. Более тонкое отношение эквивалентности , эквивалентность Соловея , можно использовать для характеристики вероятностей остановки среди левых вещественных чисел. Можно показать, что действительное число в [0,1] является константой Чейтина (то есть вероятностью остановки некоторой универсальной вычислимой функции без префиксов) тогда и только тогда, когда оно является левым в.п. и алгоритмически случайным. Ω - одно из немногих определяемых алгоритмически случайных чисел и наиболее известное алгоритмически случайное число, но оно вовсе не типично для всех алгоритмически случайных чисел.

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

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

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

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

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

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

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

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

Супер Омега

Как упоминалось выше, первые n битов константы Грегори Чейтина Ω случайны или несжимаемы в том смысле, что мы не можем вычислить их с помощью алгоритма остановки с менее чем nO (1) битами. Однако рассмотрите короткий, но никогда не останавливающийся алгоритм, который систематически перечисляет и запускает все возможные программы; всякий раз, когда один из них останавливается, его вероятность добавляется к выходу (инициализируется нулем). По истечении конечного времени первые n битов вывода больше никогда не изменятся (не имеет значения, что это время само по себе не может быть вычислено останавливающейся программой). Итак, есть короткий алгоритм без остановки, выход которого сходится (через конечное время) к первым n битам Ω. Другими словами, перечислимые первые n битов Ω очень сжимаемы в том смысле, что их можно вычислить по пределу с помощью очень короткого алгоритма; они не случайны по отношению к набору алгоритмов перебора. Юрген Шмидхубер ( Jürgen Schmidhuber, 2000) построил предельно вычислимую "Super Ω", которая в некотором смысле намного более случайна, чем исходная предельно вычислимая Ω, поскольку невозможно значительно сжать Super Ω никаким перечисляющим не останавливающим алгоритмом.

Для альтернативной «Super Q», в универсальности вероятности в виде префикса свободного универсальной машины Тьюринга (UTM) - а именно, вероятность того, что он остается универсальной , даже если каждый вход из него (как двоичная строки ) предваряется случайной двоичной строкой - можно рассматривать как вероятность остановки машины с оракулом на третьей итерации проблемы остановки (т. Е. С использованием нотации Тьюринга ). ${\ displaystyle O ^ {(3)}}$

Смотрите также

Внешние ссылки

Аспекты статьи Chaitin's Omega Survey, в которой обсуждаются последние достижения в изучении Omega Chaitin.
Omega и почему в математике нет статьи с TOE, основанной на статье Грегори Чейтина, опубликованной в августовском выпуске журнала Mathematics Today за 2004 год по случаю 50-летия со дня смерти Алана Тьюринга.
Грегори Чейтин «Пределы разума» впервые появился в журнале Scientific American в марте 2006 года.
Предельно вычислимая Супер Омега более случайна, чем Омега, и обобщения алгоритмической информации, Юрген Шмидхубер

[1] thworld.wolfram.com , Константа Чайтина . Проверено 28 мая 2012 г.

[FOOTNOTEDowneyHirschfeldTheorem_6.1.3-2] Дауни и Хиршфельд , Теорема 6.1.3.

[3] Дауни / Хиршфельд, Теорема 5.1.11

[:0-4] Дауни / Хиршфельдт, стр.405

[5] Downey / Гиршфельд, p.228-229

[6] Калуд, Хертлинг, Хусаинов и Ван: Рекурсивно перечислимые действительные числа и числа Чейтина Ω. Теоретическая информатика 255: 125–149, (2001) http://webpages.uncc.edu/yonwang/papers/TCS01.pdf

[7] Barmpalias, Г. и Dowe DL (2012). «Вероятность универсальности безпрефиксной машины» . Философские труды Королевского общества А . 370 (1): 3488–3511 (тематический выпуск «Основы вычислений, физики и ментальности: наследие Тьюринга», составленный и отредактированный Барри Купером и Самсоном Абрамски). DOI : 10,1098 / rsta.2011.0319 . PMID 22711870 .

Languages

In other projects