Изменения

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

Оракул — абстракция , вычисляющая за <tex>O(1)</tex> времени, верно ли, что <tex>x</tex> принадлежит множеству <tex>A</tex>.

В теории вычислимости, сведение по Тьюрингу задачи A к задаче B — это сведение, которое решает A, предполагая, что B уже известно. Это можно понимать как алгоритм, который может быть использован для решения A, если в его распоряжении имеются подпрограммы для решения B. Более формально, сведение по Тьюрингу является функцией, вычислимой машиной с оракулом для В.