313
правок
Изменения
→Примитивно рекурсивные функции
<tex> \textbf 0^{n}(x_1,\ldots,x_{n-1},y+1) = \mathrm{h}(x_1,\ldots,x_{n-1},\textbf 0^{n}(y)) </tex>, где <tex> \mathrm{h}(x_1,\ldots, x_n,y) = y </tex>
Константа <tex> \textbf M </tex> равна <tex> \mathrm{IN}(\textbf{M-1}) </tex>
<tex> \textbf M^n </tex> {{---}} <tex>n</tex>-местная константа, получается аналогичным к <tex> \textbf 0^n </tex> образом.
<tex> \mathrm{sum}(x,0) = x </tex>
<tex> \mathrm{sum}(x,y+1) = \mathrm{h}(x,y,\mathrm{sum}(x,y)) </tex> , где <tex> \mathrm{h}(x,y,z)=\mathrm{IN}(z) </tex>
===== Умножения =====
Сначала выразим <tex> \mathrm{eq_{0}}(x) = \mathrm{eq}(x,0) </tex>
<tex> \mathrm{eq_0}(0) =\mathrm{IN}(0) </tex>
<tex> \mathrm{eq_0}(y+1) = \mathrm{h}(y,\mathrm{eq}(y)) </tex> , где <tex> \mathrm{h}(y,\mathrm{eq}(y)) = \textbf 0^2(x,y) </tex>
<tex> \mathrm{eq}(x,y) = \mathrm{mul}(\mathrm{le}(x,y),\mathrm{le}(y,x)) </tex>
<tex> \mathrm{lower}(x,y) = \mathrm{mul}(\mathrm{le}(x,y),\mathrm{le}(\mathrm{IN}(x),y)) </tex>
===== IF =====
<tex> \mathrm{divmax}(x+1,y) = \mathrm{h}(x,y,\mathrm{divmax}(x,y)) </tex>,
где <tex> \mathrm{h}(x,y,z) = \mathrm{if}(\mathrm{eq}(\mathrm{sub}(\mathrm{IN}(x),z),y),\mathrm{IN}(x),z) </tex>,
или не формально если <tex> x+1 - y = z </tex> то <tex> \mathrm{h}(x,y,z) = x+1 </tex>, иначе <tex> \mathrm{h}(x,y,z) = z </tex>
<tex> \mathrm{divide}(0,y) =\textbf 0^{1} </tex>
<tex> \mathrm{divide}(x,y) = \mathrm{h}(x,y,\mathrm{divide}(x,y)) </tex>, где <tex> \mathrm{h}(x,y,z) = \mathrm{sum}(z,\mathrm{eq}(\mathrm{IN}(x),\mathrm{divmax}(\mathrm{IN}(x),y))) </tex>
или не формально если <tex> x+1~\vdots~y </tex>, то <tex> \mathrm{h}(x,y,z) = z+1 </tex>, иначе <tex> \mathrm{h}(x,y,z) = z </tex>
