Конструирование машин Тьюринга

 

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

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

Указание. В алфавит внутренних состояний включите четыре буквы Q= {q₀, q₁, q₂, q₃}.

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

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

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

       Указание. Машина может работать, например, следующим обра­зом. Заменить крайнюю правую единицу на a и из состояния q₁ перейти в состояние q₂, в котором она должна, ничего не меняя, прошагать к край­ней левой единице. Здесь, перейдя в состояние q₃, заменить крайнюю левую единицу на букву a. Далее, перейдя в состояние q₄,  прошагать к крайней правой единице, ничего не меняя. Здесь снова заменить единицу на бук­ву a и вернуться к крайней левой единице и т. д. Дальше программа имеет разветвление. Если, начиная двигаться с правого конца, машина в состоя­нии q₁, сделав шаг влево, обозревает ячейку с буквой *, то это означает, что единицы правого массива иссякли. Следовательно, левый массив боль­ше. Тогда машина, перейдя в состояние q₅. проходит ячейку с буквой * и во всех последующих ячейках слева проставляет единицы. Затем в со­стоянии q₆   она возвращается к ячейке со *, минует ее и следует дальше вправо, стирая содержимое ячеек (там записаны буквы a). Дойдя до пер­вой пустой ячейки, машина останавливается. Если же, начиная двигаться с левого конца, машина в состоящий q₃  сделав шаг вправо, обозревает ячей­ку с буквой *, то это означает, что иссякли единицы левого массива. Следовательно, большим оказывается правый массив. Привлекая новые состоя­ния q₇ и q₈, строим программу аналогично предыдущему ответвлению.

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

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

А          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

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

А      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. Постройте машину Тьюринга, осуществляющую пе­ревод слова  в слово . Причем в начальном положении машина должна находиться в состоянии q₁ и обозревать первую ячейку, эту же ячейку она должна обо­зревать и в момент остановки. (Эта машина называется «пере­нос нуля» и обозначается А.)

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

		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 между наборами из г и х единиц. (Эта машина называется «циклический сдвиг» и обозначается Ц₃.)

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

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

ВБ^В(01 ^x 01 ^y 01 ^z 0) = ВБ^ (В (01 ^x 01 ^y 01 ^z 0)) = ВБ^ (01 ^x 01 ^z 01 ^y 0) = В(Б^ (01 ^x 01 ^z 01 ^y 0)) =

= В(01 ^x 01 ^z 01 ^y 0)) =) = 01 ^z 01 ^x 01 ^y 0.

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

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

К₂ = Б⁺ГВБ⁺ВГВБ⁺ВБ^Б^ВБ⁺.

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

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

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

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

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

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

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

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

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