Примитивная рекурсия

[Sverest]

Какая функция получается из $\phi$ и $\psi$ с помошью примитивной рекурсии:

$\phi(x)=x,~ \psi(x,y,z)=z^x$

Будет: $z^{\phi(x)}$?

[arseniiv]

Нет. Будет $h$ такая, что $\left\{ \begin{array}{l} h(x, 0) = \phi(x), \\ h(x, n + 1) = \psi(x, n, h(x, n)). \end{array}\right.$

Т. е. $\left\{ \begin{array}{l} h(x, 0) = x, \\ h(x, n + 1) = h(x, n)^x. \end{array}\right.$

По индукции можно доказать, что $h(x, n) = x^{x^n}$ (чтобы увидеть это выражение, надо выписать $h(x, n)$ для нескольких первых $n$).

А $z^{\phi(x)} = z^x$. И это, как мы видим, не то. (И вообще, буквы, летающие в воздухе неприкреплёнными, имеют тенденцию потом падать на голову, когда их накопится большая куча.)