3 comments on “Book Review: Meta Maths, The Quest For Omega

  1. Hi Elwes,

    Thanks for the exciting review. I thought I’d leave a comment, since this is looking rather lonely without one…

    The book does sound quite intriguing and nutritious; hopefully I’ll get time to read such things one day.

    Randomness is certainly very widespread, even in unexpected places. I gave some examples in a lecture today (mainly just for fun, to scare the hell out of my students…it seemed to work…) there are various problems where one wants to construct an analytic function with various weird, horrible properties; one such method is to choose a particular sequence (a_n), and then consider random power series:

    sum_{n=0}^infty u_n a_n z^n,

    where u_0, u_1, u_2, … are independent, identically distributed random variables taking values +1 and -1 with probability 1/2.

    The funny thing is that, even though no-one knows how to find even one single specific pattern of +/- signs to give various horrible results in very simple-looking cases (I’m not sure exactly, but I think even things like a_n = 1/(n+1) and maybe even a_n=1 fall into this category), you will still find with probability one that the u_n pattern of +/- signs works. Human mathematics is highly ordered and inherently non-random I think.

    A fun example from Analysis…!

    Incidentally, Terry Tao on his blog seems to think that one of the main weaknesses of mathematicians is a lack of understanding of pseudo-random behaviour, and that this is why the Navier-Stokes equations are so difficult, which also maybe ties in a little with the above thoughts on randomness and inherently horrible difficulty of maths — although it’s dangerous for me to paraphrase him, of course, in case I’ve misunderstood the point completely…

    Some crazy thoughts of my own: what is the probability that a mathematical statement chosen “at random” is a genuine Theorem? (Of course, all depends on what measure you take — but since the set of all possible statements is countable, there are no measure theoretic difficulties). Is this number incomputable and “random”, similarly to Omega above? It sounds vaguely similar to halting problem stuff.

    It’s clear, though (isn’t it?), that the real numbers are totally inaccessible, just because they’re uncountable, but the total set of all statements and unambiguous formulae (not just Theorems!) is countable. I suppose this also ties in with the random power series example above – the set of all +/- sign patterns is uncountable (and actually canonically isomorphic as a measure space to the interval [0,1] with Lebesgue measure), so we’ve no hope of ever understanding it properly.

  2. Addition to my previous comment:

    My knowledge of Turing machines is very poor, but I now realise my question about the probability of random statements being theorems seems to be roughly equivalent to similar questions about the Omega number (of course the actual numerical values of the probability are maybe not so easily related):

    Given any finite statement, you can write a computer programme which calculates all possible theorems by brute force, according to some specific order (simply applying every axiom one-by-one to see what happens, in a “breadth first” search), and stopping only if it proves the given statement. This is then a Turing machine which halts if and only if a proof of the statement is found. (If there are countably infinitely many axioms, i.e. some kind of “axiom scheme” or whatever, it needs a little bit more work, but is still possible I think).

    Conversely, given any Turing machine, the statement “this Turing machine will halt” is well–defined, and we are simply asking whether this statement is true.

    Of course this is full of sloppiness and inaccuracy; I’ll leave it to you logicians to sort all the definitions out (what exactly does “self-delimiting” mean in this context? What about undecidable statements? etc. etc.)

    Have fun and nutrition!

  3. I believe that people are actually trying to calculate ?. It was a long time ago, but I believe that the gist of it was that you write down all the minimal length programs of length 1 and run through them all until you know how many halt (and hence the probability of any program of length 1 halting). You then do this for all minimal length programs of length 2,3,etc. and hope that your probability will converge on ?, which the authors claimed it was/would (at least one of these). Of course, one of (if not the) toughest bits is deciding whether or not a given program is equivalent to a shorter one in order to exclude it. I believe it was in New Scientist so you may be able to find it somewhere.

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 )

Twitter picture

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

Facebook photo

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

Connecting to %s