The trouble with Copenhagen

Copenhagen - Vesterbro
Copenhagen – Vesterbro (Photo credit: Valerio Fuoglio)

Dr Johnson famously settled an argument on the existence or non-existence of the physical universe by kicking a heavy stone and saying “I refute it thus”.

But when it comes to the science of the micro-universe, the quantum world, no heavy stones seem to be around to be kicked.

I have been thinking about this since I posted a blog about Antony Valentini‘s idea that we could use some very rare particles to communicate at a speed faster than the speed of light.

Valentini’s challenge is to the “Copenhagen interpretation” of what quantum mechanics appears to tell us.

The fundamental difficulty with quantum mechanics is that it says we cannot know, with total accuracy, the position and momentum of a particle. This “uncertainty” is what creates the “spooky interaction at a distance” – because if we measure the momentum of one paired particle then uncertainty and energy conservation laws “appear” to make the other particle assume a certain state instantaneously.

In the “Copenhagen interpretation” we are essentially asked to accept that this is due to an instantaneous “collapse” of the physical laws we have been using to this point. It’s as if our quantum rules are just a window on to a “real” physical world and that our poking shakes up what is going on behind the scenes in ways we cannot hope to understand.

That’s not very convincing, though (even if it “works”).

So, what are the alternatives?

Valentini is reviving an idea of Louis DeBroglie that was rejected in favour of the “Copenhagen interpretation”: namely that our paired particles remain linked by a “pilot wave” that communicates the state change instantly.

That, though, appears to offend against the physics of the world of general relativity – we are conditioned to think such instant communication is impossible because our physics tells us that we need infinite energy to move a massive body at the speed of light: hence making that an unbreakable speed limit.

And then there is the “many worlds” interpretation – namely that all that might happen does happen and so there are an infinite number of those paired particles and “our universe” is just one of an infinite number.

None of them really seem that satisfactory an explanation.

Enhanced by Zemanta

She’ll die soon, but everybody dies

Blade Runner 1982
Blade Runner 1982 (Photo credit: Dallas1200am)

If you recognise the line then chances are, like me, you saw the original cut of Blade Runner in the cinema (the line was changed in a subtle but very important way in later cuts).

The film is now over thirty years old – but like a true science fiction classic (2001: A Space Odyssey is the archetype) – it seems almost timeless and everytime you watch it you see something new.

And now the University of York is to consider the film alongside cave art and Shakespeare’s sonnets:

We chose these particular case studies for several reasons. We wanted examples of totally different art forms and media; we wanted a wide historical and cultural reach; we wanted artefacts that have already been subject to extensive debate (part of the interest is in the nature of those debates); and we wanted examples that might usefully reveal different aspects of the two principal kinds of values in our study. 

We are planning three intensive workshops on these case studies bringing together experts from different perspectives and disciplines: archaeologists and palaeontologists for the cave paintings, Shakespeare scholars and literary theorists for the Sonnets, film theorists and critics for the film. We are delighted, for example, that Jill Cook, who curated the highly successful exhibition on “Ice Age Art: Arrival of the Modern Mind” at the British Museum, will contribute to the Chauvet workshop. Throughout there will be an input also from aesthetics and philosophy of art. The interdisciplinary nature of the enquiry is crucial to it. 
The day long seminar on Blade Runner is on 11 April. Plus, there’s a showing: it’s not often you get to see the classics back in a theatre, so that might be of interest
Enhanced by Zemanta

Why we’ll never meet aliens

First page from the manuscript explaining the ...
First page from the manuscript explaining the general theory of relativity (Photo credit: Wikipedia)

Well, the answer is pretty plain: Einstein‘s theory of general relativity – which even in the last month has added to it’s already impressive list of predictive successes – tells us that to travel at the speed of light a massive body  would require an infinite amount of propulsive energy. In other words, things are too far away and travel too slow for us to ever hope to meet aliens.

But what if – and it’s a very big if – we could communicate with them, instantaneously? GR tells us massive bodies cannot travel fast, or rather along a null time line – which is what really matters if you want to be alive when you arrive at your destination – but information has no mass as such.

Intriguingly, an article in the current edition of the New Scientist looks at ways in which quantum entanglement could be used to pass information – instantaneously – across any distance at all. Quantum entanglement is one of the stranger things we can see and measure today – Einstein dismissed it as “spooky interaction at a distance” – and essentially means that we can take two similar paired particles and by measuring the state of one can instantaneously see the other part of the pair fall into a particular state (e.g., if the paired particles are electrons and we measure one’s quantum spin, the other instantly is seen to have the other spin – no matter how far away it is at the time).

Entanglement does not allow us to transmit information though, because of what the cosmologist Antony Valentini calls, in an analogy with thermodynamic “heat death”, the “quantum death” of the universe – in essence, he says that in the instants following the Big Bang physical particles dropped into a state in which – say – all electron spins were completely evenly distributed, meaning that we cannot find electrons with which to send information – just random noise.

But – he also suggests – inflation – the super-rapid expansion of the very early universe may also have left us with a very small proportion of particles that escaped “quantum death” – just as inflation meant that the universe is not completely smooth because it pushed things apart at such a rate that random quantum fluctuations were left as a permanent imprint.

If we could find such particles we could use them to send messages across the universe at infinite speed.

Perhaps we are already surrounded by such “messages”: those who theorise about intelligent life elsewhere in the universe are puzzled that we have not yet detected any signs of it, despite now knowing that planets are extremely common. That might suggest either intelligent life is very rare, or very short-lived or that – by looking at the electromagnetic spectrum – we are simply barking up the wrong tree.

Before we get too excited I have to add a few caveats:

  • While Valentini is a serious and credible scientist and has published papers which show, he says, the predictive power of his theory (NB he’s not the one speculating about alien communication – that’s just me) – such as the observed characteristics of the cosmic microwave background (an “echo” of the big bang) – his views are far from the scientific consensus.
  • To test the theories we would have to either be incredibly lucky or detect the decay products of a particle – the gravitino – we have little evidence for beyond a pleasing theoretical symmetry between what we know about “standard” particle physics and theories of quantum gravity.
  • Even if we did detect and capture such particles they alone would not allow us to escape the confines of general relativity – as they are massive and so while they could allow two parties to theoretically communicate instantly, the parties themselves would still be confined by GR’s spacetime – communicating with aliens would require us and them in someway to use such particles that were already out there, and perhaps have been whizzing about since the big bang itself.

But we can dream!

Update; You may want to read Andy Lutomirski’s comment which, I think it’s fair to say, is a one paragraph statement of the consensus physics. I am not qualified to say he’s wrong and I’m not trying to – merely looking at an interesting theory. And I have tracked down Anthony Valentini’s 2001 paper on this too.

Enhanced by Zemanta

Sometimes, admitting defeat is the very best thing you can do

English: Screenshot of GDB, the debugger of th...
English: Screenshot of GDB, the debugger of the GNU Project. . (Photo credit: Wikipedia)

I have spent the last month and half or so writing a particular computer program to model how some code would run on a 16 core “network-on-chip” device.

There were a lot of problems to get over – for although I had already written a Groovy/Java program to do the same thing, that code just was not up to handling the additional level of complexity I wanted for this iteration, so the whole thing had to be redone in C/C++.

About three weeks ago I got to the point where the code compiled and it should have been doing what I wanted, but it was crashing with memory bugs, a lot.

Debugging multi-threaded Posix Threads code is not meant to be easy but I was able – after teaching myself the basics of the GNU debugger (GDB) – to make a lot of progress (having realised that the old programmer’s saw of “if God had wanted us to use debuggers, she wouldn’t have given us printf” does not raise many laughs when you are dealing with multi-threaded code).

I discovered that the bugs were in my four year old red-black tree code. I had used it before in many situations and never had a problem, but also realised that where I used it before (and where I am still using it now), I was continually adding nodes to the tree and not deleting them. The deletion code was wrong.

Most people write their red-black tree code having read Introduction to Algorithms – but here, at least, I was not like most people. I had written the code myself more or less from scratch, piecing together the various things I needed to do from a lot of different online sources. And I was very proud of that too.

But that also meant that, when I tried to fix the code by looking at the canonical description in “Introduction…” the match was poor and my model was, at a quite fundamental level, different (I used null pointers for the leaves, not the “guard node” approach advocated in the book.)

I thought I could get around the issue by not doing any rebalancing after a deletion – after all I was still inserting nodes even as I was deleting them and my insertion code seems (and still seems) quite robust.

But while that allowed by code to run quite a lot longer before falling over, it still fell over. I had to face the facts and use the Standard Template Library (STL) classes – map and set.

I started work on that on Friday on a long train journey. I thought it would be weeks of further chopping and changing. In fact it took little more than 48 hours and I am wondering why I put myself through such misery when robust and well-tested solutions were always to hand (I kept my code for one tree I used where I am only doing insertions – as converting that would have taken a further day, but that was the margin I was operating in – having contemplated weeks, I now worried it would take more than a few hours).

The new code seems pretty robust, but I am struggling to get it on the university’s compute server as that is now under such heavy load, and so I am thinking of adding an nCurses interface while I wait.

Admitting defeat was the quickest way, it seems, to victory. Something worth remembering, perhaps, when your software project is in trouble.

Enhanced by Zemanta

Why Candy Crush is so difficult – and popular?

【APP遊戲】Candy Crush Saga
Candy Crush Saga (Photo credit: Albert.hsieh)

If the evidence of my commute is any guide then Candy Crush Saga probably uses as much compute cycles as any other program in London – it is wildly popular.

And if you are player (I am not) then you shouldn’t be surprised or disappointed if you actually struggle with it – because, in fact, there are no obvious “solutions” to the “problems” you face as a player.

Toby Walsh of the University of South Wales has published a paper than shows that the “problems” of Candy Crush are in the class of what is known as “NP”.

NP problems are those which we do not know in advance what the solution is, but for which we can relatively quickly check that the solution applied is correct. In fact NP problems are at the core of internet (and most serious) encryption – internet encryption is difficult to crack in an attack but decryption is easy if the keys  are known.

NP problems are in distinction from “P” problems for which we know, in advance, both a procedure to solve the problem and to check our answer is correct. The “P” here stands for “polynomial time” – meaning we can tell how long the problem will take to solve at the start because it is some multiple (a polynomial) of its initial complexity – long division by pen and paper is a good example from everyday life – we know how to do it and we can instinctively tell how long it will take just by looking at the length of the numbers we are dividing.

Some – but not many – mathematicians believe that NP problems are really just P problems in disguise – it is just that we have not just discovered the way to solve them. In fact it can be shown that if we could find a means of solving a special class of NP problems known as “NP complete” problems then we could solve all NP problems. But most mathematicians believe that NP problems are inherently not amenable to being solved by simple procedures in polynomial time, while yet others think that such a procedure might exist but that the polynomial will be so large that we might see little advantage in cracking the problem.

In the meantime a whole industry has arisen to offer software to solve – though heuristics (informed guesses) and approximations some of the most important NP problems – such as scheduling school or train timetables.

It’s probably not an unreasonable assumption that people like Candy Crush precisely because it is so difficult and because, it would appear, no one is ever going to come up with a way of quickly solving the problems. We can get better by playing more – so that our heuristic sense of what works increases, but no one is going to emerge as an invincible player – because that is inherently not possible. Probably.

(If you want to know more and are not afraid of some maths, then P, NP, and NP-Completeness: The Basics of Computational Complexity might be worth having a look at.)

Enhanced by Zemanta

A multithreaded “optimal” page replacement algorithm

Werbung mit Jumbo
Werbung mit Jumbo (Photo credit: Wikipedia)

Any textbook discussion of page replacement algorithms will quickly turn to Belady’s “optimal” (OPT) algorithm. This selects for replacement the page with the longest reuse distance – in other words the memory page currently in the main store that we will not need again for the longest time (possibly never).

As this OPT proposal requires foreknowledge of what a program is going to do it is sometimes described as the “clairvoyant” page replacement algorithm and it is certainly not one you see in a general use operating system.

It can be used in embedded computing environments though – after all if your software does one thing over and over again you can profile it and know the reuse distances of pages at a given moment.

But that really only applies to a single threaded environment. When there are a multitude of threads running I do not really think it is possible to have an OPT algorithm at all – as the system displays some of the characteristics of a “chaotic system” – namely small inaccuracies of measurement at the start become large anomalies over time – thread scheduling algorithms ensure that and I doubt that any two runs of a multithreaded system generate the same global memory reference strings.

So we are left with heuristics in how to approximate OPT.

And I am writing this because I think I picked the wrong one and now need to pick a better one.

My scheme was that each thread had its own record of pages it used and picked the page with the longest reuse distance from that.

But that’s simply not adequate as it favours the first thread to run – it can fill up the main store with its pages and then, when the next thread starts it could be left with only one page in memory at a time. It can force one of the first thread’s pages out at the start but then the page it brings in is more or less automatically the one it has to force out at its next different page reference.

In reality the second thread would likely very slowly grow its page set – as there would be some degree of page sharing with the other thread (through shared libraries and so on) but clearly the first thread would be privileged.

Instead, I think I am going to have to enforce a “global OPT” where each thread picks from the global pool. That arrangement is less than optimal too – because a page in heavy demand by one thread may have an infinite reuse distance for another – and so we would get a sort of “false selection” – where a page is repeatedly being brought in and out of memory.

A true OPT would, in multithreaded code, really have to be clairvoyant as it would have to know how the scheduler and I/O devices were going to work at any moment: unless, that is, we could build a fully deterministic system, which I doubt.

Enhanced by Zemanta

Russia Today is a garbage TV station

English: Russia Today logo
English: Russia Today logo (Photo credit: Wikipedia)

Buzzfeed is probably not the first place you would go to in search for news but you would still trust it more than  the Kremlin’s garbage RT television station.

RT advertised itself in Britain with a deliberate appeal to anti-science conspiracists. Support for the lunacies of the “9/11 Truther” variety are only the most prominent.

Other idiocies included reporting that the Russian military intercepted the 2013 Urals meteorite.

It’s garbage and why it is still being broadcast on  British terrestrial television is beyond any explanation except that the Kremlin’s dirty money talks.

Enhanced by Zemanta

Trying to stay calm

English: MDB Debugger Screen Shot
English: MDB Debugger Screen Shot (Photo credit: Wikipedia)

Debugging can be deeply frustrating. Not knowing how the debugger works can make it worse.

Still, there are always books (ordered today) and the deeper assurance that, in computing, nothing is truly random – your code breaks for a reason: find the reason and you fix the code.

At least that is what I am telling myself.

Enhanced by Zemanta