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

Определение

Вероятностной является машина Тьюринга с дополнительной односторонне-бесконечной лентой, в каждой клетке которой с вероятностью 1/2 записан 0 или 1.