Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

обозначать символом F*. Алгоритм F называется самоприменимым, если он применим к своей собственной записи, т.е. к слову F*, и несамоприменимым в обратном случае. Являются ли самоприменимыми следующие алгоритмы: {аЬ—>*Л, . \ {а,Ь^А) [л^аь^ ' * 7 7 ^ 7 < *7 ^ •7(*7 G А) л^1 < 1^»11(%1е А) qisolqi На ленте записано слово Р=1 и читающая головка находится над этим словом, а машина во внутреннем состоянии qo, иначе - задана начальная конфигурация qgl. Описать работу машины Тьюринга. 26. Задана машина Тьюринга qoasoqo qosorqo qobsoqi и начальная конфигурация qoP. Применима ли данная машина к этой конфигурации, если 1) P=aabbba; 3)P=acb; 2)P=cbb; 4)P=bac. Если машина применима к слову Р, то чему равняется результат? 27. Пусть А = {1,2,3,... ,9,0}. Построить машину Тьюринга То, которая любое число п (в десятичной записи) перерабатывала бы в нуль, т.е. То (п)=0. 28. Пусть А={1,2,3,... ,9,0}. Построить машину Тьюринга Ti, которая любое число п (в десятичной записи) перерабатывала бы в число п+1, т.е. Ti(n)=n+1. 29. Построить машины Тьюринга Tj иТд, перерабатывающие любые числа п в О и п+1 соответственно, при условии, что числа записаны только с использованием алфавита^=/7}, т.е. п обозначено словом п = 777...7. п+1 [а^ь , , \b ^•Ь О) р2 ={ Л ^ л д) Fj = ,а^а , , в)^з=^ {а,Ь^А) Q) Р^ о ^ •Л 25. Дана машина Тьюринга 183