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