Изменения
→Определение
Вероятностной называется машина Тьюринга с дополнительной односторонне-бесконечной лентой, называемой вероятностной. На ленте записана последовательность из 0 и 1 с некоторым распределением. Обычно рассматривается равномерное распределение, при котором 0 и 1 равновероятны.
Рассмотрим <tex>\Omega</tex> — множество всех вероятностных лент. и <tex>\Omega_p</tex> — множество всех вероятностных лент с префиксом <tex>p</tex>.
Вероятностная мера <tex>p(\Omega_p)=\frac{1}{2^{|p|}}</tex>.
