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.)

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.

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.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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