313
правок
Изменения
→Примитивно рекурсивные функции
Благодаря проекторам мы можем делать следующие преобразования:
*В рекурсии не обязательно вести индукцию по последнему аргументу. Следует из того что мы можем с помощью проекторов поставить требуемый аргумент на последнее место.
*В правиле подстановки можно использовать функции с разным числом аргументов. Например, подстановка <tex> \mathrm{F}(x,y) =\mathrm{f}(\mathrm{g}(y),\mathrm{h}(x,x,y)) </tex> эквивалентна <tex> \mathrm{F}(x,y,z) = \mathrm{f}(\mathrm{g}(\mathrm{P_{2,2}U^2_2}(x,y)),\mathrm{h}(\mathrm{P_{2,1}U^2_1}(x,y),\mathrm{P_{2,1}U^2_1}(x,y),\mathrm{P_{2,2}U^2_2}(x,y))) </tex>, но если <tex> \mathrm{F} </tex> не константная функция то все подставляемые функции должны иметь хотя бы один аргумент.
== Арифметические операции на примитивно рекурсивных функциях ==
