Модифікації машини Тюрінга
Ця стаття потребує істотної переробки. (1 квітня 2024) |
Машина Тюрінга (МТ) може мати різні модифікації:
Еквівалентні звичайній МТ[ред. | ред. код]
Недетермінована МТ[ред. | ред. код]
Може перебувати в кількох конфігураціях одночасно. Еквівалентна звичайній МТ.
Стрічка обмежена зліва[ред. | ред. код]
Читаюча голівка не може переміщуватись лівіше початкового символу. Еквівалентна звичайній МТ.
k-доріжкова машина[ред. | ред. код]
Голівка може змінювати символ на певній доріжці окремо. Моделюється звичайною МТ, якщо брати алфавіт звичайної як k-ту степінь алфавіту k-доріжкової.
k-стрічкова машина[ред. | ред. код]
На відміну від k-доріжкової, тут кожна стрічка має свою головку, які можуть рухатись окремо. Моделюється 2k стрічковою машиною, тому теж еквівалентна звичайній МТ.
k-голівкова машина[ред. | ред. код]
Машина яка має k-голівок, і одну стрічку.
Машина з k-вимірною стрічкою[ред. | ред. код]
Обмежені МТ[ред. | ред. код]
Машина без запису на вхідну стрічку (off-line)[ред. | ред. код]
Такі машини поділяються на односторонні (голівка може рухатись в обидві сторони), та двосторонні (тільки в одну). Наприклад скінченний автомат є односторонньою off-line МТ.
Лінійно обмежений автомат (ЛОА)[ред. | ред. код]
МТ з стрічкою що обмежена розмірами вхідного слова
Магазинний автомат (МА)[ред. | ред. код]
Такий автомат має обмежений набір операцій зі стрічкою, а саме:
- Дописати символ в кінці робочої зони, і пересунутись вправо.
- Пересунутись вліво, і витерти символ під голівкою (замінити на ).
За допомогою автомата з двома магазинами[de] (англ. TPDA, 2-PDA) можна промоделювати роботу машини Тьюрінга.[1]
Магазин з унарним алфавітом називається лічильником. Два лічильники можуть промоделювати роботу магазину.
Цей розділ потребує доповнення. (квітень 2010) |
Стековий автомат (СА)[ред. | ред. код]
Аналогічний МА, але крім цього вміє читати символи з середини стрічки.
Автомат з гніздовою стековою пам'яттю[ред. | ред. код]
Аналогічний стековому автомату, але вміє в будь-який момент поділити стек на два, додавши спеціальний символ C. Стек склеюється назад, як тільки цей символ видаляється. Працюючи з певною частиною стеку, її теж можна ділити.
Ця стаття не містить посилань на джерела. (квітень 2010) |
- ↑ @MISC {2833, TITLE = {Is a push-down automaton with two stacks equivalent to a turing machine?}, AUTHOR = {Luke Mathieson (https://cs.stackexchange.com/users/1636/luke-mathieson)}, HOWPUBLISHED = {Computer Science Stack Exchange}, NOTE = {URL:https://cs.stackexchange.com/q/2833 (version: 2019-02-18)}, EPRINT = {https://cs.stackexchange.com/q/2833}, URL = {https://cs.stackexchange.com/q/2833} }