Вероятностная машина Тьюринга

Математическая модель вычисления

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

В случае равных вероятностей для переходов вероятностные машины Тьюринга можно определить как детерминированные машины Тьюринга, имеющие дополнительную инструкцию «записи», где значение записи равномерно распределено в алфавите машины Тьюринга (как правило, равная вероятность записи «1» или «0» на ленту). Другая распространенная переформулировка — это просто детерминированная машина Тьюринга с добавленной лентой, полной случайных битов, называемой «случайной лентой».

Квантовый компьютер — это еще одна модель вычислений, которая по своей сути является вероятностной.

Описание

Вероятностная машина Тьюринга — это тип недетерминированной машины Тьюринга , в которой каждый недетерминированный шаг представляет собой «подбрасывание монеты», то есть на каждом шаге есть два возможных следующих хода, и машина Тьюринга вероятностно выбирает, какой ход сделать. ^[1]

Формальное определение

Вероятностную машину Тьюринга можно формально определить как 7-кортеж , где ${\displaystyle M=(Q,\Sigma ,\Gamma ,q_{0},A,\delta _{1},\delta _{2})}$

• ${\displaystyle Q}$это конечный набор состояний
• ${\displaystyle \Sigma }$это входной алфавит
• ${\displaystyle \Gamma }$представляет собой ленточный алфавит, включающий в себя пустой символ #
• ${\displaystyle q_{0}\in Q}$это начальное состояние
• ${\displaystyle A\subseteq Q}$это набор принимающих (конечных) состояний
• ${\displaystyle \delta _{1}:Q\times \Gamma \to Q\times \Gamma \times \{L,R\}}$— первая вероятностная функция перехода. — перемещение на одну клетку влево на ленте машины Тьюринга, — перемещение на одну клетку вправо. ${\displaystyle L}$ ${\displaystyle R}$
• ${\displaystyle \delta _{2}:Q\times \Gamma \to Q\times \Gamma \times \{L,R\}}$— вторая вероятностная функция перехода.

На каждом шаге машина Тьюринга вероятностно применяет либо функцию перехода , либо функцию перехода . ^[2] Этот выбор делается независимо от всех предыдущих выборов. Таким образом, процесс выбора функции перехода на каждом шаге вычисления напоминает подбрасывание монеты. ${\displaystyle \delta _{1}}$ ${\displaystyle \delta _{2}}$

Вероятностный выбор функции перехода на каждом шаге вносит ошибку в машину Тьюринга; то есть строки, которые машина Тьюринга должна принимать, могут в некоторых случаях быть отклонены, а строки, которые машина Тьюринга должна отвергать, могут в некоторых случаях быть приняты. Чтобы учесть это, говорят, что язык распознается с вероятностью ошибки вероятностной машиной Тьюринга, если: ${\displaystyle L}$ ${\displaystyle \epsilon }$ ${\displaystyle M}$

1. строка в подразумевает, что ${\displaystyle w}$ ${\displaystyle L}$ ${\displaystyle {\text{Pr}}[M{\text{ accepts }}w]\geq 1-\epsilon }$
2. строка не в подразумевает, что ${\displaystyle w}$ ${\displaystyle L}$ ${\displaystyle {\text{Pr}}[M{\text{ rejects }}w]\geq 1-\epsilon }$

Классы сложности

Нерешенная проблема в информатике :

P = BPP  ?​

(еще нерешенные проблемы в информатике)

В результате ошибки, вносимой использованием вероятностных подбрасываний монеты, понятие принятия строки вероятностной машиной Тьюринга может быть определено разными способами. Одним из таких понятий, включающим несколько важных классов сложности, является допущение вероятности ошибки 1/3. Например, класс сложности BPP определяется как класс языков, распознаваемых вероятностной машиной Тьюринга за полиномиальное время с вероятностью ошибки 1/3. Другим классом, определенным с использованием этого понятия принятия, является BPL , который является тем же, что и BPP, но накладывает дополнительное ограничение, что языки должны быть разрешимы в логарифмическом пространстве .

Классы сложности, вытекающие из других определений принятия, включают RP , co-RP и ZPP . Если машина ограничена логарифмическим пространством вместо полиномиального времени, получаются аналогичные классы сложности RL , co-RL и ZPL . При применении обоих ограничений получаются RLP , co-RLP , BPLP и ZPLP .

Вероятностное вычисление также имеет решающее значение для определения большинства классов интерактивных систем доказательств , в которых машина верификатора зависит от случайности, чтобы избежать предсказания и обмана всемогущей машиной-доказательством. Например, класс IP равен PSPACE , но если удалить случайность из верификатора, то останется только NP , который неизвестен, но широко распространено мнение, что это значительно меньший класс.

Один из центральных вопросов теории сложности заключается в том, добавляет ли случайность мощности; то есть существует ли задача, которая может быть решена за полиномиальное время вероятностной машиной Тьюринга, но не детерминированной машиной Тьюринга? Или детерминированные машины Тьюринга могут эффективно моделировать все вероятностные машины Тьюринга с не более чем полиномиальным замедлением? Известно, что P ⊆ BPP , поскольку детерминированная машина Тьюринга является всего лишь частным случаем вероятностной машины Тьюринга. Однако неизвестно, выполняется ли (но широко предполагается, что) BPP ⊆ P , что подразумевает, что BPP = P . Тот же вопрос для логарифмического пространства вместо полиномиального времени (равно ли L = BPLP ?) еще более широко считается верным. С другой стороны, мощность, которую случайность придает интерактивным системам доказательств, а также простые алгоритмы, которые она создает для сложных задач, таких как проверка простоты за полиномиальное время и проверка связности графа логарифмического пространства, предполагает, что случайность может добавлять мощности.

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

• Рандомизированный алгоритм

Примечания

1. Sipser, Michael (2006). Введение в теорию вычислений (2-е изд.). США: Thomson Course Technology. стр. 368. ISBN 978-0-534-95097-2.
2. Арора, Санджив ; Барак, Боаз (2016). Вычислительная сложность: современный подход . Cambridge University Press. стр. 125. ISBN 978-0-521-42426-4.

Ссылки

• Арора, Санджив ; Барак, Боаз (2016). Вычислительная сложность: современный подход . Cambridge University Press. стр. 123–142. ISBN 978-0-521-42426-4.
• Sipser, Michael (2006). Введение в теорию вычислений (2-е изд.). США: Thomson Course Technology. стр. 368–380. ISBN 978-0-534-95097-2.

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

• Сайт NIST о вероятностных машинах Тьюринга