Задача 9

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

Идея решения (условие останова). На ленте есть два исходных массива штрихов.

Штрихи начинаем стирать с левого конца массива m. И поочередно стираем самый левый штрих в массиве m и самый правый штрих в массиве n. Но прежде чем стереть правый штрих в массиве n, проверяем, единственный он (т.е. последний, который надо стереть) или нет.

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

Состояние q1 — поиск разделителя между массивами штрихов при движении справа налево;

состояние q2 — поиск левого штриха в массиве m;

состояние q3 — удаление левого штриха в массиве m;

состояние q4 — поиск разделителя при движении слева направо;

состояние q5 — поиск правого штриха в массиве n;

состояние q6 — проверка единственности этого штриха в массиве n, т.е. определяем, был ли он последним;

состояние q7 — если он был последним, то останов, иначе переход на новый цикл выполнения алгоритма.