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

Определение

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