Пророча машина

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Визначення[ред.ред. код]

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

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

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

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

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

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

Формальне визначення[ред.ред. код]

Пророча машина Тюринга це четвірка M= \langle Q, \delta, q_0, F \rangle де

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

Пророча машина ініціалізується робочою стрічкою із вхідними даними у вигляді скінченної кількості 1, залишок стрічки порожній, стрічка оракула містить характеристичну функцію оракула, A, машина Тьюрінга перебуває в стані q0 із голівкою читання/запису над першою непорожньою коміркою робочої стрічки, голівка пророка читає читає комірку стрічки пророка відповідну до \chi_A(0). Після цього відбуваються дії відповідно до \delta: якщо машина Тюрінга наразі в стані q, голівка читання/запису читає символ S1, а голівка пророка читає символ S2 тоді, якщо \delta(q,S_1,S_2)=(q',S_1',D_1,D_2), машина переходить в стан q', голівка читання/запису записує S1' замість S1, і тоді голівка читання/запису зсувається на одну комірку в напрямку D1 і голівка оракула зсувається на одну комірку в напрямку D2. Якщо q' це стан зупинки, машина зупиняється, інакше повторюються попередні дії.

Посилання[ред.ред. код]