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? 
 A: 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\:.$
A: 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.
A: 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.
A: 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.
