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^ncdot 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) = hleft(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)=xtimes 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
