Расширим класс операций, которые, так же как и суперпозиция с примитивной рекурсией, дают в качестве результата примитивно-рекурсивные функции.
Т.13.3.(1)Теорема
Пусть n-местная функция g(x1,.....,xn-1,xn) примитивно-рекурсивная. Тогда n-местная функция f(x1,.....,xn-1, xn), определенная равенством f(x1,.....,xn-1, xn)=∑ g(x1,.....,xn-1, i), где i изменяетсяот 0 до xn, также примитивно-рекурсивная.
Доказательство
Запишем схему примитивной рекурсии по последней переменной:
f(x1,.....,xn-1, 0) = g(x1,.....,xn-1, 0)
f(x1,.....,xn-1, xn +1) = f(x1,.....,xn-1, xn) + g(x1,.....,xn-1, xn +1)
Из этого описания очевидно, что f – примитивно рекурсивная функция, Q.E.D.
Т.13.3.(2)Теорема
Пусть n-местная функция g(x1,.....,xn-1,xn) примитивно-рекурсивна. Тогда n-местная функция f(x1,.....,xn-1, xn) определенная равенством f(x1,.....,xn-1, xn)=∏ g(x1,.....,xn-1, i), где i изменяетсяот 0 до xn, также примитивно-рекурсивна.
Доказательство
Запишем схему примитивной рекурсии по последней переменной:
 |
f(x1,.....,xn-1, 0) = g(x1,.....,xn-1, 0)
f(x1,.....,xn-1, xn +1) = f(x1,.....,xn-1, xn) ∙ g(x1,.....,xn-1, xn +1)
Из этого описания очевидно, что f – примитивно рекурсивная функция, Q.E.D.
Пусть заданы некоторые функции fi(x1,.....,xn), i=1,…,s+1 и указаны какие то условия Pj(x1,.....,xn), j=1,…,s, которые для любого набора чисел x1,.....,xn могут быть истинными или ложными. Допустим, что ни для одного набора чисел x1,.....,xn никакие два из упомянутых условий не могут быть одновременно истинными. Функция f(x1,.....,xn), заданная схемой:
 |
f1(x1,…,xn) если P1(x1,…,xn) истинно
f2(x1,…,xn) если P2(x1,…,xn) истинно
f (x1,.....,xn) = ………
fs(x1,…,xn) если Ps(x1,…,xn) истинно
fs+1(x1,…,xn) для остальных x1,…,xn
называется кусочно-заданной функцией.
Вопрос о том будет ли функция f примитивно-рекурсивной, зависит от природы функций fi и условий Pi . Зато для простейшего случая можно доказать очень полезную теорему.
Т.13.3.(3)Теорема
Пусть заданы n-местные примитивно-рекурсивные функции f1(x1,…,xn), f2(x1,…,xn), …, fs+1(x1,…,xn), a1(x1,…,xn), a2(x1,…,xn), …, as(x1,…,xn), причем ни при каких значениях переменных никакие две из функций ai одновременно в 0 не обращаются. Тогда функция, определенная кусочной схемой
f1(x1,…,xn) если a1(x1,…,xn) =0
f2(x1,…,xn) если a2(x1,…,xn) =0
f (x1,.....,xn)= ………
fs(x1,…,xn) если as(x1,…,xn) =0
fs+1(x1,…,xn) для остальных x1,…,xn
Будет примитивно-рекурсивной.
Доказательство
Функцию f можно представить в виде
f =f1unsga1+…+fsunsgas+fs+1sg(a1∙a2∙..∙as)
Все примененные функции – примитивно рекурсивные, следовательно, f – примитивно рекурсивная функция, Q.E.D.
В данной теореме рассмотрены простейшие случаи, когда все условия pi имеют вид ai=0. На самом деле условия могут быть сформулированы иначе, однако с помощью функции псевдоразности их можно преобразовать к виду, указанному в теореме.
Например,
ai=bi эквивалентно |ai÷bi|=0,
ai≤bi эквивалентно ai÷bi=0,
ai<bi эквивалентно unsg(bi÷ai)=0.
Таким образом, теорема оказывается справедливой и в этих случаях.
§ 13.4. Мажорируемые неявные функции
Как уже говорилось ранее, большой ошибкой было бы думать, что функция, выраженная при помощи оператора минимизации, однозначно является непримитивно-рекурсивной. В ряде случаев использование оператора минимизации есть не более чем удобный способ задания процедуры вычисления, позволяющий обойти определенные формальные трудности. Как мы покажем ниже, иногда пусть и более сложным образом, но все же удается заменить процедуру поиска минимально возможного решения для уравнения, задающего всюду определенную функцию.
Рассмотрим уравнение g(x1,…,xn, y)=0, левая часть которого есть всюду определенная функция. Допустим, для каждого x1,…xn уравнение имеет единственное решение y. Тогда это решение будет однозначной всюду определенной функцией от x1,…xn. Актуален вопрос: будет ли функция y=f(x1,…,xn) – примитивно-рекурсивной, если левая часть уравнения, а именно g(x1,…,xn,y) есть примитивно рекурсивная функция.
В общем случае это не так. Зато в некоторых отдельных случаях ответ будет положительным.