Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
What does addition and multiplication look like? –  Raphael Jan 16 '13 at 12:45
    
Well, first of all, you have given what seems to be a recursion scheme, but you haven't proven anything. You also need to prove that the function you give is actually $x^y$, and this you do on double induction. Moreover, have you proved that $x \cdot y$ is p.r.? –  Pål GD Jan 16 '13 at 12:45
    
To give a hint, try defining $f(y,x) = x^y$ (note the reversed order). This allows you to recurse on the first argument (which is the usual way of doing it). –  Pål GD Jan 16 '13 at 12:49
    
You seem to be using $h$ for the new function and also for multiplication. –  Carl Mummert Jan 16 '13 at 13:29
add comment

2 Answers

As I wrote in the comments, you haven't actually proved anything. If you want to prove that $x^y$ is p.r., you need to write it in the scheme form, and then you need to prove that indeed $x^y = f(y,x)$ for your defined $f$ for all $x$ and $y$ (by double induction).

Consider the following definition of $f(y,x) = x^y$:

$f(0,x) = s(z(x))$ (i.e., the successor of the constant zero function).

$f(y+1, x) = u^3_1(u^3_1(x^y, x, y) \cdot x, x, y)$.

I assume now that multiplication, $x \cdot y$ and wrote it infix, and obviously $x^y = f(y,x)$. The function $u^a_b$ is the $a$-ary projection of $b$.

(Ps. if this doesn't work for you, please post your scheme you want to use, otherwise we cannot do else then guess.)

share|improve this answer
    
Thank you for your answer. I don't know if my lecture notes jump to conclusions when showing that a function is primitive recursive, because they basically stick to what you call the recursion scheme, so I thought that was enough. Regardless I'd love to learn more. But, again, I don't know what you mean by scheme. I've been under the (mistaken) impression that it is some kind of fixed pattern to adapt to the case, but now I feel kind of lost. What am I looking for exactly? –  haunted85 Jan 16 '13 at 15:45
    
Yes, it is the pattern you must follow (that's what we call the p.r. scheme). But indeed, if I give you a scheme, say $f(x,y)$ and say that it defines the Ackermann function, you wouldn't believe me without a proof that it actually is the Ackermann function, right? That's what I mean when I say you need to prove that your function actually is exponentiation. (btw. Ackermann is not p.r.) –  Pål GD Jan 16 '13 at 15:49
    
Ok, bear with me on this, I apologize in advance if you find anything I write really really dumb. Let me start over. Look at the recursion scheme I've posted. I say $h(x,y+1)$ is built using a $g$ function such that it has three parameters so $g(x_1, x_2, x_3)$ where $x_2 = h(x,x)$ and $x_3 = x$. As I know that $h(x,y) = x \cdot y$ is p.r., am I allowed to state that $h\left(u^3_2(x_1, x_2, x_3),u^3_3(x_1, x_2, x_3)\right) = h(h(x,x),x)$ is in fact the exp function and it is p.r. because I am making use of the $h(x,x)$ which is p.r. (other than $s(x)$ and $z(x)$)? –  haunted85 Jan 16 '13 at 16:09
add comment

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!

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.