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

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

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

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

Класс алгоритмов , завершающихся за полиномиальное время на вероятностной машине Тьюринга и возвращающих ответ с ошибкой менее 1/3, называется классом BPP .