Show $x^y$ is a primitive recursive function

Problem Detail: 

As this thread title gives away I need to prove $x^y$ to be a primitive recursive function.

So mathematically speaking, I think the following are the recursion equations, well aware that I am assigning to $0^0$ the value $1$, which shouldn't be, since it is an "indeterminate" form.

\begin{cases} x^0=1 \\ x^{n+1} = x^n\cdot x \end{cases}

More formally I would write: \begin{cases} h(0) = 1 \\ h(x,y+1) = g(y,h(x,x),x) \end{cases}

as $g(x_1, x_2, x_3) = h\left(u^3_2(x_1, x_2, x_3),u^3_3(x_1, x_2, x_3)\right)$ and provided $h(x,y) = x \cdot y$ is primitive recursive.

Is my proof acceptable? Am I correct, am I missing something or am I doing anything wrong?

Asked By : haunted85

Answered By : Reza

Supposing that $\times~(mult)$ is primitive recursive function. Then you could write:

$exp(x,y)={ x }^{ y }$

1) $exp(x,0)=x^0=1$

2) $exp(x,y+1)=x^{y+1}=(x^y)\times x=mult(exp(x,y),x)$

for $mult$ you could show that:

$mult(x,y)=x\times y$

1)$mult(x,0)=x \times 0=0$

2)$\operatorname{mult} \left({x, y + 1}\right) = x \times \left({y + 1}\right) = \left({x \times y}\right) + x = \operatorname{add} \left({\operatorname{mult} \left({x, y}\right), x}\right)$

and for addition $add$ the proof is straightforward.

Hope these are useful!

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/8967