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

183 обозначать символом F ∗ . Алгоритм F называется самоприменимым , если он применим к своей собственной записи , т . е . к слову F ∗ , и несамоприменимым в обратном случае . Являются ли самоприменимыми следующие алгоритмы : а ) ( ) Ab,a b b b a F 1 ∈    •→ → = г ) ( ) Ab,a ab ab F 4 ∈    → •→ = Λ Λ б ) { Λ Λ →= 2 F д ) ( ) A1, 1 1 1 1 11 F 5 ∈∗      → •→∗ →∗ = Λ в ) ( ) Ab,a b a a F 3 ∈    •→ → = Λ е ) ( ) A1, 11 1 F 6 ∈∗      ∗→ •→ ∗→∗ = Λ 25. Дана машина Тьюринга q 0 1Lq 1 q 1 S 0 1q 1 На ленте записано слово Р =1 и читающая головка находится над этим словом , а машина во внутреннем состоянии q 0 , иначе – задана начальная конфигурация q 0 1 . Описать работу машины Тьюринга . 26. Задана машина Тьюринга q 0 aS 0 q 0 q 0 S 0 Rq 0 q 0 bS 0 q 1 и начальная конфигурация q 0 P . Применима ли данная машина к этой конфигурации , если 1) P=aabbba ; 3) P=acb ; 2) P=cbb ; 4) P=bac . Если машина применима к слову Р , то чему равняется результат ? 27. Пусть А = { 1,2,3,…,9,0 } . Построить машину Тьюринга Т 0 , которая любое число п ( в десятичной записи ) перерабатывала бы в нуль , т . е . Т 0 ( п )=0 . 28. Пусть А = { 1,2,3,…,9,0 } . Построить машину Тьюринга Т 1 , которая любое число п ( в десятичной записи ) перерабатывала бы в число п +1 , т . е . Т 1 ( п )= п +1 . 29. Построить машины Тьюринга Т 1 и Т 0 , перерабатывающие любые числа п в 0 и п +1 соответственно , при условии , что числа записаны только с использованием алфавита А = { 1 } , т . е . п обозначено словом 1n 1... 111 n + = .