Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In mathematics and computabiltiy theory, 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.)

share|cite|improve this question
up vote 0 down vote accepted

This is a short and quick answer, an expert probably will give you more details in brief. The answer is No, and you are right, the if/else statements are necessary to make the language Turing complete. But remember that Peano arithmetic, a first order logic (which includes equivalents to if\else) axiomatization of arithmetic, is closely related to computability and Turing machines. Wikipedia gives a great summary of all this.

share|cite|improve this answer

The question is not very clear about the model of computation. But I think one easily shows that even a simple function like the characteristic function of the number $0$ (sending $0\mapsto1$, and $x\mapsto0$ for $x\neq0$) cannot be realised by a finite sequence of arithmetic operations.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.