постоянная Чайтина

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

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

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

Фон

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

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

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

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

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

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

Определение

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

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

,

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

Связь с проблемой остановки

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

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

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

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

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

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

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

.

Каждая из этих строк p _i определяет подмножество Si _; канторова пространства множество Si _{канторовом пространстве ,} начинающиеся с pi _{содержит все последовательности в} . Эти множества не пересекаются, поскольку P — множество без префиксов. Сумма

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

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

\bigcup _{i\in \mathbb {N} }S_{i}

.

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

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

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

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

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

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

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

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

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

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

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

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

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

Супер Омега

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

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

См. также

Ссылки

^ mathworld.wolfram.com , Константа Чайтина . Проверено 28 мая 2012 г.
^ Дауни и Хиршфельдт, 2010 , Теорема 6.1.3.
^ Дауни и Хиршфельдт, 2010 , Теорема 5.1.11.
^ Jump up to: Перейти обратно: ^а ^б Дауни и Хиршфельдт, 2010 , с. 405.
^ Дауни и Хиршфельдт, 2010 , стр. 228–229.
^ Калуде, Кристиан С.; Хертлинг, Питер Х.; Хусаинов, Бахадыр; Ван, Юнге (1998), «Рекурсивно перечисляемые действительные числа и числа Чайтин Ω» (PDF) , STACS 98 , vol. 1373, Springer Berlin Heidelberg, стр. 596–606, Bibcode : 1998LNCS.1373..596C , doi : 10.1007/bfb0028594 , ISBN 978-3-540-64230-5 , S2CID 5493426 , заархивировано (PDF) из оригинала 19 января 2004 г. , получено 20 марта 2022 г.
^ Бармпалиас Г. и Доу Д.Л. (2012). «Вероятность универсальности машины без префиксов» . Философские труды Королевского общества А. 370 (1): 3488–3511 (Тематический выпуск «Основы вычислений, физики и мышления: наследие Тьюринга», составленный и отредактированный Барри Купером и Самсоном Абрамски). Бибкод : 2012RSPTA.370.3488B . дои : 10.1098/rsta.2011.0319 . ПМИД 22711870 .

Цитируемые работы

Калуде, Кристиан С. (2002). Информация и случайность: алгоритмическая перспектива (второе изд.). Спрингер. ISBN 3-540-43466-6 .
Дауни, Р.; Хиршфельдт, Д. (2010). Алгоритмическая случайность и сложность . Спрингер-Верлаг.
Ли, Мин; Витаньи, Пол (1997). Введение в колмогоровскую сложность и ее приложения . Спрингер. Полный текст вводной главы .
Шмидхубер, Юрген (2002). «Иерархии обобщенных колмогоровских сложностей и неисчислимые универсальные меры, вычислимые в пределе». Международный журнал основ компьютерных наук . 13 (4): 587–612. дои : 10.1142/S0129054102001291 . Препринт: Алгоритмические теории всего (arXiv: quant-ph/0011122)

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

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

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

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

[FOOTNOTEDowneyHirschfeldt2010Theorem_5.1.11-3] Дауни и Хиршфельдт, 2010 , Теорема 5.1.11.

[FOOTNOTEDowneyHirschfeldt2010405-4] Jump up to: Перейти обратно: ^а ^б Дауни и Хиршфельдт, 2010 , с. 405.

[FOOTNOTEDowneyHirschfeldt2010228–229-5] Дауни и Хиршфельдт, 2010 , стр. 228–229.

[6] Калуде, Кристиан С.; Хертлинг, Питер Х.; Хусаинов, Бахадыр; Ван, Юнге (1998), «Рекурсивно перечисляемые действительные числа и числа Чайтин Ω» (PDF) , STACS 98 , vol. 1373, Springer Berlin Heidelberg, стр. 596–606, Bibcode : 1998LNCS.1373..596C , doi : 10.1007/bfb0028594 , ISBN 978-3-540-64230-5 , S2CID 5493426 , заархивировано (PDF) из оригинала 19 января 2004 г. , получено 20 марта 2022 г.

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]