Photographer:Fotograaf: Joey Roberts/Simone Golob
Steven Kelk inspired by Bruno Courcelle
“It’s not just beautiful, it’s magical,” says Steven Kelk, assistant professor at the Department of Knowledge Engineering about Courcelle’s Theorem, proved by the French mathematician and computer scientist Bruno Courcelle.
For a layman to understand Courcelle’s Theorem, a bit of background information is necessary. “One of the main challenges in computer science is understanding which problems can be solved efficiently – by writing an appropriate computer program – and which can’t,” says Kelk. Courcelle’s Theorem helps with exactly that.
An important part of the theorem is the graph. “A graph is a fundamental structure in computer science. It’s basically a network of lines and points,” explains Kelk. “Around thirty years ago, we discovered that, for many difficult computational problems on graphs, the problem suddenly becomes easy if the graph looks like a tree. You can develop an efficient algorithm for it. Many people noticed this, it became rather repetitive.”
Courcelle decided to take the discovery to the next level. “He wrote a new metalanguage. Instead of developing an algorithm for every problem, you can describe what you want it to do in this special language, which is far easier. He completely eliminated the mechanical aspects of algorithm design. And in a way that is, to me as a mathematician, astonishingly beautiful. It blew my mind when I first saw it.”
Courcelle’s Theorem (1990) thus became the archetype of algorithmic ‘metatheorems’. “There is now a large research field in metatheorems. It’s a very attractive idea, it shortcuts designing computer programs.” But for Kelk the inspiration doesn’t come from these practical uses. It’s magical, he says and that’s important. “Life needs a bit of magic. I also find it in the wonderfully rich books of science fiction writer Gene Wolfe, who has produced some of the most sophisticated writing I’ve ever read. Or in the inspirational way Jeremy Corbyn, surprise front-runner in the contest for the leadership of the British Labour Party, is connecting with so many people across the country. He’s reminding people that there is no shame in imagining and demanding a better world, or writing a different story.” It’s what Kelk tries to teach his students. “Computer science is a young field. Courcelle is still working, as are many others who have found similar groundbreaking results. In my lectures, I talk about research from the 1970s. That might seem like two life-times ago for a student, but in an academic field it’s a second ago. I try to explain to them that these results are just the starting point. Computer science is an unfolding story and they are part of it. That’s pretty magical.”