Cтраница 1
Класс примитивно рекурсивных функций достаточно интересен с точки зрения многих практических проблем. Применение рекурсивных функций в Лиспе не ограничивается лишь численными аргументами, они используются ( и даже в первую очередь) для символьных структур, что открывает новые большие возможности по сравнению с численными вычислениями. [1]
Класс примитивно рекурсивных функций, по определению, есть минимальный класс функций, содержащий функции ( i) - ( iii), замкнутый относительно композиции ( iv) и замкнутый относительно обобщения операции простой рекурсии Rl - R2, применяемой к любому аргументу функции от многих аргументов. [2]
Таким образом, класс HI примитивно рекурсивных функций замкнут относительно ограниченной двойной рекурсии. [3]
Можно показать, что класс примитивно рекурсивных функций включает в себя все числовые функции, которые обычно ветре-ч-аются на практике. [4]
Такие определения, вообще говоря, выводят из класса примитивно рекурсивных функций, хотя соответствующее отношение предшествования может выглядеть как вполне естественное. [5]
Естественно обратить внимание на важный подкласс класса Я - класс примитивно рекурсивных функций, хотя они не являются основной темой обсуждения этой главы. Эти функции были упомянуты в § 5 гл. [6]
Слова рекурсивное определение функции можно понимать и в более широком смысле, нежели мы это делали ( см. выше определение рекурсии, или примитивной рекурсии) - как любой способ задания функции, который связывает значение функции в данной точке с другими ее значениями. Как мы увидим ниже при обсуждении функции Аккермана, есть такие схемы рекурсивных определений, которые выводят из класса примитивно рекурсивных функций. Но есть и такие, которые можно свести к рассмотренной нами схеме. [7]
Все конкретные вычислимые функции, рассмотренные в § 1, 3, 4 гл. Мы уже отмечали, что функции с и /, использованные в доказательстве теоремы 2.2, примитивно рекурсивны. Таким образом, класс примитивно рекурсивных функций является достаточно обширным. [8]
Мы доказали тем самым, что все рекурсивные функции вычисляются на абаках, а потому вычисляются в стандартной форме и на машинах Тьюринга. Чтобы извлечь отсюда следствия применительно к тезису Черча, мы должны понять, насколько широк класс рекурсивных функций. Чтобы получить представление об этом, покажем, насколько обширен уже класс примитивно рекурсивных функций. [9]
Рассмотрим теперь примитивно рекурсивные функции и меру сложности, которая считает шаги одноленточной машины Тьюринга. Xi принадлежат классу сложности, определенному некоторой примитивно рекурсивной функцией; рекурсивная функция, ограничивающая сложность суперпозиции и примитивной рекурсии, является примитивно рекурсивной, и класс примитивно рекурсивных функций замкнут относительно суперпозиции и примитивной рекурсии. [10]
В этом разделе мы изучаем две взаимосвязанные проблемы, Первая возникает естественным образом, когда мы рассматриваем некоторые хорошо известные подклассы рекурсивных функций, вроде примитивно рекурсивных функций, и пытаемся локализовать их среди классов сложности при заданной мере. Обычно эти подклассы рекурсивных функций определяются через структуру своих алгоритмов, и это вполне убеждает в том, что они должны естественным образом располагаться среди классов сложности. Мы покажем на самом деле, в качестве приложения теоремы об объединении, что для многих мер сложности Ф существует рекурсивная функция /, такая, что Cf является в точности классом примитивно рекурсивных функций. [11]
Всякая примитивно рекурсивная функция получается из базисных с помощью некоторой последовательности операций подстановки и рекурсии. Множество таких программ разрешимо, их можно пронумеровать вычислимым образом. Функция ( п, х) i - 4 i - - ( результат применения функции, заданной программой номер п, к числу х) будет вычислима и по построению будет универсальной для класса примитивно рекурсивных функций. [12]