3. Пример: умножение чисел в унарной системе счисления

Приведём пример МТ для умножения чисел в унарной системе счисления. Запись правила «q_ia_j→q_i1a_j1R/L/N» следует понимать так:q_i– состояние при котором выполняется это правило,a_j– данные в ячейке, в которой находится головка,q_i1– состояние в которое нужно перейти,a_j1– что нужно записать в ячейку,R/L/N– команда на перемещение.

Машина работает по следующему набору правил:

Набор правил	Набор правил
q0*→q0*R	q4a→q4aR
q01→q01R	q4=→q4=R
q0×→q1×R	q41→q41R
q11→q2aR	q4*→q51R
q21→q21L	q5→q2*L
q2a→q2aL	q6a→q61R
q2=→q2=L	q6×→q7×R
q2×→q3×L	q7a→q7aR
q31 → q4aR	q71→q2aR
q3a→q3aL	q7=→q8=L
q3*→q6*R	q8a→q81L
q4×→q4×R	q8×→q9×N

Умножим с помощью машины Тьюринга 3 на 2 в единичной системе:

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

4. Описание программы-эмулятора машины Тьюринга

Тренажёр «Машина Тьюринга» – это учебная модель универсального исполнителя (абстрактной вычислительной машины), предложенного в 1936 году А. Тьюрингомдля уточнения понятия алгоритма. Согласно тезису Тьюринга, любой алгоритм может быть записан в виде программы для машины Тьюринга. Доказано, что машина Тьюринга по своим возможностям эквивалентнамашине Постаинормальным «алгорифмам» Маркова.

14. Модель машины Тьюринга

Машина Тьюринга состоит из каретки (считывающей и записывающей головки) и бесконечной ленты, разбитой на ячейки. Каждая ячейка ленты может содержать символ из некоторого алфавита A={a₀,a₁,…,a_N}. Любой алфавит содержит символ «пробел», который обозначается как a₀ или Λ. При вводе команд пробел заменяется знаком подчеркивания «_».

Машина Тьюринга – это автомат, который управляется таблицей. Строки в таблице соответствуют символам выбранного алфавита A, а столбцы – состояниям автомата Q={q₀,q₁,…,q_M}. В начале работы машина Тьюринга находится в состоянии q₁. Состояние q₀ – это конечное состояние: попав в него, автомат заканчивает работу.

В каждой клетке таблицы, соответствующей некоторому символу a_i и некоторому состоянию q_j, находится команда, состоящая из трех частей:

1. символ из алфавита A;

2. направление перемещения: > (вправо), < (влево) или ● (на месте);

3. новое состояние автомата

В верхней части программы находится поле редактора, в которое можно ввести условие задачи в свободной форме.

Лента перемещается влево и вправо с помощью кнопок, расположенных слева и справа от нее. Двойным щелчком по ячейке ленты (или щелчком правой кнопкой мыши) можно изменить ее содержимое.

С помощью меню Лента можно запомнить состояние ленты во внутреннем буфере и восстановить ленту из буфера.

В поле Алфавит задаются символы выбранного алфавита. Пробел добавляется к введенным символам автоматически.

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

При вводе команды в ячейку таблицы сначала нужно ввести новый символ, затем направление перехода и номер состояния. Если символ пропущен, по умолчанию он не изменяется. Если пропущен номер состояния, по умолчанию состояние автомата не изменяется.

Справа в поле Комментарий можно вводить в произвольной форме комментарии к решению. Чаще всего там объясняют, что означает каждое состояние машины Тьюринга.

Программа может выполняться непрерывно (F9) или по шагам (F8). Команда, которая сейчас будет выполняться, подсвечивается зеленым фоном. Скорость выполнения регулируется с помощью меню Скорость.

Задачи для машины Тьюринга можно сохранять в файлах. Сохраняется условие задачи, алфавит, программа, комментарии и начальное состояние ленты. При загрузке задачи из файла и сохранении в файле состояние ленты автоматически записывается в буфер.