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

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

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

A квантовый компьютер - еще одна модель вычислений, которая по своей природе является вероятностной.

• 1 Описание
• 2 Формальное определение
• 3 Классы сложности
• 4 См. Также
• 5 Примечания
• 6 Ссылки
• 7 Внешние ссылки

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

Вероятностная машина Тьюринга может быть формально определена как кортеж из семи элементов $M\; =\; (Q,\; \Sigma ,\; \Gamma ,\; q\; 0,\; A,\; \delta \; 1,\; \delta \; 2)\; \{\backslash \; displaystyle\; M\; =\; (Q,\; \backslash \; Sigma,\; \backslash \; Gamma,\; q\_\; \{0\},\; A,\; \backslash \; delta\; \_\; \{1\},\; \backslash \; delta\; \_\; \{2\})\}$, где

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

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

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

1. строка $w\; \{\backslash \; displaystyle\; w\}$в $L\; \{\backslash \; displaystyle\; L\}$означает, что $Pr\; [M\; принимает\; w]\; \ge \; 1\; -\; ϵ\; \{\backslash \; displaystyle\; \{\backslash \; text\; \{Pr\}\}\; [M\; \{\backslash \; text\; \{принимает\}\}\; w]\; \backslash \; geq\; 1-\; \backslash \; epsilon\}$
2. a строка $w\; \{\backslash \; displaystyle\; w\}$не в $L\; \{\backslash \; displaystyle\; L\}$означает, что $Pr\; [M\; отклоняет\; w]\; \ge \; 1\; -\; ϵ\; \{\backslash \; displaystyle\; \{\backslash \; text\; \{Pr\}\}\; [M\; \{\backslash \; text\; \{rejects\}\}\; w]\; \backslash \; geq\; 1-\; \backslash \; epsilon\}$

Нерешенная проблема в информатике :. Is 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$\subseteq \; \{\backslash \; displaystyle\; \backslash \; substeq\}$BPP, поскольку детерминированная машина Тьюринга - это просто частный случай вероятностной машины Тьюринга. Однако неясно (но многие подозревали, что) BPP$\subseteq \; \{\backslash \; displaystyle\; \backslash \; substeq\}$P, подразумевая, что BPP = P. Тот же вопрос о пространстве журнала вместо полиномиального времени (действительно ли L= BPLP ?) Еще более широко считается верным. С другой стороны, сила случайности, которую дает интерактивным системам доказательства, а также простые алгоритмы, которые она создает для сложных задач, таких как проверка простоты в полиномиальном времени и проверка связности графов в лог-пространстве, предполагают, что случайность может добавить мощности.

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

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

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