Функционирование машины Тьюринга

Понятие машины Тьюринга и ее функционирование

Устройство одноленточной машины Тьюринга включает в себя:

Внешний алфавит А - конечное множество символов. В этом алфавите в виде слова кодируется та информация, которая подается в машину. Машина преобразует информацию, поданную в виде слова, в новое слово.

Внутренний алфавит (внутренняя память машины), состоящий из конечного множества состояний

Q= { q ₀, q ₁ ,..., q_m } .

Алфавит сдвиговS = { l, s, r }, где l, s, r соответственно означают сдвиг некоторого символа влево, оставить символ на месте, сдвиг символа вправо.

Кроме того, в конфигурации машины имеются:

А) бесконечная в обе стороны лента (внешняя память машины). Она разбита на клетки. В каждую клетку может быть записана только одна буква из алфавита А, включая пустой символ (пробел), который мы будем обозначать через а0.

б) управляющая головка (считывающе-записывающее устройство). Она обладает способностью передвигаться вдоль ленты и может останавливаться напротив какой-либо клетки, то есть обозревать одну ячейку ленты, считывать букву, записанную в эту ячейку, заносить на место считываемой буквы любую другую, в том числе пустой символ а ₀ (то есть стирать в ячейке символ).

В одном такте работы машины управляющая головка может сдвигаться влево или вправо только на одну клетку или может оставаться на месте;

в) устройство управления, которое управляет работой машины с помощью программы;

г) программа машины, определяющая переходы машины от одной конфигурации к другой, то есть от одного состояния q_i вместе с содержимым обозреваемой клетки на данном такте работы к другому состоянию q_j вместе с соответствующим содержимым обозреваемой клетки на следующем такте работы машины.

Важна не фактическая (актуальная) бесконечность ленты, а ее неограниченность, то есть возможность писать на ней сколь угодно длинные, но конечные слова. Данные в машине Тьюринга – это слова в алфавите А. На ленте записываются исходные данные, и окончательные результаты. Элементарные шаги машины – это считывание и запись символов, сдвиг головки на одну ячейку влево или вправо, а также переход управляющего устройства в следующее состояние.

Последовательность шагов машины Тьюринга определяется следующим образом: для любого внутреннего состояния q_i и символа а_j однозначно заданы:

o а) следующее состояние q_t;

o б) буква а_v, которую нужно записать вместо а_j в ту же ячейку (стирание символа будем понимать как запись пустого символа а ₀);

o в) направление сдвига головки d_k, обозначаемое одним из символов l, s, r.

Это задание может описываться либо системой правил (команд), имеющих вид:

q_iа_j→ q_ta_vd_k, (*)

либо таблицей, строкам которой соответствуют состояния, столбцам – входные символы, а на пересечении строки q_i и столбца а_j записана тройка символов q_tа_vd_k, и, наконец, диаграммой переходов (орграфом).

На этой диаграмме состояниям соответствуют вершины, а команде вида (*) – дуга, ведущая из вершины q_i в вершину q_t, на которой написано а_j → a_vd_k. Условие однозначности требует, чтобы для любого j и любого i ¹ 0 в системе команд имелась одна команда, аналогичная команде (*) с левой частью q_ia_j; состояние q ₀ в левых частях команд не встречается.

На диаграмме переходов это выражается условием, что из каждой вершины, кроме q ₀, выходит ровно n дуг, причем на разных дугах левые части различны; в вершине q ₀ нет выходящих дуг.

Из отдельных команд машины Тьюринга составляется программа этой машины.

Программа машины Тьюринга – это отображение

f: A × Q \ { q ₀} → A × Q × S,

Головка считывает букву, находящуюся в обозреваемой ячейке. Устройство управления обращается к программе машины, находит в таблице клетку, соответствующую считанной букве и состоянию машины. Пусть в этой клетке находится тройка (а_v, q_t, d_k).