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

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

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

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

Опис

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

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

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

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

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

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

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

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

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

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

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

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

Див. також

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

Посилання

• Веб-сайт NIST про ймовірнісні машини Тюрінга Шаблон:Ref-en