https://discopal.ispras.ru/index.php?title=%D0%92%D0%B5%D1%80%D0%BE%D1%8F%D1%82%D0%BD%D0%BE%D1%81%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0&feed=atom&action=historyВероятностная машина Тьюринга - История изменений2024-03-29T10:46:13ZИстория изменений этой страницы в викиMediaWiki 1.26.4https://discopal.ispras.ru/index.php?title=%D0%92%D0%B5%D1%80%D0%BE%D1%8F%D1%82%D0%BD%D0%BE%D1%81%D1%82%D0%BD%D0%B0%D1%8F_%D0%BC%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0&diff=879&oldid=prevWikiSysop: 1 версия2008-08-04T09:55:52Z<p>1 версия</p>
<p><b>Новая страница</b></p><div>Обобщение [[машина Тьюринга|детерминированной машины Тьюринга]], в которой, <br />
из любого состояния и значений на ленте, машина может совершить один из нескольких (можно считать, без ограничения общности — двух) возможных переходов, а выбор осуществляется вероятностным образом (подбрасыванием монетки). <br />
<br />
Вероятностная Машина Тьюринга похожа на [[Недетерминированная машина Тьюринга|недетерминированную машину Тьюринга]], только вместо недетерминированного перехода, машина выбирает один из вариантов с некоторой вероятностью.<br />
<br />
Существует также альтернативное определение: <br />
<br />
[[Вероятностная машина Тьюринга]] представляет собой [[машина Тьюринга|детерминированную машину Тьюринга]], имеющую дополнительно аппаратный источник случайных битов, любое число которых, например, она может «заказать» и «загрузить» на отдельную ленту, и потом, использовать в вычислениях, обычным для [[машина Тьюринга|МТ]] образом.<br />
<br />
[[Category:Теория сложности]]<br />
{{replicate-from-custiswiki-to-lib}}</div>WikiSysop