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