Примитивно-рекурсивные операторы. Частично-рекурсивные функции
Предикаты Пусть А – множество объектов хi (i=1,..,N), тогда утверждение P(x), истинное для некоторых хi и ложное для остальных, называется одноместным предикатом на множестве А. Предикат может быть n-местным. Тогда он определен на декартовом произведении множеств А1,…,АM: А1хА2х…xАM: {(x1,x2,…,xm)|x1∈A1,…,xm∈AM}. Для предиката вводится его характеристическая функция: χP(x1,…,xn)= 1, если P(x1,…,xn) истинен, 0, в противном случае. Предикат называют примитивно-рекурсивным, если его характеристическая функция примитивно-рекурсивна. Примитивно-рекурсивные операторы Оператор называется примитивно-рекурсивным (ПР - оператором), если он сохраняет примитивную рекурсивность функции. Условный переход или разветвление Обозначим его B, который по функциям q1(x1,…,xn), q2(x1,…,xn) и предикату P(x1,…,xn) строит функцию f(x1,…,xn)=B(q1, q2, P): f(x1,…,xn)= q1(x1,…,xn), если P(x1,…,xn) истинно. q2(x1,…,xn), если P(x1,…,xn) ложно. f(x1,…,xn)=q1(x1,…,xn) χp(x1,…,xn)+q2(x1,…,xn) (1- χp(x1,…,xn)).
