# Incompleteness in the natural world

A post inspired by Godel, Escher, Bach, Complexity: A Guided Tour, an article in this week’s New Scientist about the clash between general relativity and quantum mechanics and personal humiliation.

The everyday incompleteness: This is the personal humiliation bit. For the first time ever I went on a “Parkrun” today – the 5km Finsbury Park run, but I dropped out after 2.5km 2km – at the top of a hill and about 250 metres from my front door – I simply thought this is meant to be a leisure activity and I am not enjoying it one little bit. I can offer some excuses – it was really the first time ever I had run outdoors and so it was a bit silly to try a semi-competitive environment for that, I had not warmed up properly and so the first 500 metres were about simply getting breathing and limbs in co-ordination – mais qui s’excuse, s’accuse.

But the sense of incompleteness I want to write about here is not that everyday incompleteness, but a more fundamental one – our inability to fully describe the universe, or rather, a necessary fuzziness in our description.

Let’s begin with three great mathematical or scientific discoveries:

The diagonalisation method and the “incompleteness” of the real numbers: In 1891 Georg Cantor published one of the most beautiful, important and accessible arguments in number theory – through his diagonalisation argument, that proved that the infinity of the real numbers was qualitatively different from and greater than the infinity of the counting numbers.

The infinity of the counting numbers is just what it sounds like – start at one and keep going and you go on infinitely. This is the smallest infinity – called aleph null ($\aleph_0$).

Real numbers include the irrationals – those which cannot be expressed as fractions of counting numbers (Pythagoras shocked himself by discovering that $\sqrt 2$ was such a number). So the reals are all the numbers along a counting line – every single infinitesimal point along that line.

Few would disagree that there are, say, an infinite number of points between 0 and 1 on such a line. But Cantor showed that the number was uncountably infinite – i.e., we cannot just start counting from the first point and keep going. Here’s a brief proof…

Imagine we start to list all the points between 0 and 1 (in binary) – and we number each point, so…

1 is 0.00000000…..
2 is 0.100000000…..
3 is 0.010000000……
4 is 0.0010000000….
n is 0.{n – 2 0s}1{000……}

You can see this can go on for an infinitely countable number of times….

and so on. Now we decide to ‘flip’ the o or 1 at the index number, so we get:

1 is 0.1000000….
2 is 0.1100000….
3 is 0.0110000….
4 is 0.00110000….

And so on. But although we have already used up all the counting numbers we are now generating new numbers which we have not been able to count – this means we have more than $\aleph_0$ numbers in the reals, surely? But you argue, let’s just interleave these new numbers into our list like so….

1 is 0.0000000….
2 is 0.1000000…..
3 is 0.0100000….
4 is 0.1100000….
5 is 0.0010000….
6 is 0.0110000….

And so on. This is just another countably infinite set you argue. But, Cantor responds, do the ‘diagonalisation’ trick again and you get…

1 is 0.100000…..
2 is 0.110000….
3 is 0.0110000….
4 is 0.1101000…
5 is 0.00101000…
6 is 0.0110010….

And again we have new numbers, busting the countability of the set. And the point is this: no matter how many times you add the new numbers produced by diagonalisation into your counting list, diagonalisation will produce numbers you have not yet accounted for. From set theory you can show that while the counting numbers are of order (analogous to size) $\aleph_0$, the reals are of order $2^{\aleph_0}$, a far far bigger number – literally an uncountably bigger number.

Gödel’s Incompleteness Theorems: These are not amenable to a blog post length demonstration, but amount to this – we can state mathematical statements we know to be true but we cannot design a complete proof system that incorporates them – or we can state mathematical truths but we cannot build a self-contained system that proves they are true. The analogy with diagonalisation is that we know how to write out any real number between 0 and 1, but we cannot design a system (such as a computer program) that will write them all out – we have to keep ‘breaking’ the system by diagonalising it to find the missing numbers our rules will not generate for us. Gödel’s demonstration of this in 1931 was profoundly shocking to mathematicians as it appeared to many of them to completely undermine the very purpose of maths.

Turing’s Halting Problem: Very closely related to both Gödel’s incompleteness theorems and Cantor’s diagonalisation proof is Alan Turing’s formulation of the ‘halting problem’. Turing proposed a basic model of a computer – what we now refer to as a Turing machine – as an infinite paper tape and a reader (of the tape) and writer (to the tape). The tape’s contents can be interpreted as instructions to move, to write to the tape or to change the machine’s internal state (and that state can determine how the instructions are interpreted).

Now such a machine can easily be made of go into an infinite loop e.g.,:

• The machine begins in the ‘start’ state and reads the tape.  If it reads a 0 or 1 it moves to the right and changes its state to ‘even’.
• If the machine is in the state ‘even’ it reads the tape. If it reads a 0 or 1 it moves to the left and changes its state to ‘start’

You can see that if the tape is marked with two 0s or two 1s or any combination of 0 or 1 in the first two places the machine will loop for ever.

The halting problem is this – can we design a Turing machine that will tell us if a given machine and its instructions will fall into an infinite loop? Turing proved  we cannot without having to discuss any particular methodology … here’s my attempt to recreate his proof:

We can model any other Turing machine though a set of instructions on the tape, so if we have machine $T$ we can have have it model machine $M$ with instructions $I$: i.e., $T(M, I)$

Let us say $T$ can tell whether $M$ will halt or loop forever with instructions $I$ – we don’t need to understand how it does it, just suppose that it does. So if $(M, I)$ will halt $T$ writes ‘yes’, otherwise it writes ‘no’.

Now let us design another machine $T^\prime$ that takes $T(M,I)$ its input but here $T^\prime$ loops forever if $T$ writes ‘yes’ and halts if $T$ writes ‘no’.

Then we have:

$M(I)$ halts or loops – $T(M, I)$ halts – $T^\prime$ loops forever.

But what if we feed $T^\prime$ the input of $T^\prime(T(M, I)$?

$M(I)$ halts or loops – $T(M, I)$ halts – $T^\prime(T(M,I))$ loops forever – $T^\prime(T^\prime(T(M,I)))$ – ??

Because if the second $T^\prime(T^\prime(T(M,I)))$ halted then that would imply that the first had halted – but it is meant to loop forever, and so on…

As with Gödel we have reached a contradiction and so we cannot go further and must conclude that we cannot build a Turing machine (computer) that can solve the halting problem.

Quantum mechanics: The classic, Copenhagen, formulation of quantum mechanics states that the uncertainty of the theory collapses when we observe the world, but the “quantum worlds” theory suggests that actually the various outcomes do take place and we are just experiencing one of them at any given time. The experimental backup for the many worlds theory comes from quantum ‘double-slit’ experiments which suggest particles leave traces of their multiple states in every ‘world’.

What intrigues me: What if our limiting theories – the halting problem, Gödel’s incompleteness theorem, the uncountable infinite, were actually the equivalents of the Copenhagen formulation and, in fact, maths was also a “many world” domain where the incompleteness of the theories was actually the deeper reality – in other words the Turing machine can both loop forever and halt? This is probably, almost certainly, a very naïve analogy between the different theories but, lying in the bath and contemplating my humiliation via incompleteness this morning, it struck me as worth exploring at least.

# Programming languages in the New Scientist

Regular readers will know I am usually unstinting in my praise of the New Scientist. But not this week.

There is a very poor article by Michael Brooks, an admitted non-programmer (would you have someone who could not speak French write on the Académie française?) lamenting the “teetering tower of Binary Babel” of the  “jerry-rigged” programming languages most of which, he claims, are “still thinly veiled versions of Fortran“.

To make it all better, he asserts, “salvation may be at hand in a nascent endeavour in computer science:user-friendly languages that rethink the compiler.”

These languages “allow programmers to see, in real time, exactly what they are constructing as they write their code.”

And he adds: “Bizarrely, the outcome may look rather familiar” – like a spreadsheet he says.

So, actually, we are back with visual programming tools – such as “Subtext“. Donald Knuth can sleep easy then – Brooks is not challenging him as the greatest living writer on programming, that’s for sure.

I am old enough to remember the legend that was Guy Kewney waxing lyrical in the pages of “Personal Computer World” in 1981 about a BASIC generator called “The Last One” which did indeed claim to be the last program you’d need. At least Kewney demonstrated he knew the subject, even if he got that one profoundly wrong.

# Time’s arrow

The forward march of time is possibly the most basic and shared human experience. Whatever else may happen in our lives none of us can make time run backwards  (the title of this post recalls Martin Amis‘s brilliant novel premised on this idea – time running backwards – if you’ve read it you will understand why we are never likely to see it filmed, as 90 minutes of backwards time would be just too much to take.)

Yet, as Lee Smolin points out in this week’s New Scientist, our most fundamental theories of physicsquantum mechanics and general relativity – are time free: they work just as well if time runs the other way round. Physicists square this circle by insisting on only time-forward solutions and by imposing special conditions on our universe. We have even invented a physical category – which has no material existence per se – called entropy and demanded that it always increase.

The accepted physics leaves us in the difficult position of believing that “the future” is not the future at all – it exists and has always existed but we are barred from getting there “ahead of time”. It’s a deep contradiction, though whether this is a flaw in the theories or in human comprehension is what the debate (such as it exists, those who challenge QM and GR are very much in the minority) is all about.

In Smolin’s view (or perhaps my interpretation of it) all of this violates the “Copernican principle” – that we observers are nothing special – that has guided much of physics’s advances of the last five centuries. So what if it is actually telling us that our theories are wrong and like Newtonian gravity is to general relativity, they are merely approximations?

Smolin’s argument is just this. He says we should base our theories on the fundamental observation that time flows in only one direction and so find deeper, truer theories based on unidirectional time.

# Patenting reality

(I was about to post something about this when I noticed the Stephen Fry nomination of Turing’s Universal Machine as a great British “innovation” and decided to write about that first … but the two dovetail as I hope you can see.)

I was alerted to this by an article in the latest edition of the New Scientist (subscription link) -on whether scientific discoveries should be patentable. The New Scientist piece by Stephen Ornes argues strongly and persuasively that the maths at the heart of software should be protected from patents. But having now read the original article Ornes is replying to, I think he has missed the full and horrific scale of what is being proposed by David Edwards, a retired associate professor of maths for the University of Georgia at Athens.

Of course I am not suggesting that Edwards himself is evil, but his proposal certainly is: because he writes, in the current issue of the  Notices of the American Mathematical Society (“Platonism is the Law of the Land”) that not just mathematical discoveries should be patentable but, in fact, all scientific discoveries should be: indeed he explicitly cites general relativity as an idea that could have been covered by a patent.

Edwards is direct in stating his aim:

Up until recently, the economic consequences of these restrictions in intellectual property rights have probably been quite slight. Similarly, the economic consequences of allowing patents for new inventions were also probably quite slight up to about 1800. Until then, patents were mainly import franchises. After 1800 the economic consequences of allowing patents for new inventions became immense as our society moved from a predominately agricultural stage into a predominately industrial stage. Since the end of World War II,our society has been moving into an information stage, and it is becoming more and more important to have property rights appropriate to this stage. We believe that this would best be accomplished by Congress amending the patent laws to allow anything not previously known to man to be patented.

Part of me almost wants this idea to be enacted, because like the failure of prohibition of alcohol it would teach an unforgettable lesson. But as someone who cares about science and the good that science could do for humanity it is deeply chilling.
For instance, it is generally accepted that there is some flaw in our theories of gravity (general relativity) and quantum mechanics in that they do not sit happily beside one another. Making them work together is a great task for physicists. And if we do it – if we find some new theory that links these two children of the 20th century – perhaps it will be as technologically important as it will be scientifically significant (after all, quantum mechanics gave us the transistor and general relativity the global positioning system). But if that theory was locked inside some sort of corporate prison for twenty or twenty-five years it could be that the technological breakthroughs would be delayed just as long.

# Another reason why exercise keeps you younger?

Reading through a copy of the New Scientist from a few weeks back (2 February edition), I was struck by the comment in an article on the effects of sleep on the human body by Nancy Wesensten, a psychologist at the Walter Reed Army Institute of Research in Maryland:

Sleeping deteriorates like everything else does as you age… People have more difficulty falling asleep, and that could account for the cognitive decline we see in normal ageing.

Until I started a vigorous exercise regime about 16 months ago, I really did find it difficult to fall asleep. Since then, while I don’t have my partner’s ability to more or less doze off as soon as my head hits the pillow, I generally no longer have a problem.

I have often seen claims made for exercise as a means of maintaining mental acuity – perhaps there is some substance to those claims and this is the reason?

# Why I would not want to fly in a Dreamliner (yet)

The world’s Dreamliners are currently grounded while regulators and the manufacturer aim to sort out problems with the plane’s batteries – which supply a heavy duty electrical system that replace the more traditional (and heavier) hydraulic controls in other planes.

I imagine, and hope, that the battery problems can be sorted out – though the Lithium Ion system chosen is notorious for overheating and fire risk – or “unexpected rapid oxidisation” as an earlier (non-aviation) LiOn battery fire problem was called.

But what worries me about the planes is a different issue – their outer shell is made of plastic, again considerably lighter than traditional aircraft materials, but lacking the quality of a Faraday Cage.

The Faraday Cage effect is what makes traditional airliners (and motor cars) safe from lightning strikes – lightening represents a terrific concentration of energy but, actually, very little charge – and so when lightning strikes a sheet of metal, like a car or an airliner, the charge is spread and the strike rendered safe (in contrast poor conductors like human flesh burn up, which is what makes us so vulnerable).

Now, the Dreamliner has a metal substructure which is designed to replicate the effect of a Faraday Cage but, having read a critical piece on this in the current edition of the New Scientist, I am not convinced it has been tested enough to be reliable. Anyone who has flown through the heart of an electrical storm – as I did a few years ago coming out of Tbilisi – will understand just how essential it is that the Dreamliner’s electrical properties are fully reliable.

Update: I am a hopeless speller and, as was pointed out to me I mis-spelled ‘lightning’ throughout this the first time round. Apologies.

# Online translation a new way to learn a language fast?

This week’s New Scientist reports (online link below- it’s a short piece in the physical edition on p. 19) that Duolingo – a free online service designed to help people learn a new language by translating web content is working very well.

To probe the site’s effectiveness, Roumen Vesselinov at the City University of New York used standard tests of language ability… he found that students needed an average of 34 hours to learn the equivalent of … the first semester of a university Spanish course.

I have just been over to Duolingo’s site myself – refreshing some French – and it is certainly easy to use. The site’s blog shows that this project has some strong values and has set itself some big targets – it looks well worth exploring.