Вікіпедія

Імовірнісна машина Тюрінга: відмінності між версіями

Інтерактивний перегляд історії
[перевірена версія][перевірена версія]
Наступне редагування →
Вилучено вміст Додано вміст
ВізуальнийВікірозмітка
Створено шляхом перекладу сторінки «Probabilistic Turing machine»
 
Немає опису редагування
Рядок 1:
 
{{Тюрінг}}
У [[Теоретична інформатика|теоретичній інформатиці]] '''ймовірнісна машина Тюрінга'''  — [[недетермінована машина Тюрінга]], яка вибирає між доступними переходами в кожній точці відповідно до деякого [[Розподіл імовірностей|розподілу ймовірностей]]. Як наслідок, імовірнісна машина Тюрінга може  — на відміну від детермінованої машини  — мати [[Стохастичність|стохастичні]] результати; тобто на заданих вхідних даних та набору інструкцій вона може мати різні часи виконання або може не зупинятися взагалі; крім того, може приймати вхідні дані за одного виконання програми та відхиляти ті самі дані за іншого виконання.▼
 
▲У [[Теоретична інформатика|теоретичній інформатиці]] '''ймовірнісна машина Тюрінга''' — [[недетермінована машина Тюрінга]], яка вибирає між доступними переходами в кожній точці відповідно до деякого [[Розподіл імовірностей|розподілу ймовірностей]]. Як наслідок, імовірнісна машина Тюрінга може — на відміну від детермінованої машини — мати [[Стохастичність|стохастичні]] результати; тобто на заданих вхідних даних та набору інструкцій вона може мати різні часи виконання або може не зупинятися взагалі; крім того, може приймати вхідні дані за одного виконання програми та відхиляти ті самі дані за іншого виконання.
 
У випадку рівних імовірностей переходів імовірнісні машини Тюрінга можна визначити як детерміновані [[Машина Тюрінга|машини Тюрінга]], що мають додаткову інструкцію «записати», де записуване значення [[Дискретний рівномірний розподіл|рівномірно розподілене]] в алфавіті машини Тюрінга (загалом, рівна ймовірність запису на стрічку «1» або «0»). Іншим поширеним переформулюванням є просто [[Машина Тюрінга|детермінована машина Тюрінга]] з доданою стрічкою, заповненою випадковими бітами, так званої «випадкової стрічки».
 
[[Квантовий комп'ютер|Квантовий комп’ютер]]  — ще одна модель обчислень, яка за своєю суттю є ймовірнісною.
 
== Опис ==
Імовірнісна машина Тюрінга &nbsp;— це тип [[Недетермінована машина Тюрінга|недетермінованої машини ТьюрингаТюрінга]], в якій кожен недетермінований крок є «підкиданням монети», тобто на кожному кроці є два можливі наступні ходи, і машина Тюрінга ймовірнісним чином вибирає, який хід зробити<ref>{{Cite book
|title=Introduction to the Theory of Computation
|last=Sipser
|first=Michael
|authorlink1=MichaelМайкл SipserСіпсер
|year=2006
|publisher=Thomson Course Technology
Рядок 23 ⟶ 21:
 
== Формальне визначення ==
Імовірнісну машину ТьюрингаТюрінга можна формально визначити як 7-кортеж <math>M=(Q, \Sigma, \Gamma, q_0, A, \delta_1, \delta_2)</math>, де
 
* <math>Q</math> -&nbsp;— скінченна множина станів
* <math>\Sigma</math> -&nbsp;— вхідний алфавіт
* <math>\Gamma</math> -&nbsp;— стрічковий алфавіт, який включає символ пропуску '''#'''
* <math>q_0 \in Q</math> -&nbsp;— початковий стан
* <math>A \subseteq Q</math> -&nbsp;— множина можливих (кінцевих) станів
* <math>\delta_1: Q \times \Gamma \to Q \times \Gamma \times \{L,R\} </math> -&nbsp;— перша ймовірнісна функція переходу. <math>L</math> -&nbsp;— переміщення на одну клітинку вліво на стрічці машини Тюрінга і <math>R</math> -&nbsp;— переміщення на одну клітинку вправо.
* <math>\delta_2: Q \times \Gamma \to Q \times \Gamma \times \{L,R\} </math> -&nbsp;— друга ймовірнісна функція переходу.
 
На кожному кроці машина Тьюрінга ймовірнісно застосовує або функцію переходу <math>\delta_1</math> або функцію переходу <math>\delta_2</math><ref>{{Cite book
Рядок 43 ⟶ 41:
|page=125
|isbn=978-0-521-42426-4
|author2-link=BoazБоаз BarakБарак
}}</ref>. Цей вибір робиться незалежно від усіх попередніх виборів. Тобто, процес вибору функції переходу на кожному кроці обчислення нагадує підкидання монети.
 
Рядок 53 ⟶ 51:
== Класи складності ==
{{Нерозв'язано|інформатики|Чи {{noitalic|'''P''' {{=}} '''BPP'''}} ?}}
В результаті помилки, внесеної використанням імовірнісного "«підкидання монети"», поняття прийняття рядка ймовірнісною машиною Тюрінга можна визначити різними способами. Одне з таких понять, яке включає кілька важливих класів складності, передбачає ймовірність помилки 1/3. Наприклад, клас складності '''[[Клас складності BPP|BPP]]''' визначається як клас мов, розпізнаних імовірнісною машиною Тюрінга за [[Часова складність|поліноміальний час]] із імовірністю помилки 1/3. Іншим класом, визначеним з використанням цього поняття прийнятності, є '''{{Нп|BPL (складність)|BPL|en|BPL (complexity)}}''', який є таким самим, як і '''BPP,''' але накладає додаткове обмеження на те, що мови повинні бути розв'язними в [[Логарифмічне зростання|логарифмічному]] [[Просторова складність|просторі]].
 
[[Клас складності|Класи складності]], що випливають з інших визначень прийнятності, включають '''{{Нп|RP (складність)|RP|en|RP (complexity)}}''', '''co-RP''' та '''{{Нп|ZPP (складність)|ZPP|en|ZPP (complexity)}}'''. Якщо машину обмежити логарифмічним обсягом замість поліноміального часу, виходять аналогічні класи складності '''{{Нп|RL (складність)|RL|en|RL (complexity)}}''', '''co-RL''' і '''[[Класи складності L і NL|ZPL]]'''. Застосовуючи обидва обмеження, маємо класи складності '''RLP''', '''co-RLP''', '''{{Нп|BPL (складність)|BPLP|en|BPL (complexity)}}''' і '''ZPLP'''.
Рядок 59 ⟶ 57:
Імовірнісне обчислення також має вирішальне значення для визначення більшості класів {{Нп|Інтерактивна система доведення|інтерактивних систем доведення|en|Interactive proof system}}, в яких верифікаційна машина залежить від випадковості, щоб уникнути передбачення та обману всемогутньою машиною перевірки. Наприклад, клас '''{{Нп|IP (складність)|IP|en|IP (complexity)}}''' дорівнює '''[[Клас складності PSPACE|PSPACE]]''', але якщо з верифікатора усунути випадковість, ми залишимо лише '''[[Клас складності NP|NP]]''', про який невідомо, але вважають, що він є значно меншим класом.
 
Одне з центральних питань теорії складності полягає в тому, чи додає випадковість сили; тобто чи існує проблема, яку можна розв’язатирозв'язати за поліноміальний час імовірнісною машиною Тюрінга, але не детермінованою машиною Тюрінга? Або чи можуть детерміновані машини Тюрінга ефективно симулювати всі імовірнісні машини Тюрінга з уповільненням щонайбільше поліноміальним? Відомо, що '''P''' ⊆⊆ '''BPP''', оскільки детермінована машина Тюрінга є лише окремим випадком імовірнісної машини Тюрінга. Однак невідомо (але багато хто припускає це), чи '''BPP''' ⊆⊆ '''P''', що означає, що '''BPP''' = '''P'''. Те саме питання щодо логарифмічного обсягу замість поліноміального часу (чи '''L''' = '''BPLP'''?) ще більше вважають істинним. З іншого боку, потужність, якої випадковість надає інтерактивним системам доведень, а також прості алгоритми, які вона створює для складних задач, таких як [[Тест простоти|перевірка простоти]] за поліноміальний час і перевірка [[Зв'язний граф|зв’язностізв'язності]] графа в логарифмічному обсязі, припускають, що випадковість може додати потужності.
 
== Див. також ==
 
* [[Увипадковлений алгоритм]]
 
Рядок 69 ⟶ 66:
 
== Посилання ==
 
* [https://xlinux.nist.gov/dads/HTML/probablturng.html Веб-сайт NIST про ймовірнісні машини Тюрінга] {{Ref-en}}
 
{{Бібліоінформація}}{{DEFAULTSORT:Probabilistic Turing Machine}}
[[Категорія:Увипадковлені алгоритми]]
[[Категорія:Моделі обчислень]]
Отримано з https://uk.wikipedia.org/wiki/Імовірнісна_машина_Тюрінга