Вероятность универсальности

Вероятность универсальности — это замысловатая вероятностная мера в теории сложности вычислений , которая касается универсальных машин Тьюринга .

Фон

Машина Тьюринга — это базовая модель вычислений . Некоторые машины Тьюринга могут быть предназначены для выполнения определенных вычислений. Например, машина Тьюринга может принимать входные данные, состоящие из двух чисел, а затем выдавать выходные данные, которые являются продуктом их умножения . Другая машина Тьюринга может принимать входные данные в виде списка чисел, а затем выдавать выходные данные в виде чисел, отсортированных по порядку.

Машина Тьюринга , способная моделировать любую другую машину Тьюринга, называется универсальной . Другими словами, машина Тьюринга (TM) называется универсальной машиной Тьюринга (или UTM), если для любой другой машины Тьюринга существует некоторое ввод (или «заголовок») так, что первый TM с учетом этого входного «заголовка» всегда будет вести себя как второй TM.

интересный математический и философский Тогда возникает вопрос. Если в универсальную машину Тьюринга поступают случайные входные данные (для подходящего определения случайности ), насколько вероятно, что она останется универсальной навсегда?

Определение

Учитывая без префиксов машину Тьюринга , универсальности вероятность ее — это вероятность того, что она остается универсальной, даже когда каждый ее вход (в виде двоичной строки ) имеет префикс случайной двоичной строки. Более формально, это вероятностная мера вещественных чисел (бесконечных двоичных последовательностей), которые обладают тем свойством, что каждый их начальный сегмент сохраняет универсальность данной машины Тьюринга. Это понятие было введено ученым-компьютерщиком Крисом Уоллесом и впервые подробно обсуждалось в печати в статье Доу. ^[1] (и следующая статья ^[2]). Однако соответствующие обсуждения также появляются в более ранней статье Уоллеса и Доу. ^[3]

Вероятности универсальности UTM без префиксов не равны нулю.

вероятность универсальности UTM Хотя изначально предполагалось, что (UTM) равна нулю, существуют относительно простые доказательства того, что верхняя грань набора вероятностей универсальности равна 1, например доказательство, основанное на случайных блужданиях. ^[4] и доказательство у Бармпалиаса и Доу (2012).Если у вас есть один UTM без префиксов с ненулевой вероятностью универсальности, из этого сразу следует, что все без префиксов UTM имеют ненулевую вероятность универсальности.Далее, поскольку верхняя грань множества вероятностей универсальности равна 1 и поскольку множество ${ .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠ m / 2 н ⁠ | 0 < n и 0 < m < 2 н }$ плотно , в интервале [0, 1] подходящие конструкции УТМ(например, если U — UTM, определитеUTM U ₂ на U ₂ (0 s ) останавливается для всех строк s ,U ₂ (1 s ) = U ( s ) для всех s) дает, что набор вероятностей универсальности равен плотный в открытом интервале (0, 1).

Характеристика и случайность вероятности универсальности

Вероятность универсальности была тщательно изучена и охарактеризована Бармпалиасом и Доу в 2012 году. ^[5]Рассматриваемые как действительные числа , эти вероятности были полностью охарактеризованы с точки зрения понятий теории вычислимости. и алгоритмическая теория информации .Было показано, что когда базовая машина универсальна, эти числа являются алгоритмически случайными . Точнее, это случайность Мартина-Лёфа относительно третьей итерации проблемы остановки . Другими словами, они случайны относительно нулевых наборов, которые можно определить с помощью четырех кванторов в арифметике Пеано . И наоборот, учитывая такое сильно случайное число ^{[ нужны разъяснения ]} (с соответствующими свойствами аппроксимации) существует машина Тьюринга с вероятностью универсальности этого числа.

Связь с константой Чайтина

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

Вероятности машин как примеры весьма случайных чисел

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

См. также

Ссылки

^ * Доу, Д.Л. (5 сентября 2008 г.). «Предисловие к К.С. Уоллесу» . Компьютерный журнал . 51 (5): 523–560. дои : 10.1093/comjnl/bxm117 . (и здесь )
^ *Доу, Д.Л. (2011), « MML, графические модели гибридных байесовских сетей, статистическая согласованность, инвариантность и уникальность» , Справочник по философии науки - (HPS, том 7) Философия статистики, П.С. Бандиопадьяй и М.Р. Форстер (ред. ), Elsevier, стр. 901-982.
^ Уоллес, К.С. и Доу, Д.Л. 1999. Минимальная длина сообщения и колмогоровская сложность. Компьютер J. 42, 270–283.
^ * Эрнандес-Оралло, Дж. и Доу, Д.Л. (2013), «О потенциальных когнитивных способностях в машинном мире», Minds and Machines , Vol. 23, выпуск 2, стр. 179-210.
^ Бармпалиас Г. и Доу Д.Л. (2012). «Вероятность универсальности машины без префиксов». Философские труды Королевского общества А. 370 (1): 3488–3511. Бибкод : 2012RSPTA.370.3488B . CiteSeerX 10.1.1.221.6000 . дои : 10.1098/rsta.2011.0319 . ПМИД 22711870 . S2CID 2092954 .

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

Бармпалиас Г. и Доу Д.Л. (2012). «Вероятность универсальности машины без префиксов». Философские труды Королевского общества А. 370 (1): 3488–3511 (Тематический выпуск «Основы вычислений, физики и мышления: наследие Тьюринга», составленный и отредактированный Барри Купером и Самсоном Абрамски). Бибкод : 2012RSPTA.370.3488B . CiteSeerX 10.1.1.221.6000 . дои : 10.1098/rsta.2011.0319 . ПМИД 22711870 . S2CID 2092954 .
Доу, Д.Л. (5 сентября 2008 г.). «Предисловие к К.С. Уоллесу» . Компьютерный журнал . 51 (5): 523–560. дои : 10.1093/comjnl/bxm117 . (и здесь ).
Доу, Д.Л. (2011), « MML, графические модели гибридных байесовских сетей, статистическая согласованность, инвариантность и уникальность» , Справочник по философии науки - (HPS, том 7) «Философия статистики», П.С. Бандиопадьяй и М.Р. Форстер (ред.), Эльзевир, стр. 901–982.
Уоллес, К.С. и Доу, Д.Л. 1999. Минимальная длина сообщения и колмогоровская сложность . Компьютерный журнал 42, 270–283.
Эрнандес-Оралло Дж. и Доу Д.Л. (2013), «О потенциальных когнитивных способностях в машинном мире», Minds and Machines , Vol. 23, выпуск 2, стр. 179-210 (и здесь )
Бармпалиас Г. (июнь 2015 г.), слайды из выступления под названием «Случайность, вероятности и машины» на Десятой международной конференции по вычислимости, сложности и случайности ( CCR 2015 ), 22–26 июня 2015 г., Гейдельберг, Германия.
Кристиан С. Калуд, Майкл Дж. Диннин и Чи-Коу Шу. Вычисление случайности .

Дальнейшее чтение

Мин Ли и Пол Витаньи (1997). Введение в колмогоровскую сложность и ее приложения . Спрингер. Полный текст вводной главы .
Кристиан С. Калуде (2002). Информация и случайность: алгоритмическая перспектива , второе издание. Спрингер. ISBN 3-540-43466-6
Р. Дауни и Д. Хиршфельдт (2010), Алгоритмическая случайность и сложность , Springer-Verlag.

[1] * Доу, Д.Л. (5 сентября 2008 г.). «Предисловие к К.С. Уоллесу» . Компьютерный журнал . 51 (5): 523–560. дои : 10.1093/comjnl/bxm117 . (и здесь )

[2] *Доу, Д.Л. (2011), « MML, графические модели гибридных байесовских сетей, статистическая согласованность, инвариантность и уникальность» , Справочник по философии науки - (HPS, том 7) Философия статистики, П.С. Бандиопадьяй и М.Р. Форстер (ред. ), Elsevier, стр. 901-982.

[3] Уоллес, К.С. и Доу, Д.Л. 1999. Минимальная длина сообщения и колмогоровская сложность. Компьютер J. 42, 270–283.

[4] * Эрнандес-Оралло, Дж. и Доу, Д.Л. (2013), «О потенциальных когнитивных способностях в машинном мире», Minds and Machines , Vol. 23, выпуск 2, стр. 179-210.

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

[1]

[2]

[3]

[4]

[5]