Вычисления с оракулом

Поделись знанием:
Перейти к: навигация, поиск

В теории вычислений и теории сложности машиной с оракулом называют абстрактную машину, предназначенную для решения какой-либо проблемы разрешимости. Такая машина может быть представлена как машина Тьюринга, дополненная оракулом с неизвестным внутренним устройством. Постулируется, что оракул способен решить определённые проблемы разрешимости за один такт машины Тьюринга.





Машина Тьюринга с оракулом

Машина Тьюринга взаимодействует с оракулом путём записи на свою ленту входных данных для оракула и затем запуском оракула на исполнение. За один шаг оракул вычисляет функцию, стирает входные данные и пишет выходные данные на ленту. Иногда машина Тьюринга описывается как имеющая две ленты, одна предназначена для входных данных оракула, другая — для выходных.

Сложностные классы машин с оракулом

Сложностный класс задач решаемых алгоритмом из класса A с оракулом для задачи класса B обозначают AB. Например, класс задач решаемых за полиномиальное время детерминированной машиной Тьюринга с оракулом для NP задачи обозначают PNP.

См. также

Напишите отзыв о статье "Вычисления с оракулом"

Ссылки

Отрывок, характеризующий Вычисления с оракулом

– Ура ра ра! – заревели тысячи голосов. Пока кричали солдаты, Кутузов, согнувшись на седле, склонил голову, и глаз его засветился кротким, как будто насмешливым, блеском.
– Вот что, братцы, – сказал он, когда замолкли голоса…
И вдруг голос и выражение лица его изменились: перестал говорить главнокомандующий, а заговорил простой, старый человек, очевидно что то самое нужное желавший сообщить теперь своим товарищам.
В толпе офицеров и в рядах солдат произошло движение, чтобы яснее слышать то, что он скажет теперь.
– А вот что, братцы. Я знаю, трудно вам, да что же делать! Потерпите; недолго осталось. Выпроводим гостей, отдохнем тогда. За службу вашу вас царь не забудет. Вам трудно, да все же вы дома; а они – видите, до чего они дошли, – сказал он, указывая на пленных. – Хуже нищих последних. Пока они были сильны, мы себя не жалели, а теперь их и пожалеть можно. Тоже и они люди. Так, ребята?
Он смотрел вокруг себя, и в упорных, почтительно недоумевающих, устремленных на него взглядах он читал сочувствие своим словам: лицо его становилось все светлее и светлее от старческой кроткой улыбки, звездами морщившейся в углах губ и глаз. Он помолчал и как бы в недоумении опустил голову.