Tagged: New Scientist

Incompleteness in the natural world


Gödel Incompleteness Theorem

Gödel Incompleteness Theorem (Photo credit: janoma.cl)

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.

Related articles

Programming languages in the New Scientist


Donald Ervin Knuth

Donald Ervin Knuth (Photo credit: Wikipedia)

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.

Related articles

Time’s arrow


English: Lee Smolin at Harvard University

English: Lee Smolin at Harvard University (Photo credit: Wikipedia)

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 physics – quantum 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.

Related articles

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

Patent

Patent (Photo credit: brunosan)

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.
Related articles

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?

Related articles

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


A Faraday cage in operation: the woman inside ...

A Faraday cage in operation: the woman inside is protected from the electric arc by the cage. Photograph taken at the Palais de la Découverte (Discovery Palace). (Photo credit: Wikipedia)

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.

Related articles

Online translation a new way to learn a language fast?


Flags of Spain and MexicoThis 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.

Related articles

Hiding in plain silence via Skype


Skype 1.0 running on an Android 2.2 device

Skype 1.0 running on an Android 2.2 device (Photo credit: Wikipedia)

This week’s New Scientist reports that Polish computer scientist Wojciech Mazurczyk and his colleagues have found a way to use silence in Skype calls to encrypt data.

Silence in Skype is signified by 70 bit packets instead of 130 bit packets that carry speech. Skype Hide allows users to inject encrypted data into those 70 bits.

An eavesdropper listening to the call would therefore hear nothing.

Of course that wouldn’t stop somebody delving into the packets and rooting out the encrypted data – whether they could decrypt that is another matter.

In the end Skype probably cannot be trusted for secure communications because it’s algorithms are proprietary – we simply do not know in detail how it works and whether anybody is cracking it.

Having worked with opposition politicians who use Skype to evade state intrusion, this lack-of-trust-by-design has always bothered me: but the it is hard to explain one-way functions to most people anyway.

Skype Hide is due to be publicly demo’ed in June at a steganography conference in Montpellier.

Related articles

Pykrete revisted


pykrete meets hammer

pykrete meets hammer (Photo credit: Genista)

The current issue of New Scientist has a short but interesting piece about pykrete – the material, made of ice and saw dust, once proposed as the basis for aircraft carrier production during the Battle of the Atlantic – a conflict at its very peak 70 years ago.

In essence, while Britain, America and the Soviet Union between them could, by the end of 1942 deploy superior forces to the Nazis and deliver hammer blows – such as that seen at Stalingrad and in a smaller, but still strategically vital, way in the Western Desert, Britain was in severe danger of running out of food and fuel because of losses to the U-Boats in the Atlantic.

The battle was fought in science and engineering as much as in bullets, bombs and torpedoes. Radar (or RDF as the British called it) and Sonar (ASDIC was the British name) were not invented during the conflict but they were improved and perfected as a direct result (the cavity magnetron – now found in almost every western home in a microwave oven – was an essential innovation invented in 1940 and deployed to devastating effect in US and British planes for centimetric radar in the battle). And, of course, the greatest secret of all – the British/Polish cracking of the Enigma machine – was also central (the British got back “in” to the German navy enigma in December 1942).

Pykrete was part of this scientific battle – based around the idea of Geoffrey Pyke, the archetypal dotty scientist (and according to Wikipedia first cousin of Magnus Pyke, so amiable eccentricity  was plainly a family characteristic) . I first read of pykrete in Giles Fodden’s Turbulence – and to be honest the New Scientist article doesn’t take me much beyond the novel except to confirm some of the more bizarre episodes in the book (such as Mountbatten’s HQ being in cellars underneath Smithfield meat market) and the rather odd vignette of Canadian archivists claiming to know nothing of detailed plans they once bandied about 20 years ago (does someone fear Al-Q’ida or the North Koreans are building a pykrete boat?).

The New Scientist piece does suggest, though, that some of the wilder hopes for pykrete were misconceived, but in truth we still don’t know if it could or would be viable. By late 1942 the crack in Engima, combined with longer range aircraft, faster cargo ships, centimetric radar (which allowed much finer resolution and so made it easier to pick out U-boats on the surface)  and Leigh Lights meant that the balance of forces was shifting dramatically against the Kriegsmarine and the question of whether pykrete could have worked was rendered moot.

  • Anyone interested in the role of science in the Second World War would be well advised to see if they could pick up a copy of Brian Johnson’s Secret War: now 35 years old – and an accompaniment to the BBC series of the same name (which for the first time revealed the truth of “Station X” and the Enigma crack) – it is a tale of genius and daring-do and the good guys win in the end.
Related articles

Some questions about the science of magic chocolate


This image was selected as a picture of the we...

 (Photo credit: Wikipedia)

I have to be careful here, as it’s not unknown for bloggers to be sued in the English courts for the things they write about science. So I will begin by saying I am not, and have no intention of, casting aspersions on the integrity of any of the authors of the paper I am about to discuss. Indeed, my main aim is to ask a few questions.

The paper is “Effects of Intentionally Enhanced Chocolate on Mood“, published in 2007 in issue 5 of volume 3 of “Explore: The Journal of Science and Healing” by Dean Radin and Gail Hayssen, both of the Institute of Noetic Sciences in California, and James Walsh of Hawaiian Vintage Chocolate.

The reason it came to my attention today is because it was mentioned in the “Feedback” diary column of the current issue of the New Scientist:

the authors insist that in “future efforts to replicate this finding… persons holding explicitly negative expectations should not be allowed to participate for the same reason that dirty test tubes are not allowed in biology experiments”. [Correspondent] asks whether this may be “the most comprehensive pre-emptive strike ever” against any attempt to replicate the results.

But I want to ask a few questions about the findings of the report which are, in summary, that casting a spell over chocolate makes it a more effective mood improver.

In their introduction to the paper the authors state:

Cumulatively, the empirical evidence supports the plausibility that MMI [mind-matter interaction] phenomena do exist.

Unfortunately, the source quoted for this is a book -Entangled Minds - so I cannot check if this is based on peer reviewed science. But you can read this review (as well as those on Amazon) – and make your own mind up.

Again, not doubting their sincerity, I do have to question their understanding of physics when they state:

Similarities between ancient beliefs about contact magic and the modern phenomenon of quantum entanglement raise the possibility that, like other ethnohistorical medical therapies once dismissed as superstition – eg, the use of leeches and maggots in medicine – some practices such as blessing food may reflect more than magical thinking or an expression of gratitude.

The study measured the mood of the eaters of chocolate over a week. Three groups ate chocolate “blessed” in various ways and one ate unblessed chocolate.

The first thing that is not clear (at least to me) is the size of each group. The experiment is described as having been designed for 60 participants, but then states that 75 signed informed consents before reporting that 62 “completed all phases of the study”. Does that mean that 13 dropped out during it? As readers of Bad Pharma will know it is an error to simply ignore drop outs (if they are there – as I say it is not clear.)

The researchers base their conclusion that -

This experiment supports the ethnohistorical lore suggesting that the act of blessing food, with good intentions, may go beyond mere superstitious ritual – it may also have measurable consequences

- substantially on the changes in mood on one day – day 5 of the 7.

The researchers say that the p-value for their finding on that day is 0.0001 – ie there is a 1 in 10000 chance this is the result of chance alone.

I have to say I just not convinced (not by their statistics which I am sure are sound) but by the argument. Too small a sample, too short a period, too many variables being measured (ie days, different groups), a lack of clarity about participation and so on. But I would really appreciate it if someone who had a stronger background in statistics than me had a look.

Related articles