PROFILPELAJAR.COM

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

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

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

Опис

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

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

Імовірнісну машину Тюрінга можна формально визначити як 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}$ ^[2]. Цей вибір робиться незалежно від усіх попередніх виборів. Тобто, процес вибору функції переходу на кожному кроці обчислення нагадує підкидання монети.

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

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

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

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

Чи P = BPP ?

(більше нерозв'язаних проблем інформатики)

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

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

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

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

Див. також

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

Примітки

↑ Sipser, Michael (2006). Introduction to the Theory of Computation (вид. 2nd). USA: Thomson Course Technology. с. 368. ISBN 978-0-534-95097-2.
↑ Arora, Sanjeev; Barak, Boaz (2016). Computational Complexity: A Modern Approach. Cambridge University Press. с. 125. ISBN 978-0-521-42426-4.