Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
In Chap 34.3 NP-completeness and reducibility of the book, Introduction to Algorithm(3rd Edition), the author states(the original text):
We call the function f the reduction function, and a polynomial-time algorithm F that computes f is a reduction algorithm.
In my mind, function should be a machine dependent implementation(a set of instructions) of the algorithm. Why does he say algorithm computes function?
A function is a mapping from elements in the domain to elements in the range. Here is an example of a function: $f(n) = n!$. If you want a machine to compute $f(n)$ given $n$, you need an algorithm, for example: given $n$, multiply together all the numbers from $1$ to $n$. There can be other algorithms for computing $f$. The function exists without reference to a machine. In fact, some functions (such as the halting function) cannot be computed by any algorithm.
You might be confusing the mathematical meaning of the term function with its meaning in programming languages, which is what you describe.
