Вероятностная машина Тьюринга - Probabilistic Turing machine
В теоретической информатике , вероятностная машина Тьюринга является недетерминирована машиной Тьюринга , которая выбирает между имеющимися переходами в каждой точке в соответствии с некоторым распределением вероятностей . Как следствие, вероятностная машина Тьюринга может - в отличие от детерминированной машины Тьюринга - иметь стохастические результаты; то есть, для данного конечного автомата ввода и команд он может иметь разное время выполнения или может вообще не останавливаться; кроме того, он может принимать ввод при одном выполнении и отклонять тот же ввод при другом выполнении.
В случае равных вероятностей переходов вероятностные машины Тьюринга могут быть определены как детерминированные машины Тьюринга, имеющие дополнительную инструкцию «записи», где значение записи равномерно распределено в алфавите машины Тьюринга (как правило, равная вероятность записи «1» или «0» на ленте). Другая распространенная переформулировка - это просто детерминированная машина Тьюринга с добавленной лентой, полной случайных битов, называемой «случайной лентой».
Квантовый компьютер другая модель вычислений, которая по своей сути вероятностным.
Описание
Вероятностная машина Тьюринга - это тип недетерминированной машины Тьюринга, в которой каждый недетерминированный шаг представляет собой «подбрасывание монеты», то есть на каждом шаге есть два возможных следующих хода, и машина Тьюринга вероятностно выбирает, какой ход нужно сделать.
Формальное определение
Вероятностную машину Тьюринга можно формально определить как набор из семи , где
- конечный набор состояний
- это входной алфавит
- представляет собой ленточный алфавит, который включает пустой символ
- это начальное состояние
- это набор принимающих (конечных) состояний
- - первая вероятностная функция перехода. - это движение на одну ячейку влево на ленте машины Тьюринга и движение на одну ячейку вправо.
- - вторая вероятностная функция перехода.
На каждом шаге машина Тьюринга вероятностно применяет либо функцию перехода, либо функцию перехода . Этот выбор делается независимо от всех предыдущих вариантов. Таким образом, процесс выбора функции перехода на каждом этапе вычислений напоминает подбрасывание монеты.
Вероятностный выбор переходной функции на каждом шаге вносит ошибку в машину Тьюринга; то есть строки, которые должна принимать машина Тьюринга, в некоторых случаях могут быть отклонены, а строки, которые машина Тьюринга должна отклонять, могут в некоторых случаях приниматься. Чтобы учесть это, говорят , что язык распознается с вероятностью ошибки вероятностной машиной Тьюринга, если:
- строка в подразумевает, что
- строка не в подразумевает, что
Классы сложности
В результате ошибки, вызванной использованием вероятностных подбрасываний монеты, понятие принятия строки вероятностной машиной Тьюринга может быть определено по-разному. Одно из таких понятий, которое включает несколько важных классов сложности, допускает вероятность ошибки 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 ?) Еще более широко считается верным. С другой стороны, мощная случайность, которую дает интерактивным системам доказательства, а также простые алгоритмы, которые она создает для сложных задач, таких как проверка простоты в полиномиальном времени и проверка связности графов в лог-пространстве, предполагают, что случайность может добавить мощности.
Смотрите также
Примечания
использованная литература
- Арора, Санджив ; Варак, Вооз (2016). Вычислительная сложность: современный подход . Издательство Кембриджского университета. С. 123–142. ISBN 978-0-521-42426-4.
- Сипсер, Майкл (2006). Введение в теорию вычислений (2-е изд.). США: Thomson Course Technology. С. 368–380. ISBN 978-0-534-95097-2.