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