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

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

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

Существует также альтернативное определение:

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

Всюду далее двоичный алфавит $\{ 0,1\}\,$ мы будем обозначать через $\Sigma\,$. Тогда $\Sigma ^*\,$ — множество всех конечных двоичных строк и $\Sigma ^n=\{ x: x\in \Sigma ^*, |x|=n\}\,$ — множество всех двоичных строк длины $n\,$.

Для всякой функции $f:\Sigma ^*\rightarrow \Sigma ^*\,$ через $f_n\,$ обозначается ее ограничение на множество $\Sigma ^n\,$, то есть конечная функция, определенная на двоичных строках длины $n\,$. Таким образом, функцию $f\,$ можно рассматривать просто как сокращенное обозначение для семейства функций $\{ f_n, n\in N\}\,$.

Поскольку в теоретической криптографии рассматриваются, в основном, вероятностные вычисления, необходима строго определенная модель таких вычислений. Наиболее удобной моделью является вероятностная машина Тьюринга. Она отличается от обычной, детерминированной, машины Тьюринга тем, что может ``подбрасывать монету", то есть использовать в процессе вычислений исходы экспериментов по выбору случайного бита, принимающего каждое из значений 0 и 1 с вероятностью 1/2.

Выходом вероятностной машины Тьюринга на входе $x\,$ является случайная величина. Интуитивно, вероятностная машина Тьюринга вычисляет функцию $f\,$, если для всякого входа $x\,$ из области определения эта случайная величина принимает значение $f(x)\,$ ``с достаточно большой вероятностью".

Формально, вероятностную машину Тьюринга $M\,$ мы определяем следующим образом. Помимо обычной ленты, на которую записано входное слово $x\,$ и которая доступна машине $M\,$ и на чтение, и на запись, имеется еще дополнительная лента, содержащая случайную строку $r\,$ и доступная $M\,$ только на чтение. Пусть $\Sigma ^{\infty}\,$ обозначает множество всех бесконечных двоичных последовательностей. Можно считать, что на дополнительной ленте машины $M\,$ (в дальнейшем мы будем называть ее случайной лентой) записана бесконечная случайная последовательность битов $r\in _R \Sigma ^{\infty}$ и читающая головка машины $M\,$ в начальный момент времени обозревает первый бит этой последовательности. Процесс вычисления вероятностной машины $M\,$ определяется таким же образом, как это делается для обычной, детерминированной, машины Тьюринга, с той лишь разницей, что у машины $M\,$ имеется дополнительная лента и дополнительный вход $r\,$.

Определение. Говорят, что вероятностная машина Тьюринга $M\,$ работает за полиномиальное время, если существует такой полином $p\,$, что для всех $n\,$, для любых $x\in \Sigma ^n\,$ и $r\in \Sigma ^{\infty}\,$ машина $M\,$ на входе $(x,r)\,$ останавливается через не более чем $p(n)\,$ шагов.

Во всяком вычислении, в котором машина $M\,$ останавливается, она может использовать лишь префикс конечной длины последовательности $r\,$. В частности, очевидно, что если машина $M\,$ работает за полиномиальное время, то на любом входе $x\,$ длины $n\,$ она может использовать не более $p(n)\,$ случайных битов.

В приведенном выше определении машина $M\,$ должна останавливаться через полиномиальное число шагов всегда, то есть при любой последовательности $r\,$. Более слабое определение требует, чтобы это происходило ``почти всегда".

Тезис Эдмонда. Эффективные алгоритмы — это полиномиальные алгоритмы.

Определение. Пусть $t_M(x, r)\,$ — число шагов вероятностной машины Тьюринга $M\,$ на входе $x\,$, когда на случайной ленте записана последовательность $r\,$. Говорят, что машина $M\,$ работает за полиномиальное в среднем время, если существует такая константа $\varepsilon >0\,$, что для всех $x\in \Sigma ^n\,$

$E((t_M(x, r))^\varepsilon )\leq n.$

Здесь $E\,$ — математическое ожидание; $t_M(x,r)\,$ рассматривается как случайная величина при фиксированной строке $x\,$ и случайной последовательности $r\,$.

Для каждого фиксированного входа $x\in \Sigma ^*\,$, выходом вероятностной машины Тьюринга $M\,$ будет случайная величина, обозначаемая через $M(x)\,$.

Ссылки

• Вероятностная машина Тьюринга в custiswiki
• Курс Н. П. Варновского Понятия теории сложности вычислений

По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.