Изменения

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

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

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

Даны два множества натуральных чисел <tex>A</tex> и <tex>B</tex>, тогда говорим, что <tex>A</tex> сводится по Тьюрингу к <tex>B</tex> (<tex>A \leq_{\widetilde{T}} B</tex>), если есть машина с оракулом <tex>B</tex>, которая вычисляет характеристическую функцию <tex>A</tex>. В этом случае мы также говорим, что <tex>A</tex> является <tex>B</tex>-рекурсивным и <tex>B</tex>-вычислимым.