Імовірнісна машина Тюрінга

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

У випадку рівних імовірностей переходів імовірнісні машини Тюрінга можна визначити як детерміновані машини Тюрінга, що мають додаткову інструкцію «записати», де записуване значення рівномірно розподілене в алфавіті машини Тюрінга (загалом, рівна ймовірність запису на стрічку «1» або «0»). Іншим поширеним переформулюванням є просто детермінована машина Тюрінга з доданою стрічкою, заповненою випадковими бітами, так званої «випадкової стрічки».

Квантовий комп'ютер — ще одна модель обчислень, яка за своєю суттю є ймовірнісною.

Опис

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

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

Імовірнісну машину Тюрінга можна формально визначити як 7-кортеж ${\displaystyle M=(Q,\Sigma ,\Gamma ,q_{0},A,\delta _{1},\delta _{2})}$, де

• ${\displaystyle Q}$ — скінченна множина станів
• ${\displaystyle \Sigma }$ — вхідний алфавіт
• ${\displaystyle \Gamma }$ — стрічковий алфавіт, який включає символ пропуску #
• ${\displaystyle q_{0}\in Q}$ — початковий стан
• ${\displaystyle A\subseteq Q}$ — множина можливих (кінцевих) станів
• ${\displaystyle \delta _{1}:Q\times \Gamma \to Q\times \Gamma \times \{L,R\}}$ — перша ймовірнісна функція переходу. ${\displaystyle L}$ — переміщення на одну клітинку вліво на стрічці машини Тюрінга і ${\displaystyle R}$ — переміщення на одну клітинку вправо.
• ${\displaystyle \delta _{2}:Q\times \Gamma \to Q\times \Gamma \times \{L,R\}}$ — друга ймовірнісна функція переходу.

На кожному кроці машина Тьюрінга ймовірнісно застосовує або функцію переходу ${\displaystyle \delta _{1}}$ або функцію переходу ${\displaystyle \delta _{2}}$. Цей вибір робиться незалежно від усіх попередніх виборів. Тобто, процес вибору функції переходу на кожному кроці обчислення нагадує підкидання монети.

Імовірнісний вибір функції переходу на кожному кроці вносить помилку в машину Тюрінга; тобто рядки, які має приймати машина Тюрінга, у деяких випадках можуть бути відхилені, а рядки, які машина Тюрінга має відхиляти, можуть у деяких випадках бути прийнятими. Щоб це врахувати, мову ${\displaystyle L}$ називають розпізнаною з імовірністю помилки ${\displaystyle \epsilon }$ ймовірнісною машиною Тюрінга ${\displaystyle M}$ якщо:

1. рядок ${\displaystyle w}$ в ${\displaystyle L}$ означає, що ${\displaystyle {\text{Pr}}[M{\text{ приймає }}w]\geq 1-\epsilon }$
2. рядок ${\displaystyle w}$ не в ${\displaystyle L}$ означає, що ${\displaystyle {\text{Pr}}[M{\text{ відкидає }}w]\geq 1-\epsilon }$

Класи складності

Нерозв'язана проблема інформатики: Чи P = BPP ?

В результаті помилки, внесеної використанням імовірнісного «підкидання монети», поняття прийняття рядка ймовірнісною машиною Тюрінга можна визначити різними способами. Одне з таких понять, яке включає кілька важливих класів складності, передбачає ймовірність помилки 1/3. Наприклад, клас складності BPP визначається як клас мов, розпізнаних імовірнісною машиною Тюрінга за поліноміальний час із імовірністю помилки 1/3. Іншим класом, визначеним з використанням цього поняття прийнятності, є ^[en], який є таким самим, як і BPP, але накладає додаткове обмеження на те, що мови повинні бути розв'язними в логарифмічному просторі.

Класи складності, що випливають з інших визначень прийнятності, включають ^[en], co-RP та ^[en]. Якщо машину обмежити логарифмічним обсягом замість поліноміального часу, виходять аналогічні класи складності ^[en], co-RL і ZPL. Застосовуючи обидва обмеження, маємо класи складності RLP, co-RLP, ^[en] і ZPLP.

Імовірнісне обчислення також має вирішальне значення для визначення більшості класів ^[en], в яких верифікаційна машина залежить від випадковості, щоб уникнути передбачення та обману всемогутньою машиною перевірки. Наприклад, клас ^[en] дорівнює PSPACE, але якщо з верифікатора усунути випадковість, ми залишимо лише NP, про який невідомо, але вважають, що він є значно меншим класом.

Одне з центральних питань теорії складності полягає в тому, чи додає випадковість сили; тобто чи існує проблема, яку можна розв'язати за поліноміальний час імовірнісною машиною Тюрінга, але не детермінованою машиною Тюрінга? Або чи можуть детерміновані машини Тюрінга ефективно симулювати всі імовірнісні машини Тюрінга з уповільненням щонайбільше поліноміальним? Відомо, що P ⊆ BPP, оскільки детермінована машина Тюрінга є лише окремим випадком імовірнісної машини Тюрінга. Однак невідомо (але багато хто припускає це), чи BPP ⊆ P, що означає, що BPP = P. Те саме питання щодо логарифмічного обсягу замість поліноміального часу (чи L = BPLP?) ще більше вважають істинним. З іншого боку, потужність, якої випадковість надає інтерактивним системам доведень, а також прості алгоритми, які вона створює для складних задач, таких як перевірка простоти за поліноміальний час і перевірка зв'язності графа в логарифмічному обсязі, припускають, що випадковість може додати потужності.

Див. також

• Увипадковлений алгоритм

Примітки

1. (2006). Introduction to the Theory of Computation (вид. 2nd). USA: Thomson Course Technology. с. 368. ISBN .
2. Arora, Sanjeev; (2016). Computational Complexity: A Modern Approach. Cambridge University Press. с. 125. ISBN .

Посилання

• Веб-сайт NIST про ймовірнісні машини Тюрінга (англ.)