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) ):



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.



22 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. Tom W.

    Happy New Year Mr. Wildberger! Thank you for once again inspiring and encouraging your readers to go back and find out where we strayed from Reason into Nonsense. I hope 2016 will prove to be a corrective year for you!

  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. 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. Hye Jun

    Here is where two modern math chimeras seem to step on each others’ toes: the axiom of choice should allow us to specify some kind of rule that would allow any real number to be computed, meaning there are no non-computable numbers at all. What a bumbling mess!

  6. Robfrot

    I like your argument here initially but ironically, your statement that a real number chosen entirely at random can never be a computable number is the obvious truth. Since if you choose a computable number then your method of choice is not random as it has been biased by your capacity to compute that number. What this implies is that no “real-world” selection is *entirely* random. And we know that to be true. So the theory kind of hangs together.

  7. Anonymous

    Generally speaking, if almost all real numbers have a property P, then almost all examples of real numbers have the property not-P.

  8. Myren

    Generally speaking, if almost all real numbers have a property P, then almost all real world examples of numbers have the property not-P.
    This law doesn´t hold strictly, but it usually holds, when an argument involving the uncountability of the real numbers is involved.

  9. Dan

    Mainstream mathematics can’t give an example of an unnameable real.
    Constructivist mathematics can’t give an example of a statement where the law of excluded middle fails to hold.
    Your (Ultrafinistic?) mathematics can’t give as an example of a number too complex to express in the real world.
    I wonder if this has some connection to the incompleteness theorems.

  10. David F Mayer

    This shows the subtlety of the concept of “infinity” and the problems with infinite sets. Yet the infinite cannot be avoided. It strikes us not only in pure Mathematics, but in Physics, Information Theory, Thermodynamics, etc, etc. Constructivists, such as Kronecker, rejected actual infinity (and hence of the entirety of Cantor’s work). This rejection seems, at first glance, like a way to avoid the problems of the infinite, but, alas, throws out the baby with the bath. We have a real conundrum here, and there are no easy, facile answers. Kurt Godel opened a transfinite can of worms, didn’t he?

  11. Rhys Thomas

    Many years ago I was unconvinced by Cantor’s diagonalization proof that there exists an infinite set with a larger number of elements (or greater cardinality) than the set of natural numbers N = {1, 2, 3, …}. I devised a more transparent counting scheme than Cantor’s. In essence I reflected decimal fractions about the decimal point so for example 0.25 -> 52.0. Given that the decimal number system is complete over the integers then counting them is equivalent to counting the decimal fractions (albeit by an infinite count) and consequently Cantor’s proof is invalidated. I wrote a letter describing the procedure to an obscure mathematics magazine but the idea received negative responses. Given your own position about the existence of the real numbers then perhaps you may find my argument more acceptable. I would be interested to have your opinion of it.

    1. Rhys Thomas

      I should more clearly have said:
      “Given that the decimal number system is complete over the integers then counting them is equivalent to COMPLETELY counting the decimal fractions (albeit by an infinite count) and consequently Cantor’s proof is invalidated.”

  12. Ramon Quintana

    Dr. Wildberger, I’ve watched many of your videos. I assume that you subscribe to a constructivist philosophy of mathematics. I have read a great deal about Chaitin’s work and completely understand where you skepticism is coming from. I also read Turing’s 1936 paper where he makes references to definable but not computable numbers. I’ve looked more closely and don’t see that he actually provided and example. I am wondering whether you can provide some resources that support your position regarding the non-existence of the irrational, uncomputable numbers. I would greatly appreciate it. And thank you for the blog and videos.

    Ramon Quintana
    Los Angeles, CA

  13. 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
    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……..

  14. 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).

  15. Peter Tobias

    You write:
    “It is impossible to write down any such uncomputable number in a concrete fashion … They are not used in practical applications … 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.”

    What about random numbers? If we generate a random number on the spot, using radioactivity and its detection and getting digit after digit, that number would be uncomputable, wouldn’t it? We have to switch the apparatus at one point, but the number would be defined assuming an unchanged apparatus.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s