Константа Чейтинса - Chaitins constant

в Информатика подполе алгоритмическая теория информации, а Постоянная Чайтина (Омега-число Чайтин)^[1] или же вероятность остановки это настоящий номер что, неформально говоря, представляет вероятность что случайно построенная программа остановится. Эти числа образованы из конструкции за счет Григорий Чайтин.

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

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

Фон

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

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

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

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

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

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

Определение

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

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

,

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

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

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

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

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

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

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

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

{ Displaystyle P = {p_ {1}, p_ {2}, ldots }}

.

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

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

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

{ Displaystyle bigcup _ {я в mathbb {N}} S_ {я}}

.

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

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

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

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

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

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

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

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

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

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

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

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

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

Супер Омега

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

Для альтернативного "Super Ω" вероятность универсальности из без префиксов Универсальная машина Тьюринга (UTM), а именно вероятность того, что он останется универсальным даже тогда, когда каждый его ввод (как двоичная строка ) имеет префикс случайной двоичной строки - можно рассматривать как вероятность остановки машины с оракулом на третьей итерации проблема остановки (т.е. ${ displaystyle O ^ {(3)}}$ с помощью Обозначение прыжка Тьюринга ).^[7]

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

внешняя ссылка

Аспекты Омеги Чайтина Обзорная статья, в которой обсуждаются последние достижения в изучении Омеги Чайтина.
Омега и почему в математике нет 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] Дауни / Хиршфельд, стр.228-229.

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]