The Imitation Game; and the algorithms of the future


Posted on: Dec 16, 2014 by Mike Smith

I'm so excited. My son has just started learning about algorithms; in what they now call "Decision Mathematics". The reason I’m so excited is that, despite his predilection for sport, I am still hoping that he is just about to find his inner geek!

We (and I mean Atos here, but that's not meant to be an overt advert - I'm just using this as a real example) have applied algorithms; really applied them; to the solutions we deliver for our customers. From fraud detection to planning the schedules for football league matches, scoring systems for the Olympic Games and managing the countryside - algorithms are everywhere, helping us solve problems and making the world a better place.

Atos - The Imitation Game; and the algorithms of the future

Perhaps my favourite algorithms are those that solve the seemingly impossible. Problems in computing that are so computationally difficult - they "explode" - very rapidly becoming so vast that no brute force processing could practically give you the answer. You have to be cleverer than that. Without getting bogged down in the detail, it’s about whether the algorithm can solve the problem in a way (and time) that’s proportional to the size of the problem - not which grows exponentially or super-polynomially.

One of the first problems covered in Decision Mathematics is finding the shortest way to your destination. This is used in computing itself; it underpins the network protocols that connect our Internet together, but of course you can also see how this can help you in the real world with planning transport routes and navigation. It turns out that one well known solution to this (to those who are interested in this type of thing!) is called Dijkstra's algorithm.

I am proud of the algorithms that we use in the provision of services to the railway industry in the UK, such as train timetable look-ups that passengers perform. These systems actually use modified versions of Dijkstra. You see with trains it's not only about the distance (and therefore travel time) between your start and end stations; you have to deal with the train schedules too. And on top of that the connections between different routes so that you get the optimum journey from end to end. I'm even more proud for the few talented people who actually know how the code works!

Algorithms are gold. It's where the real value is. Mathematics and abstract algorithms are not patentable though; it's not as straight forward as that. Nevertheless this year a patent was finally granted for Google's "Panda" algorithm which improves their search results. So applied algorithms can indeed be patented.

In the past algorithms have been (or at least I have considered them) to be an equivalent of procedural programming. Systematic. But we now have new techniques, like Google's MapReduce, that brings a more functional and parallel view of the world. And new algorithm opportunities.

Today's train timetabling applications are, I would submit, fast enough. We do get sub-second answers to our queries. And it's no mean feat with over 2500 stations, hundreds of routes and with trains splitting up and joining together. Though I'd like to see a Hadoop research project exploring this area. There's bound to be be some Big Data and application of 'R' here. It’s when you step up from just a single point-to-point journey to visiting a collection of cities and returning home it becomes even more interesting; that’s the travelling salesman problem, and it’s hard - “NP-hard”.

A new film is showing in cinemas at the moment - The Imitation Game; Benedict Cumberbatch plays Alan Turing who uses algorithms to break codes, providing spine-tingling moments when it finally works. Though I believe Turing's most significant contribution in this field is his Turing machine, which (theoretically) simulates the logic of ANY computer algorithm and which ultimately led to the real computers as we have them today. When I talk about the problems being solved in a reasonable time, or being hard, it’s actually whether they can be solved using a deterministic or non-deterministic Turing machine in “polynomial time”. (The Atos blog is meant to stretch our understanding ... further research is left to the reader!)

So where are we going with this? There are many interesting converging technologies at the moment, and they are very accessible, enabling anyone (who has the desire) to explore this area: I myself have been setting up a Raspberry Pi based compute farm with Hadoop, Linux Containers (and Docker), Puppet, R, Open Stack … and the list goes on. This all provides a platform for algorithm development, testing and deployment. Oh, the long winter evenings just fly by.

But really, this means these now commoditised technologies are now available to everyone; and that is a game-changer.

I envisage a near future where algorithm development will accelerate. Tomorrow’s algorithms will lead to new advances, new approaches and perhaps even for algorithms to create new algorithms themselves. Learning algorithms if you will. Though I hope there will still be a place for human intelligence to complement the world of self-developing algorithms! There is a risk.

It’s a very exciting (and scary) future indeed.

References:

Picture: "Lego Turing Machine Read and write head" by Projet Rubens, ENS Lyon. Licensed under CC-BY-3.0.

Share this blog article


About Mike Smith

Chief Technology Officer, Atos Distinguished Expert and member of the Scientific Community
Mike has been in the IT industry for over 20 years, designing and implementing complex infrastructures that underpin key Government and private sector solutions. Setting Atos technical strategy, researching new technologies and supporting the consulting and architect communities. Previously Mike has held technical and management positions in British Rail, Sema Group and Schlumberger. He has a daughter and a son, both keen on anything but technology. Mike's sporting passion rests with Test Match Special, and is jealous/proud of his son's Ice Hockey skills.

Follow or contact Mike