Question

Дискретная математика. На ленте машины Тьюринга в четырех подряд идущих клетках записаны четыре различные буквы: A,B,C,D в произвольном порядке. Построить машину Тьюринга, меняющую местами первую и последнюю буквы. Начальное положение – стандартное.

Answer 1

Машина Тьюринга работает пошагово. На каждом шаге на основе текущего состояния и текущего просматриваемого символа определяется:

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

2) как сместить каретку для просмотра очередного символа: влево, вправо или оставаться на месте;

3) в какое состояние нужно перейти (возможно в то же самое, в котором находимся сейчас, тогда фактически состояние не изменится).

Составим алгоритм для решения задачи.

1) Поскольку по условию начальное положение - стандартное, то в начальном состоянии $q_1$ мы просматриваем крайний правый символ (справа от него находятся пустые символы, пустой символ будем обозначать λ).

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

$\begin{array}{|c|c|c|c|c|c|}COCT.&A&B&C&D&\lambda\\q_1&A,\ L,\ q_2&B,\ L,\ q_3&C,\ L,\ q_4&D,\ L,\ q_5&!\end{array}$

Инструкция машине состоит из перечисленных через запятую:

- нового символа в просматриваемой ячейке;

- команды смещения каретки (L - влево, R - вправо, N - оставаться на месте);

- нового состояния.

Так если в состоянии $q_1$ в просматриваемой ячейке находится буква А, то будет выполнена инструкция $(A,\ L,\ q_2)$, а именно в просматриваемую ячейку будет записана буква А (фактически ничего не изменится, ведь там уже находится буква А), каретка будет смещена влево, а машина перейдет в состояние $q_2$.

Для пустого символа λ вместо инструкции прописана команда остановки (!), поскольку по условию в начальном положении просматриваемый символ непустой, а выйдя из состояния $q_1$ возвращаться в него мы не планируем.

2) Для любого из полученных состояний мы должны продолжать двигаться налево, не изменяя символы и состояния, до тех пор, пока просматриваемый символ не окажется пустым. Если просматриваемый символ - пустой, то первый символ находится справа от нас, и нам необходимо сместиться вправо и поменять состояние, причем каждому из четырех ранее созданных состояний будет соответствовать свое новое состояние.

$\begin{array}{|c|c|c|c|c|c|}COCT.&A&B&C&D&\lambda\\q_2&A,\ L,\ q_2&B,\ L,\ q_2&C,\ L,\ q_2&D,\ L,\ q_2&\lambda,\ R,\ q_6\\q_3&A,\ L,\ q_3&B,\ L,\ q_3&C,\ L,\ q_3&D,\ L,\ q_3&\lambda,\ R,\ q_7\\q_4&A,\ L,\ q_4&B,\ L,\ q_4&C,\ L,\ q_4&D,\ L,\ q_4&\lambda,\ R,\ q_8\\q_5&A,\ L,\ q_5&B,\ L,\ q_5&C,\ L,\ q_5&D,\ L,\ q_5&\lambda,\ R,\ q_9\end{array}$

3) Находясь над первой ячейкой мы записываем значение последнего символа, ориентируясь на состояние машины. В зависимости от значения текущего просматриваемого символа, мы осуществляем переход в одно из четырех новых состояний. Смещение каретки должно выполняться вправо.

$\begin{array}{|c|c|c|c|c|c|}COCT.&A&B&C&D&\lambda\\q_6&!&A,\ R,\ q_{11}&A,\ R,\ q_{12}&A,\ R,\ q_{13}&!\\q_7&B,\ R,\ q_{10}&!&B,\ R,\ q_{12}&B,\ R,\ q_{13}&!\\q_8&C,\ R,\ q_{10}&C,\ R,\ q_{11}&!&C,\ R,\ q_{13}&!\\q_9&D,\ R,\ q_{10}&D,\ R,\ q_{11}&D,\ R,\ q_{12}&!&!\end{array}$

Команды остановки прописаны для пустого просматриваемого символа, которого не может быть в ситуации, когда мы просматриваем первый символ, а также для ситуаций, когда первый символ заведомо не может принимать определенное значение. Например, состояние $q_6$ несет в себе информацию о том, что последним символом была буква А, а значит первый символ не может быть буквой А.

4) По аналогии с пунктом 2) мы двигаемся вправо до тех пор, пока просматриваемый символ непустой. Когда просматриваемый символ оказывается пустым, мы меняем состояние и смещаемся влево, таким образом, оказываясь над последним символом.

$\begin{array}{|c|c|c|c|c|c|} COCT. & A & B & C & D & \lambda \\ q_{10} & A,\ R,\ q_{10} & B,\ R,\ q_{10} & C,\ R,\ q_{10} & D,\ R,\ q_{10} & \lambda,\ L,\ q_{14} \\q_{11} & A,\ R,\ q_{11} & B,\ R,\ q_{11} & C,\ R,\ q_{11} & D,\ R,\ q_{11} & \lambda,\ L,\ q_{15} \\q_{12} & A,\ R,\ q_{12} & B,\ R,\ q_{12} & C,\ R,\ q_{12} & D,\ R,\ q_{12} & \lambda,\ L,\ q_{16} \\q_{13} & A,\ R,\ q_{13} & B,\ R,\ q_{13} & C,\ R,\ q_{13} & D,\ R,\ q_{13} & \lambda,\ L,\ q_{17} \end{array}$

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

$\begin{array}{|c|c|c|c|c|c|} COCT. & A & B & C & D & \lambda \\ q_{14} & ! & A,\ N,\ q_0 & A,\ N,\ q_0 & A,\ N,\ q_0 & ! \\q_{15} & B,\ N,\ q_0 & ! & B,\ N,\ q_0 & B,\ N,\ q_0 & ! \\q_{16} & C,\ N,\ q_0 & C,\ N,\ q_0 & ! & C,\ N,\ q_0 & ! \\q_{17} & D,\ N,\ q_0 & D,\ N,\ q_0 & D,\ N,\ q_0 & ! & ! \\q_0 & ! & ! & ! & ! & !\end{array}$

Answer 2

Для создания машины Тьюринга, которая меняет местами первую и последнюю буквы на ленте, можно использовать следующее описание машины Тьюринга в виде таблицы переходов:

Состояния:

• q0: начальное состояние.
• q1: состояние, в котором происходит перемещение влево до первой буквы.
• q2: состояние, в котором происходит перемещение вправо до последней буквы.
• q3: состояние, в котором происходит обмен местами первой и последней букв.

Алфавит: {A, B, C, D, X}

Где X - символ-пустышка (пустое место на ленте).

Таблица переходов:

Состояние	Прочитанный символ	Записанный символ	Движение	Следующее состояние
q0	A	X	R	q1
q0	B	X	R	q1
q0	C	X	R	q1
q0	D	X	R	q1
q1	X	X	L	q2
q1	_	_	S	q3
q2	_	_	S	q0
q2	A	X	L	q2
q2	B	X	L	q2
q2	C	X	L	q2
q2	D	X	L	q2
q3	X	A	S	q0
q3	A	X	S	q0
q3	_	_	S	Halt

Где:

• "R" означает движение вправо.
• "L" означает движение влево.
• "S" означает остановку (машина завершает работу).

Процесс работы машины Тьюринга:

1. Начните в состоянии q0 с лентой, на которой четыре различные буквы и символ-пустышка X между ними. Например, "AXBCD".
2. Машина начнет двигаться вправо (в состоянии q0) до тех пор, пока не найдет символ X.
3. После нахождения символа X, машина перейдет в состояние q2 и начнет двигаться влево до тех пор, пока не найдет следующий символ X.
4. Когда машина достигнет состояния q3, она заменит символ X перед первой буквой на символ A и символ X после последней буквы на символ D.
5. Машина завершит свою работу в состоянии Halt (остановка).

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