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

Материал из Викиконспекты
Версия от 19:28, 10 апреля 2010; 192.168.0.2 (обсуждение) (Определение)
Перейти к: навигация, поиск

Определение

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