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

Машины Тьюринга
Машина
Эквиваленты машины Тьюринга Примеры машины Тьюринга Галерея машин Тьюринга
Варианты
Переменная машина Тьюринга Нейронная машина Тьюринга Недетерминированная машина Тьюринга Квантовая машина Тьюринга Машина Пост-Тьюринга Вероятностная машина Тьюринга Машина Тьюринга только для чтения Право движущиеся машины Тьюринга только для чтения Многолента машина Тьюринга Многодорожечная машина Тьюринга Симметричная машина Тьюринга Общая машина Тьюринга Однозначная машина Тьюринга Универсальная машина Тьюринга Зенон машина
Наука
Алан Тьюринг Категория: машина Тьюринга
v т е

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

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

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

Описание [ править ]

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

Формальное определение [ править ]

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

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

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

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

строка в подразумевает, что $w$ $L$ ${\text{Pr}}[M{\text{ accepts }}w]\geq 1-\epsilon$
строка не в подразумевает, что $w$ $L$ ${\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 $\subseteq$ $\subseteq$ ?) еще более широко считается правдой. С другой стороны, мощная случайность, которую дает интерактивным системам доказательства, а также простые алгоритмы, которые она создает для сложных задач, таких как проверка простоты в полиномиальном времени и проверка связности графов в лог-пространстве, предполагают, что случайность может добавить мощности.

См. Также [ править ]

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

Заметки [ править ]

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

Ссылки [ править ]

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

Внешние ссылки [ править ]

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

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

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

[1]