Converting any computable function into a sequence of additions

Question

Not sure if this question should be here, or on math.se.

That said, let me proceed:

On the Wikipedia page for the Ackermann function, it is mentioned that by passing the inputs of 0, 1 and 2 to the third parameter one could perform the three fundamental operations of addition, multiplication and exponentiation, respectively, on the other two parameters.
That is, addition, multiplication and exponentiation are the three fundamental operations.

But multiplication is merely repeated addition, and exponentiation repeated multiplication. So addition is the fundamental operation?

My question is this:

Does there exist an algorithm to convert any sequence of (computable) mathematical operations, into another sequence of computable operations involving only addition.

Answer 1

I don't quite see the connection between the preamble and the question.

Regarding the three fundamental operations, this is of course an arbitrary selection. On one hand, you could say that the most fundamental operation is the unary successor function $x \mapsto x+1$. On the other hand, you have hyperoperations, some of them occurring naturally in Ramsey theory and combinatorial pseudorandomness.

Regarding your actual question, the answer is plainly no. No finite sequence of addition operations can compute the function $(x,y) \mapsto xy$, for example. Indeed, the output of any given sequence of additions on inputs $x,y$ is $O(x+y)$, which grows too slowly.

This is a special instance of a more general theorem about nested bounded iteration, which states that a function $f(n)$ can be computed using $m$ nested bounded loops iff it is recursive and eventually bounded by $A(n,m)$ (the binary Ackermann function). This is part of the circle of ideas around primitive recursive functions.