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

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

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

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

Описание

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

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

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

${ displaystyle Q}$ конечный набор состояний
${ displaystyle Sigma}$ это входной алфавит
${ displaystyle Gamma}$ представляет собой ленточный алфавит, содержащий пустой символ ${ displaystyle sqcup}$
${ displaystyle q_ {0} in Q}$ это начальное состояние
${ displaystyle A substeq 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 }}$ - вторая вероятностная функция перехода.

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

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

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

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

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

Является п = BPP ?

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

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

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

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

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

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

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

Примечания

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

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

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

[1] Сипсер, Майкл (2006). Введение в теорию вычислений (2-е изд.). США: Thomson Course Technology. п. 368. ISBN 978-0-534-95097-2.

[2] Арора, Санджив; Варак, Вооз (2016). Вычислительная сложность: современный подход. Издательство Кембриджского университета. п. 125. ISBN 978-0-521-42426-4.

[1]

[2]