Задний план
Машина Тьюринга является базовой моделью вычислений . Некоторые машины Тьюринга могут быть специально предназначены для выполнения определенных вычислений. Например, машина Тьюринга может принимать входные данные, состоящие из двух чисел, а затем выдавать результат, являющийся произведением их умножения . Другая машина Тьюринга может принимать входные данные, представляющие собой список чисел, а затем выдавать выходные данные, которые представляют собой отсортированные по порядку числа.
Машина Тьюринга , которая обладает способностью имитировать любую другую машину Тьюринга называется универсальной , - другими словами, машина Тьюринга (TM) называется быть универсальной машиной Тьюринга (или UTM) , если для любого другого ТМА, есть некоторые input (или «заголовок») таким образом, что первая TM, получившая этот входной «заголовок», навсегда после этого будет вести себя как вторая TM.
Тогда возникает интересный математический и философский вопрос. Если универсальной машине Тьюринга дан случайный ввод (для подходящего определения случайности ), насколько вероятно, что она останется универсальной навсегда?
Определение
Учитывая префикс свободной машины Тьюринга , то универсальность вероятность этого является вероятность того, что он остается универсальным , даже если каждый вход из него (как двоичную строку ) предваряется случайной двоичной строки. Более формально, это вероятностная мера вещественных чисел (бесконечных двоичных последовательностей), которые обладают тем свойством, что каждый их начальный сегмент сохраняет универсальность данной машины Тьюринга. Это понятие было введено компьютерным ученым Крисом Уоллесом и впервые явным образом обсуждалось в печати в статье Доу [1] (и в последующей статье [2] ). Однако соответствующие обсуждения также появляются в более ранней статье Уоллеса и Доу. [3]
Вероятности универсальности UTM без префиксов не равны нулю
Хотя изначально предполагалось, что вероятность универсальности UTM (UTM) равна нулю, существуют относительно простые доказательства того, что верхняя грань набора вероятностей универсальности равна 1, например, доказательство, основанное на случайных блужданиях [4] и доказательство в Бармпалиас и Доу (2012). Если у кого-то есть один UTM без префиксов с ненулевой вероятностью универсальности, сразу следует, что все UTM без префиксов имеют ненулевую вероятность универсальности. Кроме того, поскольку верхняя грань множества вероятностей универсальности равна 1 и поскольку множество {м/2 п| 0 < п & 0 < т <2 п } является плотным в интервале [0, 1], подходящие конструкции UTMS (например, если U представляет собой UTM, определяют UTM U 2 с помощью U 2 (0 сек ) остановками для всех strings s , U 2 (1 s ) = U ( s ) для всех s) дает, что множество вероятностей универсальности плотно в открытом интервале (0, 1).
Характеризация и случайность вероятности универсальности
Вероятность универсальности была тщательно изучена и охарактеризована Бармпалиасом и Доу в 2012 году. [5] Рассматриваемые как действительные числа , эти вероятности были полностью охарактеризованы с точки зрения понятий теории вычислимости и алгоритмической теории информации . Было показано, что, когда базовая машина универсальна, эти числа алгоритмически случайны . В частности, это случайный результат Мартина-Лёфа относительно третьей итерации проблемы остановки . Другими словами, они случайны относительно нулевых наборов, которые могут быть определены с помощью четырех кванторов в арифметике Пеано . И наоборот, при таком сильно случайном числе [ требуется пояснение ] (с соответствующими аппроксимационными свойствами) существует машина Тьюринга с вероятностью универсальности этого числа.
Связь с постоянной Чейтина
Вероятности универсальности очень связаны с постоянной Чейтина , которая представляет собой вероятность остановки универсальной машины без префиксов. В некотором смысле они дополняют вероятности остановки универсальных машин относительно третьей итерации проблемы остановки . В частности, вероятность универсальности можно рассматривать как вероятность остановки машины с оракулом на третьей итерации проблемы остановки. И наоборот, вероятность остановки любой машины без префиксов с этим в высшей степени невычислимым оракулом является вероятностью универсальности некоторой машины без префиксов.
Вероятности машин как примеры сильно случайных чисел
Вероятность универсальности представляет собой конкретный и отчасти естественный пример очень случайного числа (в смысле алгоритмической теории информации ). В том же смысле константа Чейтина представляет собой конкретный пример случайного числа (но для гораздо более слабого понятия алгоритмической случайности).
Смотрите также
- Алгоритмическая вероятность
- История случайности
- Теорема о неполноте
- Индуктивный вывод
- Колмогоровская сложность
- Минимальная длина сообщения
- Теория индуктивного вывода Соломонова
Рекомендации
- ^ * Доу, DL (5 сентября 2008 г.). "Предисловие к К. С. Уоллесу" . Компьютерный журнал . 51 (5): 523–560. DOI : 10.1093 / comjnl / bxm117 .(и здесь )
- ^ * Доу, Д.Л. (2011), « MML, графические модели гибридных байесовских сетей, статистическая согласованность, инвариантность и уникальность» , Справочник по философии науки - (HPS Том 7) Философия статистики, PS Bandyopadhyay и MR Forster (ред. ), Elsevier, стр. 901-982.
- ^ Wallace, CS & Dowe, DL 1999 Минимальная длина сообщения и сложность Колмогорова Компьютер J. 42, 270–283
- ^ * Эрнандес-Оралло, Дж. И Доу, Д.Л. (2013), «О потенциальных когнитивных способностях в машинном царстве», « Умы и машины» , Vol. 23, выпуск 2, стр 179-210
- ^ Бармпалиас Г. и Доу Д.Л. (2012). «Вероятность универсальности безпрефиксной машины». Философские труды Королевского общества А . 370 (1): 3488–3511. Bibcode : 2012RSPTA.370.3488B . CiteSeerX 10.1.1.221.6000 . DOI : 10,1098 / rsta.2011.0319 . PMID 22711870 .
Внешние ссылки
- Бармпалиас Г. и Доу Д.Л. (2012). «Вероятность универсальности безпрефиксной машины». Философские труды Королевского общества А . 370 (1): 3488–3511 (тематический выпуск «Основы вычислений, физики и ментальности: наследие Тьюринга», составленный и отредактированный Барри Купером и Самсоном Абрамски). Bibcode : 2012RSPTA.370.3488B . CiteSeerX 10.1.1.221.6000 . DOI : 10,1098 / rsta.2011.0319 . PMID 22711870 .
- Доу, Д.Л. (5 сентября 2008 г.). "Предисловие к К. С. Уоллесу" . Компьютерный журнал . 51 (5): 523–560. DOI : 10.1093 / comjnl / bxm117 .(и здесь ).
- Доу, Д.Л. (2011), « MML, графические модели гибридных байесовских сетей, статистическая согласованность, инвариантность и уникальность» , Справочник по философии науки - (HPS Том 7) Философия статистики, PS Bandyopadhyay и MR Forster (ред.), Elsevier, pp901-982.
- Уоллес, К.С. и Доу, Д.Л. 1999 Минимальная длина сообщения и сложность Колмогорова . Computer J. 42, 270–283.
- Эрнандес-Оралло, Дж. И Доу, Д.Л. (2013), «О потенциальных когнитивных способностях в машинном царстве», « Умы и машины» , Vol. 23, Issue 2, pp179-210 (и здесь )
- Бармпалиас, Г. (июнь 2015 г.), слайды из выступления под названием `` Случайность, вероятности и машинына Десятой Международной конференции по вычислимости, сложности и случайности ( CCR 2015 ), 22–26 июня 2015 г., Гейдельберг, Германия.
- Кристиан С. Калуд, Майкл Дж. Диннин и Чи-Коу Шу. Вычисление проблеска случайности .
дальнейшее чтение
- Мин Ли и Пол Витани (1997). Введение в колмогоровскую сложность и ее приложения . Springer. Полнотекстовый вводный раздел .
- Кристиан С. Калуд (2002). Информация и случайность: алгоритмическая перспектива , второе издание. Springer. ISBN 3-540-43466-6
- Р. Дауни и Д. Хиршфельдт (2010), Алгоритмическая случайность и сложность , Springer-Verlag.