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

Материал из Викиконспекты

Версия от 19:28, 10 апреля 2010; 192.168.0.2 (обсуждение) (→‎Определение)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Перейти к: навигация, поиск

Определение

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Вероятностные_машины_Тьюринга&oldid=747»