https://discopal.ispras.ru/index.php?action=history&feed=atom&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 2026-04-26T21:42:22Z История изменений этой страницы в вики MediaWiki 1.26.4 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&diff=879&oldid=prev 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