Indescribable numbers: The theorem that made me fall in love with math

the cardinality of all real numbers that can be described by a terminating computer program to some accuracy is a countable set (since the number of such programs is countable) however, the cardinality of the reals is uncountable.

hence most real numbers cannot be computed beyond a certain accuracy.

Edit (additionally): the set of computable numbers forms a field (if a,b are computable, so is their sum, etc). and there are several movements in "constructive" mathematics, to work exclusively in this field, instead of the field of real numbers. however, many cornerstone theorems in analysis fail in this context, such as, the least upper bound of a bounded increasing computable sequence of computable numbers need not be a computable number [1].

[1] http://en.wikipedia.org/wiki/Computable_number

Theorem A (author's theorem): No mapping from finite-length strings to real numbers will hit all the real numbers.

Theorem B (your theorem): Let's map strings of finite length to real numbers as follows: Consider the string as the specification for a Turing machine. If the specification is syntactically OK as a Turing machine description, and the output is syntactically OK as the decimal expansion of a (potentially infinite) real number, then that string maps to that real number. Otherwise, the string maps to zero. Then this particular mapping doesn't hit all the real numbers.

It's obvious that Theorem B is just a special case of Theorem A. And it's also obvious that Theorem A is a trivial corollary of Cantor's result (that no mapping from natural numbers to real numbers hits all real numbers), with no Turing machines or computation theory anywhere in sight.

I can well believe that Theorem B was either proven by Turing himself, or established in the early years post-Turing; it's low-hanging fruit once you've defined Turing machines and are familiar with Cantor's results. And it could hardly have been proven before the Turing machines were defined! So Theorem B is a special case that could plausibly have first arisen in the 1940's, but Theorem A is actually the theorem the author is talking about.

http://en.wikipedia.org/wiki/Continuum_hypothesis

Not every number though. It turns out that there are numbers that are describable but not computable.

What is the difference? Well here's an example. A Chaitin omega number is the probability that a valid program randomly constructed according to a specific set of rules will eventually halt. It is describable - indeed I just described it. Yet Chaitin has proven that an algorithm to compute it will lead to an algorithm that solves the halting problem, so it cannot be computable.

So there you have it. A class of perfectly describable numbers that are not computable. Indeed it can be proven that we cannot know more than a fixed number of digits for any particular one without increasing the size of our axiom system.