Это снимок страницы. Он включает старые, но не удалённые версии шаблонов и изображений.
Обобщение детерминированной машины Тьюринга, в которой,
из любого состояния и значений на ленте, машина может совершить один из нескольких (можно считать, без ограничения общности — двух) возможных переходов, а выбор осуществляется вероятностным образом (подбрасыванием монетки).
Вероятностная Машина Тьюринга похожа на недетерминированную машину Тьюринга, только вместо недетерминированного перехода, машина выбирает один из вариантов с некоторой вероятностью.
Существует также альтернативное определение:
Вероятностная машина Тьюринга представляет собой детерминированную машину Тьюринга, имеющую дополнительно аппаратный источник случайных битов, любое число которых, например, она может «заказать» и «загрузить» на отдельную ленту, и потом, использовать в вычислениях, обычным для МТ образом.
Внимание! Данная статья выбрана для репликации во внешнюю базу знаний компании. Пожалуйста, не допускайте в этой статье публикацию конфиденциальной информации, ведения обсуждений в теле статьи, и более ответственно относитесь к качеству самой статьи — проверяйте орфографию, пишите по-русски, избегайте непроверенной вами информации.
