Hello!! I have a question about the Ackermann's function...
To show that the Ackermann's function is not primitive recursive we have to show that it grows faster than all the primitive recursive functions, right??
To do that do we have to show that
f(x1, ... , xn) <= A(u, max(x1, ... , xn))
or
f(x1, ..., xn) <= A(u, x1+ ... +xn)
where f(x1, ... , xn) is any primitive recursive function ??
I have seen both versions. Are both of them correct??
How can we prove by induction the relation $A(x,y)>y, \forall x,y$??
When we have to prove a relation $P(n), n\geq 0$, we do the following steps:
we show that it stands for $n=0$
we assume that it stands for n=k (Induction hypothesis)
we want to shw that it stands for $n=k+1$ using the In...
