Авторизация
Забыли пароль? Введите ваш е-мейл адрес. Вы получите письмо на почту со ссылкой для восстановления пароля.
После регистрации вы сможете задавать вопросы и писать свои ответы, получая за это бонусы. Все остальные функции на сайте доступны без регистрации.
Вы должны войти или зарегистрироваться, чтобы добавить ответ и получить бонусы.
Для доказательства примитивной рекурсивности функций необходимо построить их определения с использованием базовых примитивно рекурсивных функций и примитивных рекурсивных операций (проекций, композиций, примитивной рекурсии).
Пример 1: Функция сложения (addition)
Определение функции сложения: add(x, y) = x + y
1. Базовый случай: add(x, 0) = x (проекция)
2. Рекурсивный случай: add(x, y+1) = S(add(x, y)) (примитивная рекурсия, где S — функция преобразования, увеличивающая аргумент на 1)
Пример 2: Функция умножения (multiplication)
Определение функции умножения: multiply(x, y) = x * y
1. Базовый случай: multiply(x, 0) = 0 (проекция)
2. Рекурсивный случай: multiply(x, y+1) = add(x, multiply(x, y)) (примитивная рекурсия, где add — функция сложения)
Пример 3: Функция возведения в степень (exponentiation)
Определение функции возведения в степень: power(x, y) = x^y
1. Базовый случай: power(x, 0) = 1 (проекция)
2. Рекурсивный случай: power(x, y+1) = multiply(x, power(x, y)) (примитивная рекурсия, где multiply — функция умножения)
Таким образом, функции сложения, умножения и возведения в степень являются примитивно рекурсивными.