Tuesday 26 June 2012

Day 1 of The Alan Turing Centenary Conference in Manchester

I've been attending the Alan Turing Centenary Conference in Manchester. The conference was in the huge and beautiful Manchester Town Hall, and it feels very appropriate to hear these talks in Manchester where Turing worked. The conference was over a weekend, including Saturday 23rd June, which was Turing's birthday 100 years ago. There were too many talks to write about all of them, but here are a few comments on a few of the talks from Day 1.

Vint Cerf is Chief Internet Evangelist for Google, one of the creators of the internet and of TCP/IP. He described the early days of the internet, how they had to make decisions about the size of the address space they would need in order to address each of the devices connected to the internet. Imagine their problem in the 70s, trying to work out how many computers there would be in the future. Now there are about 2-3 billion internet devices connected at any one time, and a load more devices only intermittently connected. Everything is now becoming networked, including Cerf's wine cellar, which of course has a sensor network measuring temperature, humidity and light conditions, and will send an alert to his mobile phone if his wine becomes too warm. See Vint Cerf's talk.

Yuri Matiyasevich talked about number theory, which was yet another of Turing's many fields of work. Turing wrote a few papers in number theory, looking at the Riemann hypothesis. During telling us about the Riemann hypothesis, Matiyasevich told us about Skewes number, "the largest number that served any definite purpose in mathematics" according to Hardy, which was a massive lower bound of 10^10^10^34. In 1939, Turing applied for a grant from the Royal Society for just £40 to calculate information about zeros in the Riemann zeta function. This rather small amount of money was to buy parts in order to adapt some machines for predicting tides to the purpose he had in mind. Matiyasevich showed a picture of a tide prediction machine, and it instantly gives an impression of the "technology" that Turing was working with at the time. Apparently, Turing was fine with the fact that his machine gave its output in base 32, stating that he was "sufficiently familiar" with reading numbers in this form that it wasn't a problem. See Yuri Matiyasevich's talk.

David Ferrucci is the main man behind the Watson system that beat humans at the American quiz game 'Jeopardy' talked about the creation of Watson. Although Jeopardy isn't a Turing test, it is a test of general knowledge, and in this case a machine was competing against humans. His team of about 20 people put together many components (parsers, entity and relation extraction, knowledge base and search techniques etc) and then tested the system as a whole as the primary metric, not any one component. Initially it took 2 hours to answer a question, and some serious parallelisation of tasks was needed to make it fast enough for the game show. He gave lots of examples of questions and answers in his talk, including a question that asked for the common theme between "shirt", "telephone" and "TV remote control", to which the answer was "buttons", though "made with petrochemicals" and "made by humans" were also valid answers suggested by Watson. See David Ferrucci's talk.

Fred Brooks talked about Turing's Pilot ACE, a prototype of the ACE computer that Turing designed and wanted to build. Why did Turing's computer not take off? He suggested 3 main reasons: that he didn't publish his 1945 proposal, the machine was too late by the time it finally got built, and he didn't make it easy to program (didn't foresee how important that would be). Again we get the impression of Turing's amazing ability with numbers. Using backwards binary with the lower order bits on the left was no problem to him, but was not so easy for others. ACE also had other peculiarities: no accumulator, no general multiply, no straightforward conditional branch. Brooks recommended a new book by Simon Lavington, "Alan Turing and his contemporaries: Building the world's first computer", and he recommended everyone read von Neumann's EDVAC report on a much more practical machine. You can now see the Pilot ACE in the Science Museum in London. See Fred Brooks' talk.

The conference even after day 1 was already giving a wonderful picture of how diverse Turing's contributions to computer science and mathematics were, and how far reaching his ideas would be.

See also my writeup of Day 2 and Day 3 of the conference, and the online video recordings of the talks.

Day 2 of the Alan Turing Centenary Conference in Manchester

On the second day of the Turing Centenary Conference in Manchester there were more great talks. The screen showing the presentations was flanked by a large image of Alan Turing, reclining in a chair, reading a book. It was rather like having him present, listening to the talks.

Tony Hoare asked the question "Can computers understand their own programs?" and proceeded to propose to answer it with an alternative to the Turing test. In the same way that "Can a machine be intelligent" cannot be answered without a definition of "intelligent", Hoare's question cannot be answered without a definition of "understand". Instead, if a computer can answer questions posed to it about its own program, and give correct and useful answers, and explain its reasoning, then we may conclude that it understands its program. These questions might be, for example: "Will this change make the program run more slowly". He also finished his talk with a hint at his current work on algebras for programming, by asking whether programming will become part of recognised formal logic in the future. See Tony Hoare's talk.

Manuela Veloso is a robotics researcher who had 116 robots in her lab at a count in 2011. Her talk gave a tour of her work. This included planning and replanning in domains like robot football, purposeful perception (we only see/perceive what we need to deal with the task in hand, and if you arrive at an airport, you won't notice what colour the seats in the lounge are, because you're busy looking for a sign saying "Exit" or "Baggage"), robots that cohabit with humans and ask humans for help, and discussions about whether both robots and humans now use off-board AI. If Veloso and her robots had come to my school when I was young,  I'm sure I would have wanted to be a roboticist immediately. In one visit to a school, a 6-year old asked "Did the robots wonder why you picked them up?"

Donald Knuth gave a pre-dinner speech. This was actually just a short speech followed by question-and-answer session. He said that he was proud to be a geek and he believed that Alan Turing was 100% geek. He handled a wide variety of questions, such as "What advice would you give to a young researcher" (follow your muse), "Are your children and grandchildren programmers?" (my son is a maths teacher, my grandchildren are too young yet to know), "Are objects the same as co-routines (that question was from Bertrand Meyer, the creator of the Eiffel programming language, and the answer was an involved characterisation of their similarities and differences), "Whats your next book" (my life's work is the Art of Computer Programming, I'm working on the new volume, it's slow progress because I want it to be right).

During his short speech, Knuth said that he'd been on Friday before the conference to see the Alan Turing statue in Sackville Gardens, near Manchester Piccadilly. He'd sat there on the bench with Turing's statue, and he and Turing both sat there and thought for about 10 minutes, and he found it wonderful, and he recommended it to us all. When I left the conference on Monday lunchtime, I went via Turing's statue and did the same. The statue is life-size and feels strangely human, especially when you sit on the bench next to him. I'll never get to meet Turing, but I think that attending a 3 day conference all about his work, followed by sitting next to his life-size statue on a bench is probably the next best thing.

See also my writeup of Day 1 and Day 3 of the conference, and the online video recordings of the talks.

Day 3 and thoughts on the Alan Turing Centenary Conference in Manchester

On day 3 of the Alan Turing Centenary Conference in Manchester I had to leave after lunch and so I missed the afternoon sessions. However, the morning session was excellent.

Garry Kasparov: The world chess champion took us through the story of Turing's world-first chess playing program. Turing didn't have a computer to execute the algorithm, so he carried out the calculations by hand, taking 15 minutes to execute a move. Turing's algorithm was pitted against humans, and one of the matches was transcribed. Kasparov and colleagues collected the rules of Turing's chess playing program and implemented it. When they tried to reproduce the game, the results deviated from the game transcription 10 times. Presumably, Turing got bored in his hand-calulations, assumed what the answer would be, and just moved the piece. Live at the conference, Gary Kasparov played a game of chess against the implementation of Turing's program, and Kasparov very quickly won in 16 moves, with a commentary as he did so (pointing out moves that were "not the greatest choice!"). See Gary Kasparov's talk.

Rodney Brooks: The roboticist talked about Turing's unpublished 1948 paper "Intelligent Machinery", which discussed embodied robots. They were impractical in Turing's lifetime. In this paper Turing also says that machines that never make a mistakes could not be intelligent, that humans are not machines because they seem to be able to do mathematics despite Godel's famous theorem, and discusses the role of neurons and brains and their resemblance to a universal machine. Brooks showed how the field of robotics had benefitted from the exponential laws about processor speed and availability of sensors, and now there are many things we can do in robotics that Turing would not have thought possible back in 1948. In fact many things that look intelligent when humans do them, turn out to be the result of relatively simple laws, and his group's research can make robots look human-like just by taking care of how they move their gaze to track an object, or how they use prosody and movement to look as if they have emotions. See Rodney Brooks' talk.

Throughout this conference we were reminded of the huge range of topics that Turing worked on in his lifetime, and that this conference covered:
  • The Turing test (or "Imitation game") was repeatedly mentioned in several contexts by several people, including for its primary use - a discussion of whether AI is achievable and how we will know when we've made it.
  • Michael Rabin reminded us of Turing's contribution to decidability, the halting problem and computability
  • Edmund Clarke reminded us that Turing was the first to realise that software verification would be important.
  • Yuri Matiyasevich reminded us of the work Turing did in number theory and that his work is still used in computing zeros for the Reimann zeta function.
  • Adi Shamir reminded us of Turing's work in encryption.
  • Fred Brooks reminded us of Turing's efforts to create early computers (and his Turing machine) and his thoughts about whether intelligent machines were possible.
  • Leslie Valiant and others pointed out that Turing had categorised 3 types of search: intellectual search (search algorithms taught now in all AI courses), genetical search (genetic algorithms, evolution) and cultural search (gaining knowledge as a community by interaction).
  • Garry Kasparov reminded us that Turing made the first automatic chess playing program.
  • Rodney Brooks told us that Turing wrote about the possibilities and problems for embodied robots long before they could be built.
  • Hans Meinhardt told us about Turing's work in understanding the formation of biological structure.
Happy Birthday Alan Turing! Where will computer science be in another 100 years?

See also my writeup of Day 1 and Day 2 of the conference, and the online video recordings of the talks.

Wednesday 6 June 2012

Alan Turing, the first bioinformatician

This is the Alan Turing centenary year, and Alan Turing would have been 100 years old this month (on 23rd June) if he had lived this long. As well as inventing computers, theories of decidability, computability, computational cryptography and artificial intelligence, just before his death he also studied the relationship between mathematics and the shapes and structures found in biology. How do patterns in plants, such as the spiral packing of the seeds found in the head of a sunflower, come about? This year, in a big experiment, devised by Prof Jonathan Swinton to celebrate his centenary, sunflowers are being grown across the country. The seed heads will be collected, their patterns counted, then hopefully the results will demonstrate the relationship between Fibonacci numbers and biological growth that Turing was investigating. We're growing two sunflowers here in the Dept of Computer Science at Aberystwyth University as part of this experiment. Their names were voted on by the Department, and "one" and "zero" were chosen.

Turing used an early computer at Manchester (the Ferranti Mark 1, the first commercially available general purpose electronic computer) to model the chemical processes of reaction and diffusion, which could give rise to patterns such as spots and stripes. You can play with a Turing reaction-diffusion applet online, which shows how changes to the diffusion equation parameters produce different patterns. Turing wrote, near the end of his 1952 paper The Chemical Basis of Morphogenesis that:
"Most of an organism, most of the time, is developing from one pattern into another, rather than from homogeneity into a pattern. One would like to be able to follow this more general process mathematically also. The difficulties are, however, such that one cannot hope to have any embracing theory of such processes, beyond the statement of the equations. It might be possible, however, to treat a few particular cases in detail with the aid of a digital computer."

He then goes on to elaborate further on how computers have already been extremely useful to him in helping him to understand his models (no need to make so many simplifying assumptions). The fact that he actually used computers to investigate the models underlying biology, makes him the first bioinformatician / computational biologist. The fact that he could see the future, and could see how computers would enable us to model and explore the natural sciences makes him an amazingly visionary scientist.

Extra reading: