Магазинний автомат

Машина Тюрінга (МТ) може мати різні модифікації:

Еквівалентні звичайній МТ

Недетермінована МТ

Може перебувати в кількох конфігураціях одночасно. Еквівалентна звичайній МТ.

Стрічка обмежена зліва

Читаюча голівка не може переміщуватись лівіше початкового символу. Еквівалентна звичайній МТ.

k-доріжкова машина

Голівка може змінювати символ на певній доріжці окремо. Моделюється звичайною МТ, якщо брати алфавіт звичайної як k-ту степінь алфавіту k-доріжкової.

k-стрічкова машина

На відміну від k-доріжкової, тут кожна стрічка має свою головку, які можуть рухатись окремо. Моделюється 2^k стрічковою машиною, тому теж еквівалентна звичайній МТ.

k-голівкова машина

Машина яка має k-голівок, і одну стрічку.

Машина з k-вимірною стрічкою

Обмежені МТ

Машина без запису на вхідну стрічку (off-line)

Такі машини поділяються на односторонні (голівка може рухатись в обидві сторони), та двосторонні (тільки в одну). Наприклад скінченний автомат є односторонньою off-line МТ.

Лінійно обмежений автомат (ЛОА)

МТ з стрічкою що обмежена розмірами вхідного слова

Магазинний автомат (МА)

Такий автомат має обмежений набір операцій зі стрічкою, а саме:

1. Дописати символ ${\displaystyle \neq \lambda }$ в кінці робочої зони, і пересунутись вправо.
2. Пересунутись вліво, і витерти символ під голівкою (замінити на ${\displaystyle \lambda }$).

За допомогою ^[de] (англ. TPDA, 2-PDA) можна промоделювати роботу .

Магазин з унарним алфавітом називається лічильником. Два лічильники можуть промоделювати роботу магазину.

Стековий автомат (СА)

Аналогічний МА, але крім цього вміє читати символи з середини стрічки.

Автомат з гніздовою стековою пам'яттю

Аналогічний стековому автомату, але вміє в будь-який момент поділити стек на два, додавши спеціальний символ C. Стек склеюється назад, як тільки цей символ видаляється. Працюючи з певною частиною стеку, її теж можна ділити.

Примітки

1. @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} }

Джерела

• Hopcroft, John E.; ; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521.(англ.)