Областная дистанционная викторина «Великолепные кошачьи» (стр. 5 )

Другой вариант алгоритма:

	q1
|	e q1 R
e

Пример 1

1.  Дано число n в десятичной системе счисления. Разработайте машину Тьюринга, которая увеличивала бы заданное число на 2. В начальный момент времени автомат обозревает крайнюю левую цифру. В конечном состоянии он так же должен обозревать крайнюю левую цифру числа. Составить программу-таблицу и нарисовать диаграмму переходов. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии. Отметьте запрещенные клетки таблицы.

	q1	q2	q3	q4	q5
e	eq2L	Х	1q5S	eq5R	Х
0	0q1R	2q4L	1q4L	0q4L
1	1q1R	3q4L	2q4L	1q4L
2	2q1R	4q4L	3q4L	2q4L
3	3q1R	5q4L	4q4L	3q4L
4	4q1R	6q4L	5q4L	4q4L
5	5q1R	7q4L	6q4L	5q4L
6	6q1R	8q4L	7q4L	6q4L
7	7q1R	9q4L	8q4L	7q4L
8	8q1R	0q3L	9q4L	8q4L
9	9q1R	1q3L	0q3L	9q4L

q1 – перемещение автомата к последней цифре числа

q2 – добавление к последней цифре числа значения 2

q3 – увеличение разрядов числа на 1, если последняя цифра числа 8 или 9

q4 – перевод автомата в крайнюю левую позицию

q5 – завершение работы

Протестировать решение на числах 72, 39, 98, 999.

2.  На информационной ленте машины Тьюринга содержится непрерывная последовательность символов «%». Сконструируйте машину Тьюринга, которая заменит каждый третий символ на символ «$» (отсчет символов начинается с правого края строки). В начальный момент времени автомат обозревает произвольный символ заданной строки символов. В конечный момент времени он должен обозревать крайний левый символ. Составить программу-таблицу и нарисовать диаграмму переходов. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии. Отметьте запрещенные клетки таблицы.

	q1	q2	q3	q4	q5
e	eq2L	eq5R	eq5R	eq5R	X
%	%q1R	%q3L	%q4L	$q2L
$	X	X	X	X

Протестировать на значениях $, $$$, $$$$$.

3.  На информационной ленте машины Тьюринга записано число N (N>2) в унарной системе счисления. Читающая головка находится напротив крайнего левого символа в записи числа. Выполните трассировку программы для некоторого числа. Определите, какую задачу она решает. Придумайте, как можно решить эту же задачу, используя меньшее число состояний. Запишите свое решение в виде программы-таблицы. Отметьте запрещенные клетки таблицы.

	q1	q2	q3	q4	q5
|	| q1 R	e q3 L	e q4 L	| q4 L
e	e q2 L			e q5 R

Вычитает из числа 2.

	q1	q2	q3
|	eq2R	eq3R
e	X	X	X

4.  Дано число X в двоичной системе счисления. Постройте две машины Тьюринга: первая должна решать задачу умножения двоичного числа на 8, вторая – задачу вычитания 1 из заданного двоичного числа. Если при вычитании в старшем разряде получается ноль, заменять его пустым символом. Используя композицию построенных машин Тьюринга решить две задачи: вычисления Y1 = 8X – 1 и Y2 = (X – 1)*8. В начальный момент времени автомат обозревает крайний левый непустой символ. Во всех машинах Тьюринга отметьте запрещенные клетки таблицы.

Чтобы умножить двоичное число на 8, достаточно приписать справа от него три нуля.

Y=X*8

	q1	q2	q3	q4	q5
e	0q2R	0q3R	0q4L	eq5R	X
0	0q1R	X	X	0q4L
1	1q1R	X	X	1q4L

Y=X-1

	p1	p2	p3	p4	p5
e	ep2L	X	ep4R	X	X
0	0p1R	1p2L	0p3L	ep5R
1	1p1R	0p3L	1p3L	1p5S

Объединяем обе части для вычисления выражения Y1=8X-1

	q1	q2	q3	q4	q5	p1	p2	p3	p4	p5
e	0q2R	0q3R	0q4L	eq5R	X	ep2L	X	ep4R	X	X
0	0q1R	X	X	0q4L	0p1S	0p1R	1p2L	0p3L	ep5R
1	1q1R	X	X	1q4L	1p1S	1p1R	0p3L	1p3L	1p5S

Объединяем обе части для вычисления выражения Y1=(X-1)*8

	p1	p2	p3	p4	p5	q1	q2	q3	q4	q5
e	ep2L	X	ep4R	X	X	0q2R	0q3R	0q4L	eq5R	X
0	0p1R	1p2L	0p3L	ep5R	0q1S	0q1R	X	X	0q4L	0p1S
1	1p1R	0p3L	1p3L	1p5S	1q1S	1q1R	X	X	1q4L	1p1S

Протестировать на значениях 11, 100