# Converting any computable function into a sequence of additions

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.

• IMHO the key in the answer is "finite". Of course if you're allowed to infinitely go on with the addition then you might express multiplication etc., but if you talk about computer "algorithm", remember that all algorithms are finite sequences of operations. Thus that's why you can't use an addition "algorithm" to replace multiplication and exponentiation ones. – xji Jan 6 '17 at 16:43

## 1 Answer

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.

• Yeah, I don't really understand. Can you make it simpler. Something a first year undergrad might understand? – Tobi Alafin Dec 26 '16 at 8:54
• I recommend a good monograph on classical recursion theory. Some textbooks on theory of computation also cover the result about nested bounded iteration. Unfortunately I wasn't able to find a freely available online source. You can try by search for "growth rate of primitive recursive functions". – Yuval Filmus Dec 26 '16 at 9:44