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

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

Определение:

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

Сложностный класс задач, решаемых алгоритмом из класса [math]\mathrm{C}[/math] с оракулом для языка [math]\mathrm{A}[/math], обозначают [math]\mathrm{C^A}[/math]. Если [math]\mathrm{A}[/math] — множество языков, то [math]\mathrm{C^A} =\bigcup\limits_{D \in A}\mathrm{C^D}[/math].

Сведение по Тьюрингу

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

Определение:

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