Алгоритм з оракулом

В теорії складності і теорії обчислюваності, пророча машина (англ. oracle machine) — це абстрактний автомат використовний для вивчення задач вибору. Його можна зобразити як машину Тюрінга з чорною скринею, званою оракулом, яка здатна розв'язувати певні задачі вибору за одну дію. Задача може бути будь-якого класу складності. Можна використовувати навіть нерозв'язні задачі, такі як проблема зупинки.

Визначення

Пророча машина — машина Тюрінга під'єднана до оракула. Пророк, в цьому розрізі, розглядається як сутність здатна відповідати на набір питань, і, зазвичай, представлена як деяка підмножина натуральних чисел — A. Тоді інтуітивно, пророча машина може виконувати всі звичайні дії машини Тюрінга і також може запитати у пророка відповідь на питання у формі «чи x належить A?»

Наведене визначення є одним з можливих визначень пророчої машини. Всі ці визначення тотожні, бо всі вони покладаються на якусь особливу функцію f, що може бути обчислена пророчою машиною за допомогою оракула A.

Пророча машина, подібно до машини Тюрінга, має:

• робочу стрічку: послідовність комірок без початку чи кінця, кожна з яких може містити П (для порожнього значення) або 1;
• голівку читання/запису, яка знаходиться над конкретною коміркою і може прочитати звідти дані, записати туди нові дані, і зсунутись ліворуч або праворуч уздовж стрічки;
• керівний пристрій, який може знаходитись в одному зі скінченної кількості станів, і який буде виконувати різні дії (читати дані, записувати дані, рухати голівку і змінювати стани) залежно від поточного стану і прочитаного значення.

В додаток до цих вузлів, пророча машина також має:

• стрічку оракула, на якій надрукована нескінченна послідовність П і 1, відповідно до характеристичної функції множини A пророка;
• голівку оракула, яка (подібно до голівки читання/запису) може рухатись ліворуч і праворуч уздовж стрічки пророка, читаючи дані, але не може записувати (проте існують альтернативні визначення пророчої машини, які дозволяють записувати дані).

Формальне визначення

Пророча машина Тюрінга — це четвірка ${\displaystyle M=\langle Q,\delta ,q_{0},F\rangle }$ де

• ${\displaystyle Q}$ — скінченна множина станів;
• ${\displaystyle \delta :Q\times \{B,1\}^{2}\rightarrow Q\times \{B,1\}\times \{L,R\}^{2}}$ — функція переходів, де L — це зсув ліворуч, R — зсув праворуч;
• ${\displaystyle q_{0}\in Q}$ — початковий стан;
• ${\displaystyle F\subseteq Q}$ — множина станів зупинки.

Пророча машина ініціалізується робочою стрічкою із вхідними даними у вигляді скінченної кількості 1, залишок стрічки порожній, стрічка оракула містить характеристичну функцію оракула, A, машина Тюрінга перебуває в стані q₀ із голівкою читання/запису над першою непорожньою коміркою робочої стрічки, голівка пророка читає читає комірку стрічки пророка відповідну до ${\displaystyle \chi _{A}(0)}$. Після цього відбуваються дії відповідно до ${\displaystyle \delta }$: якщо машина Тюрінга наразі в стані q, голівка читання/запису читає символ S₁, а голівка пророка читає символ S₂ тоді, якщо ${\displaystyle \delta (q,S_{1},S_{2})=(q',S_{1}',D_{1},D_{2})}$, машина переходить в стан ${\displaystyle q'}$, голівка читання/запису записує S₁' замість S₁, і тоді голівка читання/запису зсувається на одну комірку в напрямку D₁ і голівка оракула зсувається на одну комірку в напрямку D₂. Якщо ${\displaystyle q'}$ це стан зупинки, машина зупиняється, інакше повторюються попередні дії.

Зведення за Тюрінгом

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

Поняття

Цю допоміжну функцію або алгоритм також називають відносним алгоритмом або алгоритмом з оракулом. Будемо позначати його через J, він визначений (тобто такий, що дає результат) на множині всіх можливих станів S. Оракул А буде підмножиною J(S).

Кожний крок процесу, що задається алгоритмом з оракулом, визначається не тільки станом S, що виник до цього кроку, але й істинністю твердження J(S) Є А. Таким чином, оператор безпосередньої переробки, що дає наступний стан S*, стає тепер функцією від двох аргументів — від S і від числа b, що приймає значення 0 чи 1, в залежності від того чи правильне співвідношення J(S) Є А.

Поняття алгоритму з оракулом виявилось важливим з методологічної точки зору. Зокрема, теорія алгоритмів використовує поняття елементарної операції. Поняття елементарності — істотно «людське» поняття. Те, що елементарно для людини, може виявитись неелементарним для інших істот, і навпаки. Можна вважати, що людина, здійснюючи обчислення, безперервно звертається до деякого оракула, тільки оракул цей відповідає на такі «елементарні» запитання (типу «Тотожні чи ні ці два символи?»), що це навіть не помітно. Можна уявити собі більш потужний, ніж у людини, запас обчислювальних засобів, що мають на увазі зокрема, звернення до деякого нетривіального (з людської точки зору) оракула (який в рамках цих засобів не усвідомлюється скоріше всього, ніж зовнішній оракул, а вважається частиною самих цих засобів).

Висловлені міркування підтверджуються наступними спробами аксіоматично визначити поняття обчислюваної функції. Аналізуючи докази, що зустрічаються в теорії обчислюваних функцій, можна помітити, що можливий— і навіть іноді використовується — наступний спосіб міркувань. Спочатку встановлюються деякі основні та інтуїтивно очевидні властивості класу обчислюваних функцій, а потім необхідні твердження виводяться із них.

Основні властивості класу К всіх обчислюваних функцій

(1) Аксіома функціональних констант.

Клас К містить всі обчислювані числові функції.

Або Клас К містить константу 0 і функцію слідування.

(2) Аксіома операторних констант.

Клас К замкнутий відносно операторів підстановки, рекурсії та мінімізації.

Ця властивість застосовується, якщо із твердження про приналежність до К яких-небудь функцій необхідно вивести твердження про приналежність до К деякої іншої функції, що виражається через перші.

(3) Аксіома протоколу.

Для будь-якої функції f із класу К існують :

1. множина натуральних чисел Е, характеристична функція якої лежить в К ;

2. функції а і b, визначені на всіх елементах Е, що належать К і задовольняють умові: значення функції f на числі x: дорівнює у тоді і тільки тоді, коли існує таке q із Е,
що а (q) = х і b (q) = у.

Змістова інтерпретація цієї аксіоми така:

Ми припускаємо, що для кожного обчислення існує його протокол (запис), що являє собою послідовність змінюючих один одного станів

алгоритмічного процесу. Множина Е є множиною кодів всіх таких протоколів. У випадку, коли К — просто клас всіх обчислюваних числових

функцій, множина всіх протоколів розв'язана, і, відповідно, характеристична функція Е в цьому випадку належить К. Функції а і b

виділяють із коду протоколу вихідне дане та результат обчислення.

(4) Аксіома універсальної функції.

В класі К існує двомісна функція, універсальна для всіх одномісних функцій із К («універсальність» U (х, у) означає,

що ∀ f Є K ∃ x ∀ y f (y)≅U (x, y)).

Як основа теорії обчислювальних функцій ці аксіоми набагато більше очевидні, ніж теза Черча. Насправді, вони не дозволяють стверджувати, що деякі функції необчислювані. На противагу цьому найбільше неочевидна частина тези Черча стверджує, що функції, необчислювані на моделі, необчислювані і будь-яким іншим чином.

Крім інших переваг аксіоматичного підходу — наприклад, заміни складних прямих конструкцій короткими аксіомами — є наступні переваги. Перша полягає в тому, що дані аксіоми не тільки більш очевидні, але також і менш технічні, ніж теза Черча. Друга перевага (і недолік) полягає в тому, що аксіоматична система може мати (і має) різні моделі.

Дійсно, чотири перераховані вище аксіоми виконуються не тільки для класу всіх обчислюваних функцій, але і для будь-якого класу всіх функцій, обчислюваних з даним оракулом. Таким чином, всі теореми, що виводяться із (1) — (4), виконані для будь-якого такого класу. Це пояснює можливість «релятивізації» багатьох теорем. І навпаки, тільки ті теореми, які випливають із аксіом (1) — (4), можливо релятивізувати. Дійсно, будь-який клас функцій, що задовольняють цим аксіомам, в дійсності є класом всіх функцій, обчислюваних з деяким фіксованим оракулом. Таким чином, з теоретичної сторони поняття алгоритму з оракулом дозволяє релятивізувати теорію алгоритмів. З більш практичної сторони воно дозволяє дати точне визначення загального поняття збіжності за розв'язністю і, отже, дати точне формулювання фундаментальної проблеми збіжності. Дійсно, тепер можна ввести наступне визначення. Множина Q збігається за Тюрінгом (збігається за розв'язністю) до множини Р тоді і тільки тоді, коли існує відносний алгоритм, що обчислює характеристичну функцію множини Q відносно множини Р, або, в оракульних термінах існує алгоритм з оракулом Р, що обчислює цю характеристичну функцію. Поняття алгоритму з оракулом і сам термін «оракул» вперше з'явились в статті Тюрінга, тому Пост ввів термін «збіжність за Тюрінгом» для позначення збіжності проблеми вирішення найзагальнішого виду.

Важливим і природним частинним випадком збіжності за Тюрінгом є збіжність за поліноміальний час. (Вона визначається заданням поліноміального — від довжини входу — обмеження на час роботи алгоритму з оракулом). Природно поставити проблему поліноміальної за часом збіжності: чи всі множини із класу NP \ P збігаються один до одного за поліноміальний час? (Звичайно, якщо NP = P, то проблема тривіальна). Завідомо збігаються один до одного за поліноміальний час багато представників класу NP, що виникли із математичної практики; до кожного із таких представників всі множини із NP збігаються за поліноміальний час. Невідомо, чи збігаються за поліноміальний час всі множини із NP до множин всіх пар ізоморфних графів.

Див. також

• Теза Черча
• Машина Тюрінга

Примітки

1. van Melkebeek, Dieter (2000). Randomness and Completeness in Computational Complexity. Lecture Notes in Computer Science (англ.). Springer (1950).

Посилання

• на сайті Принстонського університету (англ.)