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

алгоритм или нет, но нет алгоритма, позволяющего выяснить применимость любого нормального алгоритма к любому слову. Это означает, что рассматриваемый класс задач достаточно обширен и надо как-то разумно делить их на подклассы и для них искать разрешающие алгоритмы. 2. Теоремы об алгоритмической неразрешимости показывают, что математика не сводится к построению алгоритмов. 3. Алгоритмическая разрешимость не всегда означает разрешимость задач массовой проблемы, ибо может не хватить ресурсов, например, машинного времени. Область применения алгоритмов весьма широка и к ней относятся не только вычислительные процессы. Более того, для многих проблем, считающихся трудными, теоретически можно построить алгоритм, но его реализация сопряжена с очень долгим счетом и необходимостью запоминать большое количество промежуточных результатов. Создание быстродействующих вычислительных машин значительно расширило круг решаемых задач. § 13. Примитивно рекурсивные и общерекурсивные функции Рекурсивное определение функции - это, грубо говоря, определение, в котором значения функции для данных аргументов непосредственно определяются значениями этой же функции для "более простых" аргументов или значениями "более простых" функций. Здесь, как и при определении вычислимости по Маркову или Тьюрингу, будем рассматривать только арифметические функции. Теперь приступим к строгому определению примитивно рекурсивных и общерекурсивных функций. 1. Следующие функции называются исходными (простейшими) функциями: 1) нуль функция: Z(x)=0 при \/х (хЩ, 2) функция прибавления единицы: N(x)=x+1 при Vx(x^), ясно, что, используя функции Z и 7V, можно получить любую функцию-константу, например: l=N(Z(x)), 2=N(N(Z(x))), 3=N(N(N(Z(x)))), ... 3) проектирующая функция JP (xi,X2,...,XrJ=Xi при всех Xi,X2 ,...,Xn^ (i=l,2,...,n; п=1,2,...) 2. Следующие правила служат для получения новых функций, исходя из уже имеющихся функций. Подстановка: f(xi,x2,...,xrj=g(hi(xi,x2 ,...,xrj ,...,hjxi,x2 ,...,xrj), тогда говорят, что функция/ получена с помощью подстановки из функций g, hi, /22,..., h^. Рекурсия: 169