Просмотр исходного текста страницы Вероятностная машина Тьюринга

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

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

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

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

[[Category:Теория сложности]]
{{replicate-from-custiswiki-to-lib}}