# Uncomputable decimals and measure theory: is it nonsense?

Modern Measure Theory has something of a glitch. It asserts, as a main result, something which is rather obviously logically problematic (I am feeling polite this New Year’s morning!) Let’s talk a little about this subject today.

Modern measure theory studies, for example, the interval [0,1] of so-called real numbers. There are quite a lot of different ways of trying to conjure these real numbers into existence, and I have discussed some of these at length in many of my YouTube videos and also here in this blog: Dedekind cuts, Cauchy sequences of rationals, continued fractions, infinite decimals, or just via some axiomatic wishful thinking. In this list, and in what follows, I will suppress my natural inclination to put all dubious concepts in quotes. So don’t believe for a second that I buy most of the notions I am now going to talk about.

Measure theory texts are remarkably casual about defining and constructing the real numbers. Let’s just assume that they are there, shall we? Once we have the real numbers, measure theory asserts that it is meaningful to consider various infinite subsets of them, and to assign numbers that measure the extent of these various subsets, or at least some of them. The numbers that are assigned are also typically real numbers. The starting point of all this is familiar and reasonable: that a rational interval [a,b], where a,b are rational numbers and a is less than or equal to b, ought to have measure (b-a).

So measure theory is an elaborate scheme that attempts to extend this simple primary school intuition to the rather more convoluted, and logically problematic, arena of real numbers and their subsets. And it wants to do this without addressing, or even acknowledging, any of the serious logical problems that people (like me) have been pointing out for quite a long time.

If you open a book on modern measure theory, you will find a long chain of definitions and theorems: so-called. But what you will not find, along with  a thorough discussion of the logical problems, is a wide range of illustrative examples. This is a theory that floats freely above the unpleasant constraint of exhibiting concrete examples.

Your typical student is of course not happy with this situation: how can she verify independently that the ideas actually have some tangible meaning? Young people are obliged to accept the theories they learn as undergraduates on the terms they are given, and as usual appeals to authority play a big role. And when they turn to the internet, as they do these days, they often find the same assumptions and lack of interest in specific examples and concrete computations.

Here, to illustrate, is the Example section of the Wikipedia entry on Measure, which is what you get when you search for Measure Theory (from Wikipedia at https://en.wikipedia.org/wiki/Measure_(mathematics) ):

Examples

___________________________

Some important measures are listed here.

Other ‘named’ measures used in various theories include: Borel measure, Jordan measure, ergodic measure, Euler measure, Gaussian measure, Baire measure,Radon measure, Young measure, and strong measure zero.

In physics an example of a measure is spatial distribution of mass (see e.g., gravity potential), or another non-negative extensive property, conserved (seeconservation law for a list of these) or not. Negative values lead to signed measures, see “generalizations” below.

Liouville measure, known also as the natural volume form on a symplectic manifold, is useful in classical statistical and Hamiltonian mechanics.

Gibbs measure is widely used in statistical mechanics, often under the name canonical ensemble.

_______________________________

(Back to the regular channel) Now one of the serious problems with theories which float independent of examples is that it becomes harder to tell if we have overstepped logical bounds. This is a problem with many theories based on real numbers.

Here is a key illustration: modern measure theory asserts that the real numbers with which it is preoccupied actually fall into two types: the computable ones, and the uncomputable ones. Computable ones include rational numbers, and all irrational numbers that (supposedly) arise as algebraic numbers (solutions of polynomial equations), definite integrals, infinite sums, infinite products, values of transcendental functions; and in fact any kind of computer program.

These include sqrt(2), ln 10, pi, e, sqrt(3+sqrt(5)), Euler’s constant gamma, values of the zeta function, gamma function, etc. etc. Every number that you will ever meet concretely in a mathematics course is a computable number. Any kind of decimal that is conjured up by some pattern, say 0.1101001000100001000001…, or even by some rule such as 0.a_1 a_2 a_3 … where  a_i is 1 unless i is an odd perfect number, in which case  a_i=2, is a computable number.

And what is then an uncomputable real number?? Hmm.. let’s just say this rather quickly and then move on to something more interesting, okay? Right: an uncomputable real number is just a real number that is not computable.

Uhh.. such as…? Sorry, but there are no known examples. It is impossible to write down any such uncomputable number in a concrete fashion. And what do these uncomputable numbers do for us? Well, the short answer is: nothing. They are not used in practical applications, and even theoretically, they don’t gain us anything. But they are there, my friends—oh yes, they are there — because the measure theory texts tell us they are!

And the measure theory texts tell us even more: that the uncomputable real numbers in fact swamp the computable ones measure-theoretically. In the interval [0,1], the computable numbers have measure zero, while the uncomputable numbers have measure one.

Yes, you heard correctly, this is a bona-fide theorem of modern measure theory: the computable numbers in [0,1] have measure zero, while the uncomputable numbers in [0,1] have measure one!

Oh, sure. So according to modern probability theory, which is based on measure theory, the probability of picking a random real number in [0,1] and getting a computable one is zero. Yet no measure theorist can give us even one example of a single uncomputable real number.

This is modern pure mathematics going beyond parody. Future generations are going to shake their heads in disbelief that we happily swallowed this kind of thing without even a trace of resistance, or at least disbelief.

But this is 2016, and the start of a New Year! I hope you will join me in an exciting venture to expose some of the many logical blemishes of modern pure mathematics, and to propose some much better alternatives — theories that actually make sense. Tell your friends, spread the word, and let’s not be afraid of thinking differently. Happy New Year.

## 9 thoughts on “Uncomputable decimals and measure theory: is it nonsense?”

1. William Tanksley

Although the uncomputable numbers are useless, they’re not impossible to describe. Chaitin’s Omega (see Wikipedia) is a fascinating example of an uncomputable number with a description (and the description is precise enough to reveal randomness properties between the number’s digits).
What’s especially hilarious to me is that Omega is a member of the “nameable numbers”, and the measure of the nameable numbers is _also_ zero — with the same results as described in the original post.
Thank you for your work on this topic, Dr. Wildberger.

2. Mark

Excellent article as usual. Happy New Year to you too & I can’t wait for more like this.

3. paul19642014

Happy New Year, Norman.

Pure mathematics wants to ‘jump to the end’ of things instead of going stepwise, it seems. Moving both inwards (to fractions) and outwards (to natural number) from the interval [0,1] entails progressively more and more information in their descriptions, which is data that must be ‘sifted out’ by computation (effort) and cannot simply be willed into existence. The product of those efforts will never stand ‘complete’ of course.

So even something as simple as counting 1,2,3,.. represents a process of ever-growing complexity?

1. njwildberger: tangential thoughts Post author

That depends very much on whether or not you believe that Chaitin’s construction is really a construction of a real number. Do you think it is?

1. William Tanksley

That depends on the meaning of “is”. Since I agree there are no real numbers, Chaitin’s Omega joins them in nonexistence. However, it’s very distinctly defined with properties which would set it apart from unnameable reals and non-normal reals if either existed; so its properties make it clear that as useless as uncomputable reals are, almost all of the reals are both useless _and_ completely unreachable by any means. You can’t use them, you can’t name them, you can’t think about them, can’t reason using them…
And YET almost all of modern mathematics depends utterly on them somehow existing.

4. Brandon

Meanwhile, math students worldwide are staring at their homework assignments that read: “For all real numbers x, show that … is true.” No wonder math problems take so long!

5. Em

There are *many* standard examples of non-computable numbers, which have been well-known for decades. Two very canonical examples are:

———————————————
1. The set of (codes for) Turing machines which eventually halt.
(These are coded with natural numbers as usual, so we get a natural list of all Turing machines
M_0, M_1, M_2, ….,
and then we form the number
0.d_0d_1d_2……..
where d_i is 0/1, with d_i=0 iff M_i halts.)
——————————————–
2. The set of Sigma_1 truths over the natural numbers N, in the language of Peano arithmetic.
(Again we code and list the sentences
phi_0, phi_1, …………..
and form a number as above.)
One can easily look up a precise explanation of what Sigma_1 in the language of Peano arithmetic means, but roughly, it is the true sentences of the form

“There exists a natural number n such that [ ……….psi(n)……….. ]”,

where the part psi(n) is Delta_0, which means roughly that it is
a statement about n which is “locally verifiable”, meaning that it only refers to numbers which are “nearby” n. That is, for example, psi(n) could be of the form

“for all x < n*n there is y < x*x*x*x*n*n*n*n such that [ …..phi(x,y)…..]"
where * is multiplication and phi uses no quantifiers "for all" or "there exists";
phi is built from the symbols in the set
{ 0, 1, +, *, <, "and", "not", (, ), x, y, n }.
———————————————
Examples (1) and (2) are basically equivalent, i.e. computationally equivalent — there are Turing machines which, given one side as input, turns it into the other side.
——————————————–
Examples (1) and (2) are not computable, but they are *computably enumerable":
for example for (2), there is a Turing machine which which runs forever, and outputs a list
rho_0, rho_1, rho_2, …………….
such that T = { rho_n | n in N } is the set of all true Sigma_1 sentences over N.
(But there's no Turing machine M which can always correctly answer questions of the form “Is rho in T?'', with a "yes/no" answer, in finite time.)
———————————————————–
More complex examples:
———————————————————
One can then naturally consider more complex sentences true over the natural numbers.
The Sigma_2 sentences are those of the form
“there exists n in N [ for all m in N [ psi(n,m) ]]'',
where psi is Delta_0. This yields another non-computable number, and this time, the set of sentences is not computably enumerable. For each n, one can consider the true Sigma_{n+1} sentences, and this set is not computable from the set of true Sigma_{n+1} sentences, so we have a hierarchy of ever more complex numbers.
————————————————————-
One can then consider the "join" of the numbers constructed above, interweaving all together;
this codes the set of all true sentences over N. This is again more complex than any of the Sigma_n theories above, and gives a yet more complex number. Call this theory / number T.
————————————————————-
One can then consider "computation relative to T", where a Turing machine M is as usual, but it is also equipped with the ability to ask "Is the formula phi in T?", and it has an "oracle" which gives it the correct answer immediately. Similarly, we have Sigma_1-truth-in-predicate-T over N.
This relativizes the examples (1) and (2) above the complexity of T, and we can start the entire hierarchy over, producing yet more complex numbers / theories.
—————————————————————-
And so on……..

6. Evgeniy Kucherenko

Hello, Mr. Wildberger!
I’m very inspired by your vision of irrational numbers as an algorithm opposite choice. The first time I thought about this then I read a book of V.I. Arnold “Continued fractions” (you can check it on youtube). But you structured my thoughts, so I’m very grateful to you. And of course I have many questions.
So, can we represent Sqrt (-1), also known as ‘I’, as an elementary algorithm of the rotation? But it is problematic to decompose x ^ 2 = -1 as continued fraction.
Also, what about continued fractions of quadratic irrationals? As we know, it has an accurate period. It looks like a infinite loop with finite instructions like ‘while (true) {DoFirst (), DoSecond (), // and so on}’.
Also we see that composition of “algorithms” like Sqrt (2) * Sqrt (2) gives us a real number (which we can represent as transition or maybe scaling or just point on a line).