# Can all programs reducible to ones with only arithmetic operations on inputs be simulated with polynomial overhead by arithmetic machine?

I failed to get an answer at https://math.stackexchange.com/questions/364061/can-all-programs-reducible-to-ones-with-only-arithmetic-operations-on-inputs-be, so I am asking here.

In https://math.stackexchange.com/questions/364018/can-all-programs-be-modeled-as-operations-of-elementary-arithmetic-operations-onmathematics and computabiltiy theory, I asked:

we treat all inputs and intermediate results and final outputs as natural number. While algorithms/programs themselves are considered natural numbers, here we treat these programs/functions/algorithms as just computable functions. The question is, when the function operates on an input to produce an output, can we consider the operation of function as using only a number of arithmetic operations (addition, subtraction, multiplication and division) on an input? Or does the use of if/else make the aforementioned not true? If this is true, is the number of arithmetic operations polynomially proportional to the lowest time complexity bound possible for solving a problem? (That is, if the lowest time complexity is $\text{O(whatever)}$, then the number of arithmetic operations is $\text{O(whatever}^k)$ where $k$ is some rational number.)

I learned an answer to this, and now I would like to present variation: If we limit our scope to programs that can be modeled as operations of arithmetic operations on inputs, can these program be simulated by a machine that can only do basic arithmetic processes on inputs (multiplciation, division, subtraction, addition) with polynomial overhead (That is, if the lowest time complexity is $\text{O(whatever)}$, then the number of arithmetic operations is $\text{O(whatever}^k)$ where $k$ is some rational number.) to the lowest possible time complexity for solving a problem?

So suppose that there is a problem that have some computational complexity known for deterministic Turing machine. Then we construct a machine which can only use basic arithmetic operations - addition, subtraction, multiplication and division. Examplary problems that can be computed with this machine would be Fourier transform, or computing function $x^5+14x^4+13x^3+9x+1$ with $x$ given as input. Then we use this machine to solve the problem that we have knowledge of its computational complexity in deterministic Turing machine. What would complexity of solving the problem in this special machine be like? Would the problem be solved with only polynomial overhead over deterministic Turing machine? That's my question. Of course, I assume that the problem can be solved by the special machine.

Also, I know that we can only have unbounded recursions for some problems - there is no need for explaining that.

• cross-posted at math.stackexchange.com/questions/364061/… – Miliard Apr 22 '13 at 12:01
• So your question is "can the complexity be significantly (more than polynomially) improved if we allow complex operations like recursion ?". Is it a way to reformulate it ? – Denis Apr 22 '13 at 18:23
• So what I ask is if we allow recursion and other features of Turing machine that do not exist in the special machine, will there only be polynomial improvement? – Miliard Apr 23 '13 at 1:26