Вероятностные машины Тьюринга — различия между версиями
(→Определение) |
(→Определение) |
||
| Строка 2: | Строка 2: | ||
Вероятностной является машина Тьюринга с дополнительной односторонне-бесконечной лентой, в каждой клетке которой с вероятностью 1/2 записан 0 или 1. | Вероятностной является машина Тьюринга с дополнительной односторонне-бесконечной лентой, в каждой клетке которой с вероятностью 1/2 записан 0 или 1. | ||
==Определение== | ==Определение== | ||
| + | Множество называется измеримым, если представимо в виде отрезков. | ||
| + | |||
| + | ==Определение== | ||
| + | <tex>\Omega</tex> — множество всех вероятностных лент. | ||
| + | |||
| + | ==Определение== | ||
| + | <tex>\Omega_p</tex> — множество префиксов всех вероятностных лент, каждый из которых длины <tex>p</tex>. | ||
Версия 20:05, 10 апреля 2010
Содержание
Определение
Вероятностной является машина Тьюринга с дополнительной односторонне-бесконечной лентой, в каждой клетке которой с вероятностью 1/2 записан 0 или 1.
Определение
Множество называется измеримым, если представимо в виде отрезков.
Определение
— множество всех вероятностных лент.
Определение
— множество префиксов всех вероятностных лент, каждый из которых длины .
