Can all programs be modeled as operations of elementary arithmetic operations on inputs? 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.

Tiffany Page

Tiffany Page

Answered question

2022-11-15

Can all programs be modeled as operations of elementary arithmetic operations on inputs?
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 O(whatever), then the number of arithmetic operations is O(whatever k ) where k is some rational number.)

Answer & Explanation

Aedan Hatfield

Aedan Hatfield

Beginner2022-11-16Added 16 answers

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

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?