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

      Аргументами и значениями вычислимых функций могут быть лишь конс-
труктивные объекты, так как только такими объектами могут манипулировать
алгоритмы.
      Вычислимая функция, областью определения которой являются натура-
льные числа, называется вычислимой последовательностью.
      Различные уточнения понятия алгоритма (машина Тьюринга, нормальный
алгоритм) приводят к соответствующим уточнениям понятия вычислимой фун-
кции. Все они эквивалентны между собой, а в случае числовых функций (функ-
ций с натуральными аргументами и значениями) эквивалентны понятию рекур-
сивной функции. Общепринята гипотеза (тезис Черча), это всякая числовая вы-
числимая функция является рекурсивной.

      1.2 Разрешимые и перечислимые множества

       Областью применимости алгоритма называется совокупность тех объек-
тов, к которым он применим, то есть дает результат.
       Про алгоритм А говорят, что он:
       - «вычисляет функцию f», если его область применимости совпадает с
областью определения f, и А перерабатывает любой х из своей области приме-
нимости в f(х);
       - «разрешает множество М относительно множества Х», если он приме-
ним к любому х из Х и перерабатывает любой х из Х∩М в слово «да», а любой
х из Х\М – в слово «нет»;
       - «перечисляет множество М», если его область применимости есть нату-
ральный ряд, а совокупность результатов есть М.
       Множество называется разрешимым относительно Х, если существует ра-
зрешающий его относительно Х алгоритм. Множество называется перечисли-
мым, если либо оно пусто, либо существует перечисляющий его алгоритм.
       Обнаружены результаты (путем анализа понятия «алгоритм»):
       - область возможных исходных данных и область применимости любого
алгоритма суть перечислимые множества;
       - для любой пары вложенных одно в другое перечислимых множеств мо-
жно подобрать алгоритм, у которого внешнее множество служит областью воз-
можных исходных данных, а внутреннее – областью применимости. Кроме то-
го, имеет место следующие теоремы.
       Теорема 1 Функция f вычислима тогда и только тогда, когда перечислим
ее график.
       Теорема 2 Подмножество М перечислимого множества Х тогда и только
тогда разрешимо относительно Х, когда М и Х\М перечислимы.
       Теорема 3 Если Р, Q перечислимы, то Р∪ Q, Р∩ Q также перечислимы.
       Теорема 4 В каждом бесконечном перечислимом множестве Х существу-
ет перечислимое подмножество с неперечислимым дополнением. (В силу тео-
ремы 2 это перечислимое подмножество будет неразрешимым относительно Х).