# Mathematical functions that can't be computed

I was reading over this in my notes, but it doesnt make any sense to me:

However, suppose we ﬁx an alphabet for writing our programs (e.g. 8- bit ASCII). Since each individual program is ﬁnite in length, we can put all possible programs into a (very long) ordered list. For any ﬁxed character length k, there are only a ﬁnite set of possible programs. So, we can write down all programs by ﬁrst ﬁrst writing down all the 1-character programs, then all the 2-character programs, and so forth. In other words, there’s a bijection between the integers and the total set of programs. But this means that the number of functions is uncountable, whereas the number of programs is only countably inﬁnite. So there must be mathematical functions that we can’t compute with any (ﬁnite-length) program.

What exactly is this saying? Why does it hold? It seems like it shouldn't. In some cases a program of only 30-40 characters can compute billions of numbers! Maybe with current hardware it may not be possible to computer some numbers, but theoretically, this shouldn't be a problem, right?

-
It is referring to proofs that "the number of subsets of positive integers is uncountable". These can be viewed as a special case of functions of positive integers, that output 0 or 1 on any input, or (equivalently), programs that emit an infinite string of bits. –  T.. Dec 14 '10 at 1:12
The cited passage contains one of the easiest proofs for the fact that there must be non-computable functions. –  Raphael Dec 14 '10 at 7:42

Here is one analogy which may prove helpful: there are rational numbers, which can be represented as the ratio of two integers: 1/2, 3, 5/6 etc. This can be seen as all the numbers which can be printed out by "programs" which only have access to the "division" operator. Clearly some numbers cannot be printed out by a program with only this operation - $\pi$, for example cannot.

Now suppose we add in the full power of arithmetic: you can specify a number like "the root of $x^2-2x+3$". These are the algebraic numbers. We can print out more numbers this way, but not all of them. $\pi$ again cannot be printed out by this type of program, as it is transcendental.

As a last hurrah, we allow any operation which can print out an arbitrary number of digits in a finite amount of time. We can now find values like $\pi$ and $e$, since there are formulae for these. But can we print all values?

The answer is no. As you have indicated, there are "too many" numbers and too few programs. It is not merely that we have not discovered (or created) some operation - even if we double the number of symbols in our language that only increases the amount of numbers we can write by a finite amount, and there is an infinite amount of space to make up.

Rather than talking about programs, another way to phrase it is: "for every real number, is there some finitary description of it?" E.g. $e=\lim_{n\to\infty}\left(1+\frac{1}{n}\right)^n$ - even though $e$ has an infinite number of digits, we can describe it using only a finite number of symbols. The proof you are discussing shows that there must be some numbers which admit no finitary description.

-
Your explanation has flaws: 1) Either programs can print the number π like this: "π" or "Pi". Or they cannot even print some rational numbers like 1/3 because of their infinite number of digits after the dot. 2) There do not exist numbers which definitely need an infinite description, because otherwise only undefinable infinite long formulas would be possible to evaluate to those numbers. 3) The Question is about functions and programs, not numbers and formulas that define numbers. –  comonad Dec 14 '10 at 6:04
I disagree subtly with comonad. Numbers like $\frac{1}{3}$ and $\pi$ can be computed in the sense that there is a computable function $f : \mathbb{N} \rightarrow \mathbb{N}$ that maps $n$ to the $n$th digit in a decimal representation without leading zeroes. Of course, you can never print out the whole number, but hey. But not every real number can be computed in this sense because of the argument stated in the question. –  Raphael Dec 14 '10 at 7:46
@comonad: as Raphael suggested, the notion we are looking at is "can we print out an arbitrary number of decimal places in a finite amount of time?" Clearly, we need not print out the entire number in a finite amount of time. Secondly, consider a description like "the smallest number not expressible in first order logic." This number cannot be found using an FOL language, even though it has a finitary description in HOL. Lastly, it was indeed an analogy, but I'm not convinced it's a bad one. –  Xodarap Dec 14 '10 at 15:00
"the smallest number not expressible in first order logic." is indeed a better example, as is the "busy beaver function". With those examples, I think, it won't be misleading anymore. –  comonad Dec 14 '10 at 15:53

Cantor's diagonal argument can be used to show that the number of functions from $\mathbb{N}$ to $\mathbb{N}$ is uncountable. However, of those functions, the number of functions which can be computed by any computer program is countable because there are only countably many computer programs. So there exist functions which cannot be computed by a computer program - in fact, "most" functions have this property. An explicit example is the busy beaver function.

This is not a matter of computing numbers but of computing sequences of numbers, and is a fundamental limitation of computation.

-

Each string (that parses) represents a program that computes a function on $\rm\:\mathbb N$. The argument shows that the number of functions representable by such a language is countable because the number of program strings in the language is countable (note that some programs may compute the same function). But there are uncountably many functions on $\rm\:\mathbb N\:$ by diagonalization (du-Bois-Reymond, Cantor). Thus there are functions not computable by any program in the language.

You might find it helpful to consider a more explicit language. For example, consider a language that represents polynomials with natural coefficients. An analogous argument shows that such polynomials are countable, so we can enumerate them, i.e. we can index the polynomials by naturals: $\rm\ f_i(x),\ \:i\in \mathbb N\:.\$ By diagonalization we may construct a non-polynomial function on $\rm\:\mathbb N\:,\:$ e.g. $\rm\;\ g(n)\ :=\ f_n(n)+1\:.\$ Notice that if $\rm\ f_i = g\$ then $\rm\ f_i(i) = g(i) = f_i(i) + 1\:,\$ a contradiction. Therefore $\rm\:g\:$ is not equal to any polynomial function $\rm\:f_i\:.$

-

You are looking for the Halting Problem and Higher-order logic.

You can't really count the functions via their representations as programs, because you can neither compare all program behaviours nor find out all those programs that won't halt at all. You could define a function which is not only undefined on some or many of uncountably many points, but also can't be proven to be undefined at those points. If you could, then you could count the functions of First-Order Logic, but still not those of Higher Order Logic (Second Order Logic?) and above.

Aditionally, there are functions, that cannot be expressed as programs at all, like the "busy beaver function": It describes for every n the largest finite number of steps after which any ever halting program of length n halts. The program of this function itself would need to have an infinite description length to be correct. The busy beaver function could solve the Halting Problem via timeout, iff it would be expressible as a (finite) program.

What you can count, that are the source codes of all programs. In a similar way can all functions be represented as a finite amount of chalk – in infinite different ways. But even with this, they can only be described but not always in all their properties proven, because there exist theorems that are true even though they can't be proven, and because the possibility of a prove does not always imply the existance of a proven example. To compare it with the busy beaver function: There exist functions that would need an infinite amount of chalk to be proven (in other words: they can't be proven) but not to be described; to map those functions to programs would either require to prove them first (→ impossible or program won't halt) or imply to prove them (→ infinite program description). As an example: Think about a program H that receives the description of another program P as input and needs to calculate an existing but unprovable property of that program P (like halting or not) and therefore would not halt itself; the function could simply be defined on that existing property, which makes it to something else than this non-halting program H.

-
Your example is misleading (i.e. most certainly wrong) and exhibits the same misconception as shown here: cstheory.stackexchange.com/questions/1977/… –  Raphael Dec 14 '10 at 7:40
Hm, you are right, it is misleading - I remove it. The "busy beaver function" is a better example, like Qiaochu Yuan answered. –  comonad Dec 14 '10 at 15:42
Can you reinsert the wrong example and mark it as such? Many people have this problem so it might be worthwhile to explicitly state the difference. –  Raphael Dec 14 '10 at 18:39
oh, I'll remember that for the next time. The misleading example was using the "3n+1"-problem as function and program, where the program searches for an counter-example (and would probably not halt) and the function just states that everything goes to 1. We have to wait for either the program to halt or a genius to prove the function, which could be impossible, too. Then there was a joke about Chuck Norris, who could be the only person to halt the program. –  comonad Dec 14 '10 at 19:25