Failing software – again


The line above is from a real (and current at time-of-posting) job advertisement for a software developer. I’m not positing it because I think it is bad, shocking or dangerous, but mainly because it is illustrative of the real world: developers are expected to be “pragmatic” when it comes to testing the software they make for correctness.

So when, as happened today with British Airways, we see a major software failure (or at least what looks like a major software failure), maybe we should not be too surprised.

There is more to it, of course, than the fact developers are expected to compromise on testing their code: there is the simple fact that most functions are not computable at all and that for many others we don’t know how to compute them.

For an example of something uncomputable there is Hilbert’s tenth problem:

For any given a Diophantine equation is there a general algorithm that tells us whether or not there is a solution with the unknowns taking integer values…

To explain:

  • A Diophantine equation (named after Diophantus of Alexandria) is a polynomial (e.g., x = y , y^2 + 5x + z^{67} = 0, 3x + 2y +5x^2y^3 + 90 = 7z and so on) equation where all the coefficients of the unknowns are integer (counting number) values and where there are a finite number of unknowns.
  • An algorithm is a set of rules of simple mathematical procedures to solve a problem

So the task is to take a Diophantine equation and not to find a solution but to determine whether such a solution exists – but no such algorithm exists and therefore we cannot write any sort of computer program that would do this for us, no matter how powerful a computer we were using.

And for an example of something for which a solution does exist but which we will struggle to find, there is the famoustravelling salesman problem” – namely given a set of cities all connected by roads (or railways, or air routes) what is the most efficient way of visiting all the cities.

This problem is an example of what is known as an “NP” problem – in other words one for which (we believe) no general algorithm exists to produce a solution in “polynomial time” (meaning in a time related to the length of the input – in this case the number of cities).

Plainly a solution does exist – there is a quickest way to travel to all the cities – but the only immediately available way to be certain of finding this is to try all the solutions.

But that will take time: for even moderately sized problems quite possibly more time than we have before the Sun swallows the Earth. To get round this we have to use heuristics (essentially educated guesswork) or approximations.

In the travelling salesman case those approximations are powerful and efficient – that’s why modern logistics works – but the general point remains the same: in many cases we are building software that approximates the solution to our problem but may not answer it fully correctly and, unless there is a breakthrough which eliminates NP problems as a class, we are always going to be stuck with that.

Advertisements

If you want bad advice, ask a London taxi driver


Steve McNamara, general secretary of the Licensed Taxi Drivers’ Association in London, quoted in the Guardian on the prospect of driverless buses in the capital:

“We don’t have a a lot of confidence in anything that comes out of TfL [Transport for London], to be honest, and the fact that they’re suggesting it means it’s almost certainly likely not to happen.

“Who knows with technology, but some of the simplest things, they still can’t do. The best example is voice recognituion technology.

“If you’ve got it on your car… it’s rubbish. If you’ve got it on your phone, it’s probably worse. They’re all crap, aren’t they? None of them work, and they can’t even get that right. And they expect people to get into driverless cars?”

Where do you begin with this?

Firstly, we should note that the Mayor’s office ran a million miles away from the suggestion – in their own paper – that at some point between now and 2050 driverless buses will be on London’s streets. To make it worse they – plainly less than truthfully – tried to claim that references in their own paper to driverless vehicles were a reference to tube trains.

The disappointing thing is that instead of actually once again pioneering a public transport technology – London gave the world underground railways and once had the world’s most admired bus network too – London’s public admisitrators are not willing to lead.

Before anyone on the left says “what about the jobs”, my reply is “what about them?” Is not the left meant to be about freeing human creativity from the realm of necessity? The issue is the distribution of the opportunities freed by the removal of the need to drive buses – it cannot be about preserving relatively low-skilled jobs that are no longer required.

As for Steve McNamara, I am amused by the fact he thinks speech recognition is the “simplest thing”. Should we reply that  three billion years of evolution produced only one species that can speak so it can’t be that simple? Or perhaps ask McNamara how many languages he can speak given that speech recognition is so simple?

In fact, my guess would be that speech recognition is probably many more times more difficult, computationally speaking, than driving a bus. However the risk of human injury means that speech recognition software is socially more acceptible than driverless vehicles – for now. But I don’t expect that to last.

Time to write a signal handler?


Unix Creators at DEC PDP11
Unix Creators at DEC PDP11 (Photo credit: PanelSwitchman)

I am trying to execute some self-written pieces of software that require a lot of wall clock time – around three weeks.

I run them on the University of York‘s compute server which is rebooted on the first Tuesday of every month, so the window for the software is limited. I have until about 7 am on 5 August before the next reboot.

To add to the complication the server runs Kerberos which does not seem to play well with the screen/NFS combination I am using.

And – I keep killing the applications in error – this time, just half an hour ago I assume I was on a dead terminal session (ie an ssh login which had long since expired) and pressed ctrl-C, only to my horror to discover it was a live screen (it had not responded to ctrl-A, ctrl-A for whatever reason).

Time to add a signal handler to catch ctrl-C to at least give me the option of changing my mind!

President Obama’s campaign and free software


It seems a row has broken out between staff on President Barack Obama’s re-election campaign over the fate of the free software it produced (the article linked President Barack Obamahere refers to it all as “open source” but on this issue I tend to side with RMS and not ESR).

Actually I do not blame the DNC at all for not wanting to release any source (if that is what they want to do – it is not entirely clear). It would simply be foolish to surrender an advantage they have over their opponents if there is no need to do so. Nor does there appear to be any ethical issue involved: the core idea of the free software movement is surely that any user of software should have access to the source code out of which it is built. If the DNC does not distribute the software then they are under no moral or any other obligation to hand out the source code.

By far the worst idea the article talks of is selling the software: that would truly be a breach of the ethics of free software – because plainly trying to use the built software as a revenue stream means keeping the software hidden or forcing users, 1970s Unix-style, to sign NDAs. Either of those is worse than keeping a piece of private software private.

There is a wider question, of course, could distributing the software help build a better world. But if the distribution helps the US republican party, then surely the answer for the DNC is no?

Here we go again


I used to have a blog. It was meant to be about “politics and free software” (not the politics of free software) but ended up being mainly about politics. I wrote the last entry on that in January 2008 and subsequently took it off line (the content is still on my server at home and it was amusing to read it again just now, but it’s not going back up).

My politics haven’t changed – so if you want to do something to make Britain a better place to live I still recommend you start here.

But I am not going to write about politics here. The geeky title ought to give the game away – this one is about computing (and, I suppose, mathematics to an extent).

My inspiration came from this: generally speaking I am in the n – log(n) part of this matrix and while I am not interested in pursuing a career in computing I am passionate about improving my skills and competency, so the comment that a log(n) programmer “maintains a blog in which personal insights and thoughts on programming are shared”, left me with little choice.

Of course I’ll actually have to demonstrate some insights and thoughts too.