Обчислення з оракулом

У теорії обчислень та теорії складності "машиною з оракулом" називають абстрактну машину, призначену для вирішення будь-якої проблеми розв'язності. Така машина може бути представлена ​​як машина Т'юрінга, доповнена оракулом з невідомим внутрішнім пристроєм. Постулюється, що оракул здатний вирішити певні проблеми розв'язання за один такт машини Тьюринга. Машина Тьюринга взаємодіє з оракулом шляхом запису свою стрічку вхідних даних для оракула і потім його запуском виконання. За один крок оракул обчислює функцію, стирає вхідні дані та пише вихідні дані на стрічку. Іноді машина Тьюринга описується як має дві стрічки, одна призначена для вхідних даних оракула, інша для вихідних.

Визначення:

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

Відомості по Тьюрингу [ред.]

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

---