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

Машини Тюрінга
Машина
Модифікації машини Тюрінга Приклади машини Тюрінга Галерея машин Тюрінга
Варіанти
Змінна машина Тюрінга Нейронна машина Тюрінга Недетермінована машина Тюрінга Квантова машина Тюрінга Машина Поста-Тюрінга Імовірнісна машина Тюрінга Незмінна машина Тюрінга Незмінна машина Тюрінга з рухом праворуч Багатострічкова машина Тюрінга Багатодоріжкова машина Тюрінга Симетрична машина Тюрінга Повна машина Тюрінга Однозначна машина Тюрінга Універсальна машина Тюрінга Машина Зенона
Науковці
Алан Тюрінг Еміль Пост

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

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

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

Опис

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також

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

Посилання

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