Программирование машины Тьюринга, страница 14

+-----¦------+------+------+------¦ 

¦  ^  ¦ ^Пq0 ¦ ^Пq0 ¦ ^Нq3 ¦ ^Лq3 ¦ 

+-----¦------+------+------+------¦ 

¦  *  ¦ ^Сq0 ¦ *Лq1 ¦ *Пq2 ¦ *Нq0 ¦ 

+---------------------------------+ 

_1.5 

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

Задание III_.. Реализация алгоритмов для машины Тьюринга 

1. Алгоритмы работы с символами 

_1.2 

1. Составить функциональную схему машины, реализующей алгоритм  переводящий слово из X палочек в слово из X+1 палочки. 

2. Составить функциональную схему машины, реализующей алгоритм  замены символа '0' на символ '1'. 

3. Составить функциональную схему машины, реализующей алгоритм  копирования символа А заданное число раз. 

4. Составить функциональную схему для  машины  Тьюринга,  осу-  ществляющую алгоритм замены символа 'А' на символ 'В' и наоборот. 

5. Машина начинает с "пустого" начального состояния (т.е.  та-  кого,  при котором все секции заполнены символом внешнего алфави- 

- 27 -  та,  обозначающего пустой знак - '^'). Составить такую программу,  после выполнения которой лента примет вид: 

_1.0 

----------------------------------------------------- 

¦ ^ ¦ @ ¦ ^ ¦ @ ¦ ^ ¦ @ ¦ ^ ¦ @ ¦ @ ¦ ^ ¦ @ ¦ @ ¦ ^ ¦ 

----------------------------------------------------- 

_1.5 

6. На  ленте  машины записаны два набора палочек,  разделенных  между собой звездочкой. Составить функциональную схему для машины 

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

7. На ленте машины напечатан  массив  символов,  состоящий  из 

n-элементов.  Составить  программу  для машины Тьюринга,  которая  строит массив,  равный данному и отстоящий от него вправо на  две  неотмеченные секции. 

8. Дан массив, длина которого выражается нечетным числом. Най-  ти середину массива,  т.е.  стереть метку в секции, которая делит  массив на две равные части. 

9. Одна отмеченная секция расположена на ленте левее основного  массива отмеченных секций. Каретка машины расположена под одиноч-  ной отмеченной секцией.  Составить программу, работая по которой,  машина присоединит эту метку к основному массиву и остановится. 

10. Составить функциональную схему машины,  реализующей  алго-  ритм копирования набора символов. 

11. На ленте машины напечатан массив  символов,  состоящий  из 

n-элементов.  Составить  программу  для машины Тьюринга,  которая  строит массив,  состоящий из 2n-элементов  и  отстоящий  от  него  вправо на две неотмеченные секции. 

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

13. Пусть на ленте машины Тьюринга помещена последовательность  чередующихся между собой символов 'М' и 'А'. Необходимо составить  программу, работая по которой, машина "сотрет" символы 'А', а 'М'  расположит рядом. 

14. Составьте функциональную схему для машины Тьюринга,  рабо-  тая по которой машина стирала бы с ленты любое начальное слово  и  записывала бы вместо него слово AABBA в алфавите {A,B}. 

15. Составьте функциональную схему для машины Тьюринга,  рабо-  

тая  по  которой машина любое заданное слово А_41А_42...А_4n в алфавите 

{0,1} преобразовала бы в "перевернутое" слово А_4n...А_41А_42. 

16. Машина начинает с "пустого" начального состояния (т.е. та-  кого,  при котором все секции заполнены символом внешнего алфави-  та,  обозначающего пустой знак - '^'). Составить такую программу,  после выполнения которой лента примет вид: 

_1.0