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

[неперевірена версія][неперевірена версія]
Вилучено вміст Додано вміст
Немає опису редагування
Немає опису редагування
Рядок 1:
 
В теоретичній інформатиці '''недетермінована машина Тюрінга''' — машина Тюрінга, функція переходу якої являє собою недетермінований скінченний автомат.
{{sidebar
| name = Тюрінг
| title = [[Машина Тюрінга|Машини Тюрінга]]
 
| headingclass = navbox-abovebelow
| contentclass = plainlist
 
| heading1 = Варіанти машин
| content1 =
* [[Універсальна машина Тюрінга]]
* [[Альтернативна машина Тюрінга]]
* [[Квантова машина Тюрінга]]
* [[Недетермінована машина Тюрінга]]
* [[Ймовірнісна машина Тюрінга]]
* [[Машина Поста]]
 
| heading2 = Вчені
| content2 =
* [[Алан Тюрінг]]
}}<noinclude>
[[Категорія:Шаблони:Математика|{{PAGENAME}}]]
[[en:Template:Turing]]
[[ru:Шаблон:Тьюринг]]
</noinclude>
 
 
== Опис ==
 
Детермінована [[Машина Тюрінга|машина Тюрінга]] має функцію переходу, яка по комбінаціюкомбінації поточного стану і символу на стрічці визначає три речі: символ, що буде записаний на стрічці, напрямок зміщення головки по стрічці і новий стан скінченного автомату. Наприклад, ''X'' на стрічці в стані 3 однозначно визначає перехід в стан 4, запис на стрічку символу ''Y'' і ​​переміщення головки на одну позицію вліво.
 
[[File:TuringBeispielDiskretAnimatedGIF.gif|thumb|Демонстрація роботи машини Тюрінга]]
 
У випадку з недетермінованою [[Машина Тюрінга|машиною Тюрінга]], комбінація поточного стану автомата і символу на стрічці може допускати кілька переходів. Наприклад, ''X'' на стрічці і стан 3 допускає як стан 4 із записом на стрічку символу ''Y'' та зміщенням головки вправо, так і стан 5 з записом на стрічку символу ''Z'' і зміщенням головки вліво.
 
Як НМТ «дізнається», який з можливих шляхів приведе в допускаєпотрібний стан? Є два способи це уявити.
* Можна вважати, що НМТ - «надзвичайно щаслива»; тобто завжди вибирає перехід, який в кінцевому рахунку призводить до потрібного стану, якщо такий перехід взагалі є.
* Можна уявити, що в разі неоднозначності переходу (поточна комбінація стану і символу на стрічці допускає кілька переходів) НМТ ділиться на кілька НМТ, кожна з яких діє за одним з можливих переходів.