математика - Примитивно-рекурсивные функции

Рассмотрим функцию $%\phi(x,y)$%, заданную схемой рекурсии:

$%\phi(x,0)=1$%

$%\phi(x,y+1)=\phi(x,y)\cdot|g(x)-h(y)|$%

При этом строится примитивно-рекурсивная функция $%\phi(x,y)=|(g(x)-h(0))(g(x)-h(1)\ldots(g(x)-h(y-1))|$%. Далее рекурсией по $%x$% строим функцию $%\psi(x,y)$%, полагая

$%\psi(0,y)=1$%

$%\psi(x+1,y)=\psi(x,y)\cdot\phi(x,y)$%

Если есть требование вести рекурсию по последней переменной, то можно переставить переменные, но этот момент не принципиален.

В итоге получается, что $%\psi(x,y)$% равно модулю произведения разностей вида $%g(i)-h(j)$% при $%0\le i < x$% и $%0\le j < y$%. При этом $%\psi(y+1,y+1)$% равно нулю, если $%g(i)=h(j)$% для некоторых $%0\le i,j\le y$%, и положительна в противном случае. Остаётся подставить эту функцию в $%\overline{\rm sg}$%, которая равна 1 в нуле и равна 0 для остальных значений аргумента.