1. Постройте машину Тьюринга, которая в алфавите 
слово abb преобразует в слово bba.
2. Постройте машину Тьюринга, вычисляющую числовую функцию 
.
3. Известно, что на ленте записано слово из 
единиц 11... 1. Постройте машину Тьюринга с внешним алфавитом 
, которая отыскивала бы левую единицу этого слова (т.е. приходила бы в состояние, при котором обозревалась бы ячейка с самой левой единицей данного слова, и в этом положении останавливалась), если в начальный момент головка машины
обозревает одну из ячеек с буквой данного слова.
4. Сконструируйте машину Тьюринга с внешним алфавитом , которая каждое слово в алфавите 
перерабатывает в пустое слово, исходя из стандартного начального положения.
5. Сконструируйте машину Тьюринга с внешним алфавитом , которая каждое слово длиной в алфавите перерабатывает в слово длиной 
в том же алфавите .
Указание. Используйте алфавит внутренних состояний из двух букв.
6. На ленте машины Тьюринга записаны два набора единиц 1. Они разделены звездочкой *. Составьте функциональную схему машины так, чтобы она, исходя из стандартного начального положения, выбрала больший из этих наборов, а меньший стерла.
Звездочка должна быть сохранена, чтобы было видно, какой из
массивов выбран. Рассмотрите примеры работы этой машины
применительно к словам:
а) 1*11; б) 11*1; в) 11*111.
7. Постройте машину Тьюринга, которая бы к натуральному числу в десятичной системе счисления прибавляла единицу.
8. Пусть для слов в алфавите 
заданы следующие марковские подстановки: а) 
, б) 
, в) 
, г) 
, д) 
, е) 
.
По очереди примените каждую из них к слову: 1) 
, 2) 
- максимальное число раз.
Литература:[2,3,4,7,16,17,19,21,23,24,25]
Учебно-методическая литература:[2]
Дата добавления: 2015-09-12; просмотров: 105 | Поможем написать вашу работу | Нарушение авторских прав |