|
|
| Строка 1: |
Строка 1: |
| − | Обобщение [[машина Тьюринга|детерминированной машины Тьюринга]], в которой,
| + | #REDIRECT [[discopal:{{PAGENAME}}]] |
| − | из любого состояния и значений на ленте, машина может совершить один из нескольких (можно считать, без ограничения общности — двух) возможных переходов, а выбор осуществляется вероятностным образом (подбрасыванием монетки).
| + | |
| − | | + | |
| − | Вероятностная Машина Тьюринга похожа на [[Недетерминированная машина Тьюринга|недетерминированную машину Тьюринга]], только вместо недетерминированного перехода, машина выбирает один из вариантов с некоторой вероятностью.
| + | |
| − | | + | |
| − | Существует также альтернативное определение:
| + | |
| − | | + | |
| − | [[Вероятностная машина Тьюринга]] представляет собой [[машина Тьюринга|детерминированную машину Тьюринга]], имеющую дополнительно аппаратный источник случайных битов, любое число которых, например, она может «заказать» и «загрузить» на отдельную ленту, и потом, использовать в вычислениях, обычным для [[машина Тьюринга|МТ]] образом.
| + | |
| − | | + | |
| − | [[Category:Теория сложности]]
| + | |
| − | {{replicate-from-custiswiki-to-lib}} | + | |
