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

1) алгоритм Тьюринга; 2) алгоритм Евклида; 3) алгоритм Квайна; 4) композиция заданного нормального алгоритма и некоторого фиксиро­ ванного алгоритма Тьюринга; 5) композиция алгоритмов Тьюринга и Евклида. 6. Пусть М - множество функций, частично вычислимых по Маркову, Т - множество функций, частично вычислимых по Тьюрингу. Какое из следующих утверждений истинно: 1) (MczT)&(M^T), 2) (Тс^)&(ТЛ4), 3) Т=М, 4) Т^, 5) ТпМ=0. 7. Пусть М - множество функций вычислимых по Маркову, Т - множество функций вычислимых по Тьюрингу, OR - множество общерекурсивных функций. Какое из следующих ут­ верждений истинно? 1) (M^)&(T=OR), 2) (M=T)&(M^OR), 3) (M^T)&(M=OR), 4) (M^)&(T^OR), 5) T=M=OR. 8. Машина Тьюринга имеет 1) (бесконечную ленту)с&(конечный внешний алфавит)с&(конечный внут­ ренний алфавит); 2) (бесконечную ленту)с&(бесконечный внешний алфавит)с&(конечный внутренний алфавит); 3) (бесконечную ленту)с&(бесконечный внешний алфавит) с&(бесконечный внутренний алфавит); 4) (конечную ленту)с&(бесконечный внешний алфавит)с&(конечный внут­ ренний алфавит); 5) (конечную ленту)с&(конечный внешний алфавит)с&(бесконечный внут­ ренний алфавит). 9. Арифметическая функция f(x,y) = х+у 1) (не вычислима по Тьюрингу)с&(вычислима по Маркову)cfe(является общерекурсивной); 2) (вычислима по Тьюрингу)с&(вычислима по Маркову)с&(является обще­ рекурсивной); 3) (не вычислима по Тьюрингу)с&(не вычислима по Маркову) с&(является общерекурсивной); 4) (не вычислима по Тьюрингу)с&(не вычислима по Маркову) с&(не явля­ ется общерекурсивной); 5) (вычислима по Тьюрингу)с&(вычислима по Маркову)с&(не является общерекурсивной). 254