لخّصلي

function. In turn, a fundamental task of computer science is to find techniques for computing the functions that lie beneath the problems we want to solve.
Consider, for example, a system in which a function’s inputs and outputs can be predetermined and recorded in a table. Each time the output of the function is required, we merely look for the given input in the table where we find the required output. Thus, the computation of the function is reduced to the process of searching the table. Such systems are convenient but limited in power because many functions cannot be represented completely in tabular form. An example is shown in Figure 12.1, which is an attempt to display the function that converts measurements in yards into equivalent measurements in meters. Because there is no limit to the list of possible input/output pairs, the table is destined to be incomplete.
A more powerful approach to computing functions is to follow directions provided by an algebraic formula rather than trying to display all possible input/ output combinations in a table. We could, for example, use the algebraic formula
V = P(1 + r)n
to describe how to compute the value of an investment of P after earning an
annually compounded interest rate of r for n years.
But the expressive power of algebraic formulas has its limitations as well. There are functions whose input/output relationships are too complex to be described by algebraic manipulations. Examples include the trigonometric functions such as sine and cosine. If pressed to calculate the sine of 38 degrees, you might draw the appropriate triangle, measure its sides, and calculate the desired ratio—a process that cannot be expressed in terms of algebraic manipulations of the value 38. Your pocket calculator also struggles with the task of computing the sine of 38 degrees. In reality, it is forced to apply rather sophisticated mathematical techniques to obtain a very good approximation to the sine of 38 degrees, which it reports to you as the answer.
We see, then, that as we consider functions with increasing complexity, we are forced to apply more powerful techniques for computing them. Our ques- tion is whether we can always find a system for computing functions, regardless of their complexity. The answer is no. A striking result from mathematics is that

          632 Chapter 12 Theory of Computation

M12_BROO3427_13_GE_C12.indd 632 17/10
there are functions that are so complex that there is no well-defined, step-by- step process for determining their outputs based on their input values. In turn, the computation of these functions lies beyond the abilities of any algorithmic system. These functions are said to be noncomputable, whereas the functions whose output values can be determined algorithmically from their input values are said to be computable. Even if we restrict the discussion to decision prob- lems, functions that output only a 1 or 0 (“yes” or “no”), the universe of possible problems falls into two camps: decidable functions for which a correct algorithm can be constructed for every possible input, and undecidable functions for which no algorithm can be constructed that always returns a correct answer.
The distinction between computable and noncomputable functions is impor- tant in computer science. Because machines can only perform tasks described by algorithms, the study of computable functions is the study of the ultimate capabilities of machines. If we can identify capabilities that allow a machine to compute the entire set of computable functions and then build machines with these capabilities, we will be assured that the machines we build are as powerful as we can make them. Likewise, if we discover that the solution to a problem requires the computation of a noncomputable function, we can conclude that the solution to that problem lies beyond the capabilities of machines.