Damir Dzhafarov is an Associate Professor 
of Mathematics at University of Connecticut. This Fall, Damir, together with his wife Veronica and their two children Zora and Nico, have spent three months in Prague, in the city of Damir's childhood. In the 1980s, while growing up in Prague with his Czech parents, Damir fell in love with computers, specifically with the model Commodore 64. Fast forward 40 years, today, Damir is exploring "New interactions of computability theory and combinatorics" at the Faculty of Mathematics and Physics of Charles University in Prague as a Fulbright Scholar. In his research, Damir is fascinated with the idea of pushing the border of what mathematicians have historically considered to be unsolvable. While Damir is eager to share the culture of his childhood and family roots with his wife and children, "...when it comes to academia, and doing research here, I feel almost as if I am in the Czech Republic for the first time," he says, highlighting the cultural and scientific enrichment of Fulbright exchanges.
When I was about five, my mom bought my older brother a Commodore 64 computer. Almost overnight, our living room was filled with the 8-bit sounds of games like Ghostbusters, Spy vs. Spy, and the Great Giana Sisters. Day after day, it was also filled with friends from our street, all eager to see the new computer and have a turn themselves.
My brother and I fell in love with computers and all they can do. In this, our experience was probably similar to that of lots of other kids in the early and mid 1980s. But it was different in at least one way: we were living in Prague, then still part of Communist Czechoslovakia. Getting a home computer was no small feat, certainly nowhere near as simple as walking down to the local Radio Shack. And while we were just kids, mostly oblivious to the political reality around us, I imagine our recollections of spending time on that Commodore 64 are somewhat unique.
My brother and I fell in love with computers and all they can do. In this, our experience was probably similar to that of lots of other kids in the early and mid 1980s. But it was different in at least one way: we were living in Prague, then still part of Communist Czechoslovakia. Getting a home computer was no small feat, certainly nowhere near as simple as walking down to the local Radio Shack. And while we were just kids, mostly oblivious to the political reality around us, I imagine our recollections of spending time on that Commodore 64 are somewhat unique.
For my part, I remember listening to the jingle of Radio Free Europe in the mornings, as my brother squeezed in a quick game before school. I remember passing pioneers in red scarves as I walked home with friends and discussed ideas for making games of our own someday. And I remember, in November of 1989, my mom explaining why we had to turn the computer off, and keep the TV on, because there were more important things happening.
Shortly after the events of the Velvet Revolution, our family emigrated to the United States, and I brought along my fascination with computers. Eventually I came to do research in a field focusing on computers—not just on what they can do, but on what they cannot.
Computability theory is an area of mathematical logic, at the interface of mathematics and computer science. The subject was founded by Alan Turing, in his groundbreaking work in the 1930s on formalizing models of computation. Turing’s concept—what we today call a universal Turing machine—is an idealized computer, one that, if we ignore limitations of memory, power, etc., is able to model any other computing machine, from the little Commodore 64 of my childhood, to the most powerful supercomputer of today. So if something cannot be done by a Turing machine, it can’t be done by any computer—of today or of the future.
That may be a surprising concept. We tend to think of computers as omnipotent—at least, eventually. Almost daily, it seems, we hear of yet another amazing feat of modern computing—from driving a car to playing Go, or recognizing a specific person in a photo. But there are problems that computers just can’t solve, and never will be able to solve, no matter how fast or smart or sophisticated. This was first shown by Turing himself, when he solved a famous mathematical problem called the Entscheidungsproblem (decision problem).
Let me illustrate this in a fittingly retro way. Say you’re playing a game on a Commodore 64, making progress through levels, when all of a sudden, everything freezes up. (It happened often enough!) You’re faced with two choices. One is to cut your losses: restart the computer, reload the game, and start over. The other is to wait it out: hopefully the computer is stuck only temporarily, and if you’re patient, you will eventually be able to resume your game. Obviously, there’s some cost-benefit analysis to do here. First, how long do you wait before deciding? And more importantly, should you even bother waiting at all? (Will the computer eventually get going again or not?) The Entscheidungsproblem, formulated in 1928 by the mathematician David Hilbert, asked—not quite in these terms!—whether a computer program can decide for you. So rather than agonizing over what to do, you just boot up this magical program, tell it what’s happening, and let it tell you, “Yes, wait it out”, or, “No, your game needs to be restarted”. And Turing showed, in his seminal paper in 1937, that no such computer program can exist. Not on a Commodore 64, not on any computer. The decision problem is what we call unsolvable.
Over the decades, researchers in computability theory have identified many other examples of unsolvable problems in the above sense. They have also developed many other (finer) measures for studying problems. A problem can be solvable or unsolvable, but some unsolvable problems can be “more solvable” than others. Understanding why this happens—what subtle reasons are responsible for one kind of problem being amenable to being solved algorithmically, by a computer, and another not—is incredibly fascinating.
It is a wonderful opportunity to have a chance to work on this research in Prague this fall, as a Fulbright US Scholar. The Department of Theoretical Computer Science and Mathematical Logic at Charles University, where I’m based, has strong groups working in several different areas of computability—some close to my own, some very different. I’ve learned a lot from my local colleagues, and still feel like I’m just getting started. We have some projects underway, and will likely continue our collaborations well into the future. Professionally, it has certainly been a very fulfilling and fruitful time.
On a personal level, it has of course been very gratifying. To work on computer science, in the city where I fell in love with computers, is pretty special. So is being a member of such a distinguished Department—one which is all the more remarkable for having only been formed in the past thirty years, since the fall of Communism. (Quite the leap from the days when it was hard to find a Commodore 64….) And to be here with my wife, Veronica, and our two kids, Zora and Nico—all of whom are learning to speak Czech, some better than others—makes it an experience I will certainly treasure for the rest of my life.
My experience is also a bit unusual. I was born in Prague, lived here as a kid, and have been back regularly since emigrating. But virtually all my education, and all my professional development and academic career, have been abroad. And so when it comes to academia, and doing research here, I feel almost as if I am in the Czech Republic for the first time. That’s a weird feeling. But cultural exchanges are as central to the Fulbright Program as the scientific, and for me, they have come in the form of insights into how things are done differently at Czech universities, and how, in some aspects, they are done better.
A good example is my Department’s annual retreat, which took place in September of this year in the beautiful foothills of the Vltava just south of Prague. There, meals were shared, new students and faculty introduced, and plans for the coming year announced. Some members of the Department also gave informal talks about their experiences over the past year, both professional and personal—a few presented recent research results, one faculty member showed photos from his travels through US national parks during his sabbatical. It was a great way to get to know people, and I assume for the regular members of the Department, a good bonding experience. I’m used to something similar happening at conferences, but never at any department I have been a part of in the US. Having more opportunities for members of a department just to chat, to tell each other what they’ve been up to, seems healthy, and something I’d like to see more of at home.
Actually, cultural exchanges between the Czech Republic and the US have been a part of my life forever. My dad, a political dissenter, was forced to emigrate when I was a toddler, and my mom, brother, and I didn’t see him again for many years. In that time, he’d send us tapes, talking about the US, about freedom and democracy (and sometimes, even about computers). These ideas filled our imaginations, and let us picture exciting new possibilities. Since then, of course, the Czech Republic has adopted these ideas for itself, in no small part because of the US. And yet, the US also shows us that the importance of these ideas—these ideals—can at times be forgotten. Hopefully, by keeping the exchange of ideas going—among other ways, through the Fulbright Program—the Czech Republic and the US can keep reminding each other.
Thinking ahead, I suspect I’ll look back on my Fulbright with great fondness. It is an exciting time to do research in my area, and Prague is an exciting place to do it. And for my wife, kids, and me, it has been an incredible place to live. We do miss some things about home, though—chiefly our dog, Lola. And I miss my Commodore 64….
