Přeskočit na hlavní obsah

Damir Dzhafarov: Computing in Prague

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.

Photo 2: Damir (right) and his brother when growing up in the Czech Republic, family archive. (Two boys pose together for a picture.)
 
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.

Photo 3: A group picture of U.S. Fulbright scholars and students during the orientation meeting in Prague, September 2021. (Almost three dozens of U.S. grantees and their family members pose together for a picture in front of Vila Lanna in Prague.) 
 
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….

Photo 4: Damir, his wife Veronica and their two children Zora and Nico, September 2021, Prague. (A family portrait, all dressed formally.)

Populární příspěvky z tohoto blogu

Czech Prom Season: A Story of a Feathered Raffle Win

Authors: Griffin Trau, Katie Winner, Alanna Powers (current Fulbright ETAs) If you’re an American, chances are we all had similar prom experiences in high school. Usually a few weeks before graduation, boys ask girls to the prom. Girls buy a fancy dress, and boys a nice suit with a matching tie. Prom night consists of about an hour of picture taking with your date and friend group, followed by a ride to prom in a nice car or a limo. The dance itself is about three hours long, and the only people in attendance are typically students at the school with a handful of teacher chaperones. After prom ends, around 10 or 11 p.m., all the students leave and go their separate ways for the night, usually to a post-prom hang out. After attending six (and counting!) Czech proms, I can confidently state that Czech proms are nothing like American proms. At all. My school, Střední Škola Informatiky a Služeb, is a technical school with seven different concentrations of study. Of these seven, s

Pranav Kakulamarri: Say Less

Pranav Kakulamarri is an English Teaching Assistant. He currently teaches English at Gymnázium Tišnov. His host town of 10 000 is located 22 kilometers north-east of Brno. In August 2022, Pranav arrived in the Czech Republic with a BS in Neuroscience from the University of Alabama at Birmingham, a life-long passion for chess and a future plan to become a physician after his 10-month adventure in the Czech Republic. With experience as a chess instructor, a reading tutor and a researcher, he had some pedagogy skills, but no prior classroom experience. Today, Pranav is the Tišnov celebrity - he was featured in the town's paper, people greet him in the streets and strangers initiate conversations with him on train or bus, starting with: "I know you, you were in the town's paper." What is Pranav's magic? Natural charisma, positive attitude, disarming smile, and his ability to listen to others. “What is happiness and how does it differ within a culture? Why does one liv

Katherine Pérez Rivera: Beyond science - collaboration, engagement, and identity

Katherine X. Pérez Rivera is an environmental scientist. She came to the Czech Republic in September 2021 to study carbon dynamics in Czech streams impacted by acid rain. Katherine's host institution was the Czech Geological Survey located in Prague, but she spent many days and nights collecting samples and data in the Slavkov Forest, a sparsely inhabited protected landscape area, located in Karlovy Vary Region, famous for its spa towns. During her year-long Fulbright adventure, Katherine had to conduct fieldwork during the winter for the first time in her life. As someone born and raised in Puerto Rico, adjusting to Czech winter temperatures, hiking in a deserted forest covered by snow and wearing snowshoes was a life-changing experience. "Becoming a Fulbrighter permitted me to connect with others beyond my science and field of study. These connections were rooted in the core of our identities, who we are and what matters to us," reflects Katherine when adjusting back to