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

2. Результат применения нормального алгоритма ab —> d • be —> e a dd —^ b к слову P=abdca равен 1) dad-, 2) da-, 3) dd\ 4) ccd, 5) aa. 3. Результат применения машины Тьюринга Ti. qoаSoqo qoSoR qo qobSoqi q\SoRq\ q\c с qi к слову abcc равен (в начальный момент читающая головка маши­ ны обозревает первую букву слова Р)-. 1) аЬс\ 2) сс; 3) Ьс; 4) аЪ-, 5) Ьсс. 4. Результат применения машины Тьюринга Ti (см. предыду­ щую задачу) к слову F= abc равен (в начальный момент читающая головка машины обозревает первую букву слова Р): 1 ) abc-. 2) ab-, 3) be-. 4) c; 5) 5. Для каждого нормального алгоритма существует вполне эк­ вивалентный ему; 1) алгоритм Тьюринга; 2) алгоритм Евклида; 3) алгоритм Квайна; 4) композиция заданного нормального алгоритма и некоторого фиксированного алгоритма Тьюринга; 5) композиция алгоритмов Тьюринга и Евклида. 6. Пусть М - множество функций частично вычислимых по Маркову, Т - множество функций частично вычислимых по Тьюрингу. Какое из следующих утверждений истинно? 325