I'm doing a research paper on Ackermann's function and I came up across the claim that it is not a primitive function. Now I've gone through the proof as to why that's true. But then this other claim which states that
Primitively recursive functions imply total and computable but total and computable does not imply primitively recursive.
Now, I can see how Ackermann' function, being that it is not a primitive recursive function and it's total and computable would serve as a counter-argument to the contrapositive of that claim, thus proving it. But is there a more formal proof to this ? Maybe using the definitions of primitive recursive and total and computable?
ps: I'm pretty new to Logic as this is my first course but this is what I thought of.
Let Q= universe of Primitive functions
Let P= universe of total and computable
the claim is :$$ \forall x(Qx \rightarrow Px) \wedge \neg\forall x(Px \rightarrow Qx)$$so assume
$$ \forall x(Qx \iff Px)$$ and show a contradiction.
Anyone have any pointers. Or am I just going about this completely wrong?
First of all, demonstrating that Ackermann's function is a total recursive function but not primitive recursive is a perfectly good way of providing a formal proof of this.
But there is a more general reason:
The primitive recursive functions have the property that there is a programming language which precisely characterizes them: Every program in the language computes a primitive recursive function, and every primitive recursive function can be computed by some program in the language.
This lets you diagonalize over the primitive recursive functions to produce a total recursive function that's not primitive recursive, as follows.
First, enumerate these programs (the programs are just strings of characters, so you can enumerate them in lexicographic order). Then pare this list down to just those programs that compute a function of one variable. So we've specified a list of programs $P_0, P_1, P_2, \dots,$ which compute precisely the primitive recursive functions of one variable.
Now define a function $f\colon\mathbb{N}\to\mathbb{N}$ by setting $$f(x)=1+(\text{the result of running the program }P_x\text{ on the input }x).$$
You can see that $f$ is total and computable, but it can't be primitive recursive (because it was designed not to equal $P_0, P_1, P_2,$ etc.).
This same method of proof shows that any computable characterization of (some) total recursive functions cannot include all total recursive functions. (Note that the Turing-machine characterization that you're probably familiar with isn't subject to this limitation, since it includes partial functions too.)