Математическая логика и теория алгоритмов. Стенюшкина В.А. - 109 стр.

                                   Упражнения

      1 Доказать, что множество всех рациональных чисел, меньших e (основа
ние натуральных алгоритмов), разрешимо.
      2 Доказать, что непустое множество натуральных чисел разрешимо тогда
и только тогда, когда оно есть множество значений всюду определённой не-
убывающей вычислимой функции с натуральными аргументами и значениями.
      3 Множество тех n, для которых в числе π есть не менее n девяток по-
дряд, разрешимо. Доказать.
      4 Доказать перечислимость пересечения и объединения перечислимых
множеств.
      5 Доказать перечислимость декартова произведения A×B⊂N×N, если
A⊂N и B⊂N перечислимы.
      6 Доказать перечислимость множества диофантовых уравнений, то есть
уравнений вида P(x1,…,xn)=0, где P – многочлен с целыми коэффициентами.
      7 Выяснить перечислимость множества показателей n, для которых суще-
ствует решение уравнения xn+yn=zn в целых числах.
      8 Доказать, что действительное число α вычислимо тогда и только тогда,
когда множество рациональных чисел, меньших α, разрешимо.
      9 Пусть U – перечислимое множество пар натуральных чисел, универса-
льное для класса всех перечислимых множеств натуральных чисел. Доказать,
что его «диагональное сечение» K={x|(x,x)∈U} является перечислимым нераз-
решимым множеством.
      10 Некоторое множество S натуральных чисел разрешимо. Разложим все
числа из S на простые множители и составим множество D всех простых чи-
сел, встречающихся в этих разложениях. Можно ли утверждать, что множество
D разрешимо?
      11 Построить главную универсальную функцию.
      12 Пусть U – главная универсальная функция. Докажите, что для любой
вычислимой функции V(m,n,x) существует такая всюду определённая вычис-
лимая функция S(m,n), что V(m,n,x)=U(s(m,n),x) при всех m,n и x.
      13 Пусть h – всюду определённая вычислимая функция, у которой мы
хотим найти неподвижную точку. Вычисляющий её алгоритм , допустим, имеет
вид:
      function Compute_h(x:String):String;
      begin
      …
      end;
      Используя процедуру GetProgramText(var s:String), помещающую текст
исходной программы в строку s, записать программу, являющуюся неподвиж-
ной точкой функции h. Указание: Использовать также процедуру ExecutePro-
gram(s:String), которая передаёт управление программе, текст которой находит-
ся в строке s.