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

1) {Mc:T)8ciM^T), 2) {ТСМ)&{ТФМ) 3 ) Т^М, 4) Т^М, 5) ТпМ=0. 7. Пусть М~ множество функций вычислимых по Маркову, Т- множество функций вычислимых по Тьюрингу, OR- множество общерекурсивных функций. Какое из следующих утверждений истинно; 1 ) (M^T)&{T=^OR); 2) {М=Т)8с{Мф OR)-, 3) (МФТ)&{М=ОК)-, 4) {М?^Т)81{Тф 0R)\ 5) T=M=OR. 8. Машина Тьюринга имеет: 1) (бесконечную ленту)с&(конечный внешний алфавит)«& (конечный внутренний алфавит); 2) (бесконечную ле,нту)&(бесконечный внешний алфавит)^ (конечный внутренний алфавит); 3) (бесконечную ленту) ££ (бесконечный внешний алфавит)^ (бесконечный внутренний алфавит); 4) (конечную ленту) ££ (бесконечный внешний алфавит) ££ (конечный внутренний алфавит); 5) (конечную ленту)<ё:(конечный внешний алфавит)^ (бесконечный внутренний алфавит). 9. Арифметическая функцияДл:,>') = х+у: 1)(не вычислима по Тьюрингу)(6:(вычислима по Маркову)^ (является общерекурсивной); 2) (вычислима по Тьюрингу)(6:(вычислима по Маркову)(6: (является общерекурсивной); 3) (не вычислима по Тьюрингу)(6:(не вычислима по Маркову) с&(является общерекурсивной); 4) (не вычислима по Тьюрингу)(6:(не вычислима по Маркову) с&(не является общерекурсивной); 5) (вычислима по Тьюрингу)(6:(вычислима по Маркову)^ (не является общерекурсивной). 10. Укажите, какая из перечисленных проблем является алго­ ритмически разрешимой: 326