Опр. Множество всех всюду определенных функций из называется классом рекурсивных функций.

Опр. Множество всех функций, которые можно получить из системы при помощи операций суперпозиции и примитивной рекурсии, называется классом примитивно-рекурсивных функций.

Очевидно, что .

28. Замкнутость класса вычислимых функций относительно операции суперпозиции.

Лемма 6. Из вычислимой функции при добавлении и изъятии несущественных переменных получается вычислимая функция.

Лемма 7. Если , ,…, вычислимы, то функция тоже вычислима.

Теорема 1. Класс замкнут относительно операции суперпозиции.

29. Замкнутость класса вычислимых функций относительно операций примитивной рекурсии и минимизации.

Теорема 2. Класс замкнут относительно операции примитивной рекурсии.

Теорема 3. Класс замкнут относительно операции минимизации.

Теорема 4. Класс замкнут относительно системы операций .

30. Частичная рекурсивность вычислимых функций. Формула Клини.

Теорема 5. Для всякой вычислимой функции существуют такие примитивно-рекурсивные функции и , что .

Теорема 6.

Теорема 7. Система функций полна в относительно системы операций .

Теорема 8. Система функций полна в относительно системы операций .

Дата добавления: 2015-11-14