Are All Functions Computable?
Suprisingly, most aren't
It might seem a strange question to ask whether all functions are computable. We are used to seeing functions written down in mathematical language, making them automatically computable. For example, the quadratic function is obviously computable:
We can put any x into this function and calculate the answer. Or to take another example, the sine function is computable since we can write it as an infinite series:
We can put any x into this function and calculate sin(x) to any precision we like by including as many terms as we need in the infinites series. Surprisingly, however, there are an infinite number of functions that we can’t compute. The reason is that there are more functions than there are algorithms to compute them.
What does it mean to compute a function? Intuitively, it means that we can work out the answer on pencil and paper or we can punch numbers into a caculator to compute the function. More generally, a function is computable if we can write a computer program to compute it. For example, one python code to compute the quadratic function would be
def quadratic_function(x):
return x**2 + 5*x + 2How Many Possible Computer Programs Are There?
Computer programs are strings of characters of finite, but arbitrarily large length. For example, the python program above could be represented as the string of characters:
def\space\quadratic_function(x):\enter\\tab\\return x**2 + 5*x + 2
where \space\ is the space character,\enter\ is a carriage return, and \tab\ is a tab. All computer programs can be written as strings of characters of finite length. How many possible computer programs are there? It would seem that there are an infinite number of compute programs, but we’ll need to be more precise about what we mean by infinity.
Countable Infinity
A set is countably infinite if it can be put in order and counted by the infinite positive integers. This definition immediately leads to surprising consequences. The set of even numbers is countably infinite since the even numbers can be put in order and counted by the positive integers.
Thus, it turns out that a subset of a countably infinite set is also countably infinite. When we are talking about infinite numbers, a subset of an infinite set has the same number of elements as the set itself.
What about the rational numbers? They are countably infinite as well, since we can put them in order and count them by the positive integers:
In this diagram, we order the rational numbers by following the arrows, excluding the rational numbers circled in green, since we already counted them previously. 1/1 would be the first element, counted as one, 1/2 would be second, counted as two, 2/1 would be the third element, counted as three, and so on.
Uncountable Infinity
What about the real numbers? Let’s assume we can order them by putting them into a one-to-one correspondence with the natural numbers as in the diagram below, in which we have circled the diagonal element in each real number.
Now let’s construct a new real number with the property that its first digit is different from the first digit of the first real number, its second digit is different from the second digit of the second real number, continuing in that fashion:
This new real number can’t be on the list. As a consequence, there are more real numbers than there are integers. Even if you think you’ve written down an infinite set of real numbers, there are always more. The set of real numbers isn’t countable—it’s uncountably infinite.
Is The Set of Possible Computer Programs Countably or Uncountably Infinite?
The set of all possible computer programs is countably infinite since we can order them. Every computer program is a sequence of character symbols of finite length. To order them, we can consider all legitimate computer programs that have one character, all legtimate computer programs that are two characters in length, etc. We can order them by placing the one character programs first (counting only those that are legitimate, if any, in the programming language we are using), then the two character programs next, and so on. Within the programs of character length N, we can also order them further by defining rules that order sequences of characters: if the first letter is “a”, it comes before any program that begins with any other letter or symbol, including “A” with the rule that lower case letters are counted before upper case letters. If both programs begin with “a,” then we proceed to the next character and apply the same ordering rules. In this way, we can associate every legitimate program with a positive integer. The set of all possible legitimate programs is countably infinite.
How Many Functions Are There?
The number of functions is uncountably infinite. To see this, let’s define a family of functions as follows: for every real number, the function is
where n is a positive integer and dn is the nth digit in the infinite decimal expansion of the real number. We can define one such function for every real number, implying that this subset of all the functions is uncountably infinite. Since there are more functions than there are algorithms to compute them, there must be an infinite number of functions that are not computable.
Implications
Most real numbers are not computable, since there are an uncoutably infinite number of real numbers and a countably infinite number of computer programs. If a real number is not computable, that means that there is no algorithm to compute its value to arbitrary precision. The computable reals are countable, however, because there are as many of them as there are algorithms.
Chaitin’s Constant
Chaitin’s constant is the probability that a randomly generated computer program will halt. These probabilities are non-computable. They can be approximated, but not to arbitrary precision.
Zeros of Functions
Since most real numbers are non-computable, it should not be surprising to realize that there an infinite number of functions with some real zeros that cannot be computed.
Very cool post Greg !!!!!