Вероятностная машина Тьюринга
Обобщение детерминированной машины Тьюринга, в которой, из любого состояния и значений на ленте, машина может совершить один из нескольких (можно считать, без ограничения общности — двух) возможных переходов, а выбор осуществляется вероятностным образом (подбрасыванием монетки)
Вероятностная Машина Тьюринга похожа на недетерминированную машину Тьюринга, только вместо недетерминированного перехода машина выбирает один из вариантов с некоторой вероятностью.
Существует также альтернативное определение:
Вероятностная машина Тьюринга представляет собой детерминированную машину Тьюринга, имеющую дополнительно аппаратный источник случайных битов, любое число которых, например, она может «заказать» и «загрузить» на отдельную ленту и потом использовать в вычислениях обычным для МТ образом.
Класс алгоритмов, завершающихся за полиномиальное время на вероятностной машине Тьюринга и возвращающих ответ с ошибкой менее 1/3, называется классом BPP.
<imagemap>: неверное или отсутствующее изображение |
Для улучшения этой статьи желательно?:
|
Напишите отзыв о статье "Вероятностная машина Тьюринга"
Отрывок, характеризующий Вероятностная машина Тьюринга
Когда Гаврило пришел доложить Марье Дмитриевне, что приходившие люди убежали, она нахмурившись встала и заложив назад руки, долго ходила по комнатам, обдумывая то, что ей делать. В 12 часу ночи она, ощупав ключ в кармане, пошла к комнате Наташи. Соня, рыдая, сидела в коридоре.– Марья Дмитриевна, пустите меня к ней ради Бога! – сказала она. Марья Дмитриевна, не отвечая ей, отперла дверь и вошла. «Гадко, скверно… В моем доме… Мерзавка, девчонка… Только отца жалко!» думала Марья Дмитриевна, стараясь утолить свой гнев. «Как ни трудно, уж велю всем молчать и скрою от графа». Марья Дмитриевна решительными шагами вошла в комнату. Наташа лежала на диване, закрыв голову руками, и не шевелилась. Она лежала в том самом положении, в котором оставила ее Марья Дмитриевна.
– Хороша, очень хороша! – сказала Марья Дмитриевна. – В моем доме любовникам свидания назначать! Притворяться то нечего. Ты слушай, когда я с тобой говорю. – Марья Дмитриевна тронула ее за руку. – Ты слушай, когда я говорю. Ты себя осрамила, как девка самая последняя. Я бы с тобой то сделала, да мне отца твоего жалко. Я скрою. – Наташа не переменила положения, но только всё тело ее стало вскидываться от беззвучных, судорожных рыданий, которые душили ее. Марья Дмитриевна оглянулась на Соню и присела на диване подле Наташи.
