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

Фон

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

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

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

Определение

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

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

Хотя вероятность универсальности UTM (UTM) изначально предполагалось равным нулю, существуют относительно простые доказательства того, что супремум множества вероятностей универсальности равно 1, например, доказательство, основанное на случайные прогулки[4] и доказательство в Barmpalias and Dowe (2012). без префиксов UTM с ненулевой вероятностью универсальности сразу следует, что все без префиксов UTM имеют ненулевую вероятность универсальности. Кроме того, поскольку супремум множества вероятностей универсальности равно 1, а поскольку множество { м/ 2п | 0 < п & 0 < м < 2п} является плотный в интервале [0, 1] подходящие конструкции UTM (например, если U это UTM, определите aUTM U2 к U2(0s) останавливается для всех струн s, U2(1s) = U(s) для всех s) дает, что множество вероятностей универсальности равноплотный в открытом интервале (0, 1).

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

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

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

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

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

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

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

Рекомендации

  1. ^ *Доу, Д.Л. (5 сентября 2008 г.). "Предисловие к К. С. Уоллесу". Компьютерный журнал. 51 (5): 523–560. Дои:10.1093 / comjnl / bxm117. (и здесь )
  2. ^ * Доу, Д. Л. (2011) "MML, гибридные байесовские сетевые графические модели, статистическая согласованность, инвариантность и уникальность », Справочник по философии науки - (HPS Том 7) Философия статистики, P.S. Bandyopadhyay и M.R. Forster (ред.), Elsevier, pp901-982
  3. ^ Уоллес, К. С. и Доу, Д. Л. 1999 Минимальная длина сообщения и колмогоровская сложность Computer J. 42, 270–283
  4. ^ * Эрнандес-Оралло, Дж. И Доу, Д. Л. (2013), «О потенциальных когнитивных способностях в машинном царстве», Умы и машины, Vol. 23, Выпуск 2, pp179-210
  5. ^ Бармпалиас Г. и Доу Д.Л. (2012). «Вероятность универсальности машины без префиксов». Философские труды Королевского общества A. 370 (1): 3488–3511. Bibcode:2012RSPTA.370.3488B. CiteSeerX  10.1.1.221.6000. Дои:10.1098 / rsta.2011.0319. PMID  22711870.

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

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

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