Машина Тюрінга

Машина Тюрінга – це пристрій, що складається з центру управління, а також ряду осередків.

Керуючий пристрій даної машини має можливість рухатися по ряду осередків, і зчитувати всі значення, які їм присвоєні.

Для роботи машини Тюрінга написаний алгоритм, який спрямований на роботу керуючого пристрою. Даний алгоритм дозволяє задавати значення того осередку, в якій знаходиться керуючий пристрій. Так само можна задати деяку дію пристрою в даній комірці.

Для завдання значень осередків в машині Тьюринга використовують обмежений алфавіт. А для переходу від одного значення до іншого використовують наступну команду:

q1a1 -> q2a2D.

Зліва від команди написано стан або значення даного осередку в даний момент часу, а праворуч значення, яке матиме ця група після зміни властивостей. D – це пересування керуючого пристрою. Якщо на місці цієї букви варто L, то необхідно керуючий пристрій необхідно пересунути вліво, якщо R – то вправо, а якщо N, то залишитися на місці.

Посилання на основну публікацію