editor
143
правки
Изменения
Нет описания правки
В теории вычислений и теории сложности Машиной "машиной с оракулом " называют абстрактную машину, предназначенную для решения какой-либо проблемы разрешимости. Такая машина может быть представлена как машина Тьюринга, дополненная оракулом с неизвестным внутренним устройством. Постулируется, что оракул способен решить определенные проблемы разрешимости за один такт машины Тьюринга. Машина Тьюринга взаимодействует с оракулом путем записи на свою ленту входных данных для оракула и затем его запуском оракула на исполнение. За один шаг оракул вычисляет функцию, стирает входные данные и пишет выходные данные на ленту. Иногда машина Тьюринга описывается как имеющая две ленты, одна предназначена для входных данных оракула, другая — для выходных.
{{Определение
|definition=
Оракул — программа <tex>A(x)</tex>абстракция, вычисляющая за <tex>O(1)</tex> времени, верно ли, что <tex>x \in </tex> принадлежит множеству <tex>A</tex>.
}}
Сложностный класс задач, решаемых алгоритмом из класса <tex>\mathrm{C}</tex> с оракулом для языка <tex>\mathrm{A}</tex>, обозначают <tex>\mathrm{C^A}</tex>.
Если <tex>\mathrm{A}</tex> — множество языков, то <tex>\mathrm{C^A} =\bigcup\limits_{D \in A}\mathrm{C^D}</tex>.
== Сведение по Тьюрингу ==
В теории вычислимости сведение по Тьюрингу задачи A к задаче B — это сведение, которое решает A, предполагая, что B уже известно. Это можно понимать как алгоритм, который может быть использован для решения A, если в его распоряжении имеются подпрограммы для решения B. Более формально, сведение по Тьюрингу является функцией, вычислимой машиной с оракулом для В.
{{Определение
|definition =
Даны два множества натуральных чисел <tex>A</tex> и <tex>B</tex>, тогда говорим, что <tex>A</tex> сводится по Тьюрингу к <tex>B</tex> (<tex>A \leq_{T} B</tex>), если есть машина с оракулом <tex>B</tex>, которая вычисляет характеристическую функцию <tex>A</tex>. В этом случае мы также говорим, что <tex>A</tex> является <tex>B</tex>-рекурсивным и <tex>B</tex>-вычислимым.
}}
[[Категория: Теория сложности]]
