Применение машин Тьюринга к словам (стр. 4 )

5)  f(x, y)-? В начальной конфигурации обозревается крайняя правая единица ленты

4) 5)

q1

q2

q3

q1

q2

q3

q4

q5

q6

0

q21L

q31R

q00

0

q20R

q10L

q40R

q40L

q60R

q00

1

q11R

q21L

q01

1

q11R

q30R

q30R

q51L

q51L

q01

КОНСТРУИРОВАНИЕ МАШИН ТЬЮРИНГА

5.13. Известно, что на ленте записано слово ; n ³ 1. Постройте машину Тьюринга с внешним алфавитом А = {а0, 1}, которая отыскивала бы левую единицу этого слова (т. е. приходила бы в состояние, при котором обозревалась бы ячейка с самой левой единицей данного слова, и в этом положе­нии останавливалась), если в начальный момент головка машины обозревает одну из ячеек с буквой данного слова.

5.14. Сконструируйте машину Тьюринга с внешним ал­фавитом А = {а0, 1}, которая каждое слово в алфавите А1 = {1} перерабатывает в пустое слово, исходя из стандарт­ного начального положения.

Указание. В алфавит внутренних состояний включите четыре буквы Q= {q0, q1, q2, q3}.

5.15. Сконструируйте машину Тьюринга с внешним алфавитом А = {а0, 1}, которая каждое слово длиной п в алфавите A1 = {1} перерабатывает в слово длиной п + 1 в том же алфавите А1.

Указание. Используйте алфавит внутренних состояний из двух букв. См. задачу 5.1.

5.16. На ленте машины Тьюринга записаны два набора единиц 1. Они разделены звездочкой *. Составьте функцио­нальную схему машины так, чтобы она выбрала больший из этих наборов, а меньший стерла, исходя из стандартного на­чального положения (см. задачу 5.2). Звездочка должна быть сохранена, чтобы было видно, какой из массивов выбран.

Указание. Машина может работать, например, следующим обра­зом. Заменить крайнюю правую единицу на a и из состояния q1 перейти в состояние q2, в котором она должна, ничего не меняя, прошагать к край­ней левой единице. Здесь, перейдя в состояние q3, заменить крайнюю левую единицу на букву a. Далее, перейдя в состояние q4, прошагать к крайней правой единице, ничего не меняя. Здесь снова заменить единицу на бук­ву a и вернуться к крайней левой единице и т. д. Дальше программа имеет разветвление. Если, начиная двигаться с правого конца, машина в состоя­нии q1, сделав шаг влево, обозревает ячейку с буквой *, то это означает, что единицы правого массива иссякли. Следовательно, левый массив боль­ше. Тогда машина, перейдя в состояние q5. проходит ячейку с буквой * и во всех последующих ячейках слева проставляет единицы. Затем в со­стоянии q6 она возвращается к ячейке со *, минует ее и следует дальше вправо, стирая содержимое ячеек (там записаны буквы a). Дойдя до пер­вой пустой ячейки, машина останавливается. Если же, начиная двигаться с левого конца, машина в состоящий q3 сделав шаг вправо, обозревает ячей­ку с буквой *, то это означает, что иссякли единицы левого массива. Следовательно, большим оказывается правый массив. Привлекая новые состоя­ния q7 и q8, строим программу аналогично предыдущему ответвлению.

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

Р е ш е н и е. В качестве внешнего алфавита естественно выбрать алфавит, содержащий наименования всех цифр десятичной системы счисления. Конечно же, необходим и пу­стой символ а0. Итак, А ={ а0, 1 2, 3, 4, 5, 6, 7, 8, 9, 0}. Состоя­ний у машины будет два: q0 (это, как обычно, остановка) и q1 (рабочее состояние). Итак, Q = {q0, q1}. Функциональная схема {программа) машины:

А Q	а0	1	2	3	4	5	6	7	8	9	0
q1	q01	q02	q03	q04	q05	q06	q07	q08	q09	q10Л	q01

На­чальное положение машины стандартное. Читателю предла­гается проанализировать работу машины.

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

5.19. Дана конечная совокупность единиц, вписанных в ячейки, взятые подряд без пропусков. Постройте функцио­нальную схему такой машины Тьюринга, которая записывала бы в десятичной системе число этих единиц, т. е. пересчитывала бы набор единиц.

5.20. На ленте записаны два числа в двоичной системе счисления, разделенные звездочкой:

1

0

1

1

*

1

0

1

Определите, какую операцию проделает с ними машина Тью­ринга, начиная из стандартного положения (крайняя правая ячейка, состояние q1), если программа машины задается таблицей:

А Q	q1	q2	q3	q4	q5	q6
a0	q0		q11Л	q5a0П	q6a0Л
1	q20Л	q21Л	q40Л	q41Л	q51П	q60Л
0		q20Л	q30Л	q40Л	q50П	q60Л
*		q3*Л			q5*П	q3*Л

5.21. Вопрос, аналогичный вопросу из предыдущей задачи, для ленты

1

1

0

1

*

1

0

0

1

и для машины Тьюринга с программой:

q11	®	q10Л,		q10	®	q1Л,
q21	®	q20Л,		q20	®	q3Л,
q31	®	q4Л,		q1*	®	q2Л,
q41	®	q10Л,		q1а0	®	q0.

5.22. На ленту подряд вписаны два конечных набора еди­ниц, разделенные звездочкой. Составьте программу машины Тьюринга, которая выписывала бы подряд, без разделения звездочкой, столько единиц, сколько их в обоих наборах (сло­жение единиц).

Указание. См. задачу 5.3.

5.23. На ленту подряд вписаны два конечных набора еди­ниц, разделенные звездочкой. Причем в левом наборе единиц больше, чем в правом. Составьте программу машины Тьюринга, которая в левом наборе оставляла бы ровно столько еди­ниц, на сколько единиц в левом наборе больше, чем в правом, а все остальные единицы стирала бы (вычитание единиц).

Указание. См. задачу 5.4.

5.24. Два конечных набор а. из т и n единиц записаны на ленту подряд. Машина в: начальном положении обозревает крайнюю правую единицу левого набора. Постройте про­грамму машины Тьюринга, которая выдавала бы набор единиц из НОД (m, п) штук, а остальные единицы, стирала бы.

Указание. Используйте алгоритм Евклида нахождения наибольшего общего делителя двух натуральных чисел и запрограммируйте его для машины Тьюринга. См. задачу 5.5.

5.25. Постройте машину Тьюринга, осуществляющую пе­ревод слова в слово . Причем в начальном положении машина должна находиться в состоянии q1 и обозревать первую ячейку, эту же ячейку она должна обо­зревать и в момент остановки. (Эта машина называется «пере­нос нуля» и обозначается А.)

Решение. Приводим программу машины. Рядом с командами изображаем конфигурации, получающиеся в ре­зультате выполнения соответствующих команд:

		q1
Начальное положение		0	0	1	….	1	0
			q2
q10 → q2П		0	0	1	….	1	0
				q3
q20 ® q31		0	1	1	….	1	0
							q3
q31 ® q3П		0	1	1	….	1	0
						q4
q30 ® q4Л		0	1	1	….	1	0
						q5
q41 ® q50		0	1	….	1	0	0
					q6
q50 ® q6Л		0	1	….	1	0	0
		q6
q61 ® q6Л		0	1	….	1	0	0
		q0
q60 ® q00		0	1	….	1	0	0

Проанализируйте работу машины.

5.26. Постройте машину Тьюринга, перерабатывающую слово в это же слово из стандартного начального положения, причем в момент остановки должна обозре­ваться крайняя левая ячейка. (Эта машина называется «ле­вый сдвиг» и обозначается Б.)

5.27. Условие аналогично условию предыдущей задачи, но в начальном положении должна обозреваться крайняя левая ячейка, а конечное положение стандартно. Эта машина называется «правый сдвиг» и обозначается Б+.)

Указание. Программа этой машины получается из программы
Б заменой символа Л символом П.

5.28. Постройте машину Тьюринга (называемую «транс­позиция» и обозначаемую В), которая перерабатывает слово в слово , причем в начальном и конечном положении обозревается ячейка, содержащая 0, меж­ду двумя наборами единиц.

5.29. Постройте машину Тьюринга (называемую «удвое­ние» и обозначаемую Г), которая перерабатывает слово в слово , причем в начальном и конечном положении обозревается крайняя левая ячейка.

5.30. Постройте машину Тьюринга, переводящую слово в слово , причем в начальном положении обозревается ячейка с 0 между наборами из у и z единиц, а в конечном положении обозревается ячейка с 0 между наборами из г и х единиц. (Эта машина называется «циклический сдвиг» и обозначается Ц3.)

Указание. Проверьте, что такой перевод произойдет в резуль­тате последовательного применения (композиции) ранее построенных ма­шин В, Б и В, т. е. Ц3 = ВБВ.

Решение. В самом деле, введем обозначение и вычислим:

ВБВ(01x01y01z0) = ВБ (В (01x01y01z0)) = ВБ (01x01z01y0) = В(Б (01x01z01y0)) =

= В(01x01z01y0)) = ) = 01z01x01y0.

5.31. Постройте машину Тьюринга, перерабатывающую слово 01x01y (здесь использовано обозначение ) в слово 01x01y01x01y, причем в начальном положении обо­зревается самая левая ячейка, а в конечном  ячейка, в ко­торой записан 0, заключенный между массивами 1x01y и 1y01x. (Машина называется «копирование» и обозначается К2.

Указание. Проверьте, что эта машина представляет собой сле­дующую композицию построенных выше машин:

К2 = Б+ГВБ+ВГВБ+ВББВБ+.

5.32. Постройте машину Тьюринга с внешним алфавитом А = {а0, 1}, обладающую следующим свойством:

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

б) машина применима к любому непустому слову, т. е. любое непустое слово перерабатывается машиной в некоторое слово (в результате машина останавливается, т. е. приходит в состояние q0);

в) машина применима только к словам вида , п ³ 1;

г) машина применима только к словам вида, п ³ 1, m ³ 1.

Решение. а) Будем считать, что машина начинает работать из стандартного начального положения, т. е. в на­чальном состоянии q1 «головкой» машины обозревается ячей­ка, в которой записана самая правая единица перерабатывае­мого слова. Тогда искомую машину построить нетрудно: из начального положения она должна неограниченно двигаться по ленте вправо. Вот ее функциональная схема:

А Q	q1	q2
a0	q0a0	q2a0П
1	q21П	q21П

В этой машине предусмотрена остановка, если только в на­чальном состоянии q1 обозревается пустая ячейка, т. е. если машина применяется к пустому слову.

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

ВЫЧИСЛИМЫЕ ПО ТЬЮРИНГУ ФУНКЦИИ

5.33. Постройте машины Тьюринга, которые вычисляют следующие функции:

а) f(x) = x + 1;

б) О(х) = 0.

Указание. См. задачи 5.1 и 5.14 для задач п. а) и б) соответ­ственно.

5.34. Постройте, машины Тьюринга, вычисляющие следующие функции:

а) f (x1, х2, х3) = х2;

б) f (x1, х2, …, хn) = хm (1 £ m £ n).

Указание. Попробуйте построить эти машины в виде компози­ции машин О, Б, Б+, Ц, где О — машина из задачи 5.33, б, а Б, Б+ и Ц - машины из задач 5.26, 5.27 и 5.30 соответственно.

5.35. Докажите, что следующие функции вычислимы по Тьюрингу, для чего постройте машины Тьюринга, вычисляю­щие их:

а) f (x, y) = х + y; ж) f (x, y) = НОД (х, y);

б) з)

в) и)  целая часть числа ;

г) к)

д) л) ;

е) f (x, y) = х  y; м) f (x) = 2х + 1; н) f (x) = 21х.

Указание. а) См. задачу 5.4. д) См. задачу 5.24. е) См. задачу 5.23. и) См. задачу 5.6.

Решение. в) Читателю предлагается проверить, что данная функция вычисляется машиной Тьюринга со следую­щей функциональной схемой (программой): q10®q20П, q20 ® q00Л, q21 ® q31П, q31 ® q30П, q30 ® q40Л, q40 ®q40Л, q41 ® q00Л.

5.36. Докажите, что следующие функции вычислимы по Тьюрингу, построив соответствующие машины Тьюринга:

а)

б)

Указание. См. задачу 8.2.

5.37. Cоставьте программы машин Тьюринга, вычисляющих следующие функции:

а) е)

б) ж)

в) з)

г) и)

д) и)