Математическая логика и теория алгоритмов

Являются ли самоприменимыми следующие алгоритмы: д ) * 1 —> А - ^ \ 25. Дана машина Тьюринга е ) Fg = • 1 ®1 l(*,l е А) Л —^ * qo^Lqx qiSolqo. На ленте записано слово Р=1 и читающая головка находится над этим словом, а машина находится во внутреннем состоянии до, иначе - задана начальная конфигурация qo\. Описать работу машины Тьюринга. 26. Задана машина Тьюринга и начальная конфигурация q^P. Применима ли данная машина к этой конфигурации, если Если машина применима к слову Р, то чему равняется результат? 27. Пусть ^={1,2,3,...,9,0}. Построить машину Тьюринга Го, ко­ торая любое число п (в десятичной записи) перерабатывала бы в нуль, т.е. Го(и)=0. 28. Пусть у1={ 1,2,3,...,9,0}. Построить машину Тьюринга Ти ко­ торая любое число п (в десятичной записи) перерабатывала бы в число и+1,т.е. Т\{п)=п+\. qoaSoqo q(^oRqQ qobSoqi 1) P=aabbba; 3) P^'^acb', 2) P==cbb\ 4) P=bac. 271