Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

2 Answers

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.