Модифікації машини Тюрінга

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

Еквівалентні звичайній МТ[ред. | ред. код]

Недетермінована МТ[ред. | ред. код]

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

Стрічка обмежена зліва[ред. | ред. код]

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

k-доріжкова машина[ред. | ред. код]

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

k-стрічкова машина[ред. | ред. код]

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

k-голівкова машина[ред. | ред. код]

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

Машина з k-вимірною стрічкою[ред. | ред. код]

Обмежені МТ[ред. | ред. код]

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

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

Лінійно обмежений автомат (ЛОА)[ред. | ред. код]

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

Магазинний автомат (МА)[ред. | ред. код]

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

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

За допомогою автомата з двома магазинами можна промоделювати роботу машини Тьюрінга.

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

Стековий автомат (СА)[ред. | ред. код]

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

Автомат з гніздовою стековою пам'яттю[ред. | ред. код]

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