Универсальная Машина Тьюринга

Cинтаксис по Тьюрингу

Примеры записи команд:

7LQ2 - В любом случае записываем в ячейку число - 7, далее двигаем каретку на один шаг влево (команда L) и переходим в состояние - Q2

]HQ1 - стираем ячейку, делаем ее пустой, даже если она и была пустой - ], стоим на месте (команда H) и переходим в состояние (столбец)- Q1

xHQ0 - записываем в ячейку букву - x, стоим на месте (команда H) и остонавливаем выполнение программы - Q0

Машина Тьюринга, примеры решения задач:

задача1.

Увеличить число на единицу, записанное в двоичной системе счисления.

  1. Каретка находится слева от числа (до числа)
  2. Каретка находится над числом

Решение:

Для решения данной задачи нам необходимо определить множество всех значений алфавита, так как речь идет о двоичной системе счисления, то в поле “ алфавит ” запишем числа 0 и 1. Программа автоматически добавит в столбец слева от таблицы "программа" введенные числа и знак пустой ячейки - ]. В задаче не сказано, к какому именно числу необходимо добавить единицу, а значит, берем произвольное двоичное число и записываем его в поле «слово».

Машина тьюринга примеры
Расположение элементов эмулятора Машины Тьюринга

Далее самое интересное – кодирование. Из условия задачи для пункта «а» сказано, что каретка находится слева от слова, это значит что само слово нужно еще и найти. Сам автомат (каретка) кроме текущей ячейки ничего не видет, он может только прочитать ее содержимое и на основании значения, которое он считывает, безусловно выполняет поручения. А видит он пустую ячейку. Даем команду двигать в право до тех пор, пока он не увидит начало слова - команда ]RQ1. С точки зрения автомата:

если ячейка пуста

  1. нахожусь в состоянии Q1
  2. считываю значения текущей ячейки
  3. если она пуста то записываю в нее пустоту (звучит странно но так оно и есть, хотя я всеже добавил здравый смысл в свой эмулятор и он просто пропускает такой шаг)
  4. двигаю каретку вправо на один шаг
  5. перехожу (даже если я и находился там) в состояние Q1

если ячейка содержит значения 0 или 1 выполняем команды 0RQ2 и 1RQ2

C точки зрения автомата:

  1. нахожусь в состоянии Q1
  2. считываю значения текущей ячейки
  3. если это 0 или 1 то продолжаю двигаться вправо и перехожу в состояние Q2

Автомат переходит в состояние Q2 (второй столбец), так как функция состояния Q1 - найти число находящегося на ленте, выполнена. Число на ленте найдено. Каретка теперь находится над числом и теперь необходимо найти его конец, для продолжения выполнения программы. Для этого продолжаем двигать каретку вправо, до тех пор, пока не наткнемся на пустую ячейку (означает конец числа на ленте) - команда ]LQ3, при выполнении которой автомат переходит в сотояние Q3.

Q1 Q2 Q3
0 0RQ2 0RQ2 1HQ0
1 1RQ2 1RQ2 0LQ3
] ]RQ1 ]LQ3 1HQ0

Из таблицы видно, что автомат в состоянии Q3 выполняет арифметические действия над вводимым числом. Алгоритм для двоичного числа очень прост, считываем, и если это ноль, то заменим значение ячейки единицей и останавливаем программу, если единица, то меняем на ноль и переходим на шаг влево, где алгоритм повторяется для текущей ячейки, и так далее.

Задача 2.

Напишите программу для машины Тьюринга, которая проверяет любое введенное десятичное число на четность.

Решение:

Q1 Q2 Q3 Q4
0 0RQ1 0RQ3
1 1RQ1 1RQ4
2 2RQ1 2RQ3
3 3RQ1 3RQ4
4 4RQ1 4RQ3
5 5RQ1 5RQ4
6 6RQ1 6RQ3
7 7RQ1 7RQ4
8 8RQ1 8RQ3
9 9RQ1 9RQ4
Y
N
] ]RQ2 YHQ0 NHQ0

С точки зрения автомата:

  1. нахожусь в состоянии - Q1
  2. если это цифра, то двигаю каретку на шаг вправо и перехожу в состояние - Q1
  3. если это пустая ячейка, то двигаю каретку на шаг влево и перехожу в состояние - Q2
  4. если эта цифра 0,2,4,6,8 - двигаю каретку на шаг вправо и перехожу в состояние - Q3
  5. в состоянии Q3 стою на месте, записываю букву Y и останавливаю программу - Q0
  6. если эта цифра 1,3,5,7,9 - двигаю каретку на шаг вправо и перехожу в состояние - Q4
  7. в состоянии Q4 стою на месте, записываю букву N и останавливаю программу - Q0

От автора:

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