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

Определение

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

Определение

Множество называется измеримым, если представимо в виде отрезков.

Определение

[math]\Omega[/math] — множество всех вероятностных лент.

Определение

[math]\Omega_p[/math] — множество префиксов всех вероятностных лент, каждый из которых длины [math]p[/math].