3. Известно, что на ленте записано слово из 
единиц 11... 1. Постройте машину Тьюринга с внешним алфавитом 
, которая отыскивала бы правую единицу этого слова (т.е. приходила бы в состояние, при котором обозревалась бы ячейка с самой правой единицей данного слова, и в этом положении останавливалась), если в начальный момент головка машины обозревает одну из ячеек с буквой данного слова.
5. Сконструируйте машину Тьюринга с внешним алфавитом , которая каждое слово длиной в алфавите 
перерабатывает в слово длиной 
в том же алфавите .Указание. Используйте алфавит внутренних состояний из двух букв.
6. На ленте машины Тьюринга записаны два набора единиц 1. Они разделены звездочкой *. Составьте функциональную схему машины так, чтобы она, исходя из стандартного начального положения, выбрала меньший из этих наборов, а больший стерла.
Звездочка должна быть сохранена, чтобы было видно, какой из массивов выбран. Рассмотрите примеры работы этой машины применительно к словам:
г) 111*11; д) 11*1111; е) 1111*11.
7. Постройте машину Тьюринга, которая бы к натуральному числу в десятичной системе счисления прибавляла единицу.
8. Пусть для слов в алфавите 
заданы следующие марковские подстановки: ж) 
, з) 
, и) 
, к) 
, л) 
.
По очереди примените каждую из них к слову: 
, - максимальное число раз.
Дата добавления: 2015-09-12; просмотров: 57 | Поможем написать вашу работу | Нарушение авторских прав |