Імовірнісна машина Тьюринга

Машина Тьюринга
Варіанти машин

Узагальнення детермінованою машини Тьюринга, в якій, з будь-якого стану і значень на стрічці, машина може зробити один з декількох (можна вважати, без обмеження спільності - двох) можливих переходів, а вибір здійснюється імовірнісним чином ( підкиданням монетки)

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

Існує також альтернативне визначення:

Імовірнісна машина Тьюринга являє собою детерміновану машину Тьюринга, що має додатково апаратний джерело випадкових бітів, будь-яке число яких, наприклад, вона може "замовити" і "завантажити" на окрему стрічку і потім використовувати в обчисленнях звичайним для МТ чином.

Клас алгоритмів, що завершуються за поліноміальний час на ймовірнісної машині Тьюринга і повертають відповідь з помилкою менш 1/3, називається класом BPP.