Steve Cook (EN, 2018-09-26)

The Digital Transformation is currently changing all aspects of our lives fundamentally. In this series I discuss with people about their personal experiences regarding this Digital Transformation.

This episode: Steve Cook, Turing Award Winner (“Nobel Price” for Informatics): 1982 for his contributions to complexity theory.

More about him:

The interview took place at the occasion of the Heidelberg Laureate Forum in September 2018. You can watch it online here:


Marc: Steve, it’s a great honour and pleasure having you here. Even though you’re very well-known, maybe some people need a quick reminder who you are. Could you briefly introduce yourself?

Steve Cook:  I am professor of computer science, emeritus at the University of Toronto. Actually, recently retired as of July 1st, so they’ve now finally turned off my salaries and they’re probably going to eventually kick my me out of my office.


Marc: Is that really happening?

Steve: Well, it hasn’t happened yet, and I know I’ll get some kind of office, but the Department is of course hiring new faculty like mad, since computer science is the big thing now. There will be more people and there’ll be a problem of rooms for office space.


Marc: In Germany the older professors still get emeriti, meaning that they still keep an office space and still get some money.

Steve: No, emeritus is just another word for retired. Actually, I have been officially emeritus for some time, but I had a contract. There was mandatory retirement when I turned 65, the law at the university was that you had to retire. There was no choice. So, I had a contract so I could stay for a limited period.


Marc: The topic of this series is “Being Human with Algorithms” and the focus is the digital transformation. Especially computer algorithms being part of more and more parts of the daily life, ranging from the product I hold in my hand, for instance, which is running algorithms.  Even this product here, algorithms were part of the production, either in the direct production or in the transportation. It’s impossible, I would say, to live without algorithms today in the big areas of life. This digital transformation, what does it mean to you?

Steve:  Personally, of course, it’s made quite an effect on me since computers. When I started off with my PhD thesis in 1966, we had very primitive computers, we didn’t even have Xerox machines. I typed, or actually I had the secretary type my thesis, and then they made carbon copies. Because they didn’t even have Xerox machines. Things have come a long way, absolutely. I do have a laptop, a computer, I have a cell phone, but I have to admit that I don’t use the cell phone very much. But I do use the laptop, I do use the desktop computers and of course they’re extremely useful.  I use them for email and that’s very important. I use them for going online and answering questions.


Marc: What would you say is the biggest difference to when you think back to 15 years ago? Is it the connectivity, that you are always online? Is it new forms of communication, like having chats, FaceTime, Skype and video conferencing?

Steve: I’m old enough, so I don’t tend to chat. I do have a cell phone, as I say, but I don’t really use it. My chatting is via email, so email certainly has had a big effect on me. I do like that, I do communicate. I’m a little hard of hearing, that’s part of the problem with the cell phone, but I can read emails. Of course, Google is extremely useful, because I frequently want to ask questions that I should know or want to know. Now, it’s easy, I just ask Google, and Google usually has the answers. I find that extremely useful.


Marc: Do you see a shift in people, now that knowledge is available literally at the fingertip? When you write something into Google, people are spending less time on reading like book with the background, or actually memorizing something. That it shifts from knowing something towards knowing how I can find something?

Steve: I think that is true to some extent. It is especially useful to me, with a fading memory. So, in my case, yes, absolutely. I if I forget something that I know, I can look it up. As far as reading goes, well, we still we still have textbooks. The courses I taught, at least one of them had a textbook, so I could assign problems reading from the textbook. A lot of the stuff was just online, because I made up my own notes and they were online. The computer was certainly playing a big role there. We still have books, though, and you still look them up occasionally and read.



Marc: How would you say did you personally shape this digital transformation?

Steve: As you know, I’m famous for introducing the idea of NP-completeness, which is the issue of certain problems seem to be difficult to solve. What’s very interesting, I don’t know that my work itself has changed how we actually use computers. It’s really kind of a negative concept to show something is NP-complete and it’s going to be a hard problem to solve. So, that would be the application: don’t spend a whole lot of time trying to solve the problem, probably it’s going be really difficult.


Marc: Speaking about the NP-hardness, is there an iconic example, especially for those who are not totally familiar with the concept, where you would say this is where my theory applies and where you have an actual connection to activities that you do.

Steve: The travelling salesman problem, I suppose, where you have a hundred cities. You know the distance between every pair of cities and the salesman has to travel to each city somehow. The question is what order you use to minimize the total distance. That problem is NP- hard. In practice you are probably not going to be able to find the order of shortest distance, but that isn’t that important, because there are algorithms for finding nearly the shortest distance.


Marc: Also, the real systems are typically finite.

Steve: They’re finite, but they could be big. They could be big enough so that it really is difficult to find the absolute shortest route. But you don’t really need to do that, you just need to find a reasonably short route. That’s just one example.


Marc: Could you say something about the relation of complexity theory and cryptography?

Steve: I mean cryptography certainly is much harder. Showing that things are possible or impossible cryptographically is harder than NP-completeness. But certainly, the idea of NP-completeness has influenced the theory of cryptography, no question.


Marc: When you think of this digital transformation, what would you say are the biggest challenges that we’re currently facing with the societal change?

Steve: I guess security is one obvious thing. Of course, we like to pay with credit cards online, but we worry about people finding out our credit card numbers. Security is certainly a serious issue there.


Marc: When think about the definition of the people as humans, moving towards a digital representation of their self.  When you think about children that are using their smartphone more often than going outside to play with other children on the street. Do you see that there’s an impact on society, either a negative or a positive one, of having such a shift in the habits?

Steve: It absolutely seems to be huge. It doesn’t affect me, I am too old, but you’re right, you see people walking down the street all the time just looking at their cell phone. I think you’re right; I mean instead of chatting with people physically, they just seem to be absorbed on their cell phones, which is a change. It seems not too good, dangerous, even, when you’re a pedestrian and not paying attention. Or even when driving a car, people are looking on their phone.


Marc: I don’t know if you noticed that, but at least in Germany there’s an interesting development because. At escalators, they started to have some signs on the ground that are a red or a green line. People don’t even have to look up from their smartphone, because when they look down, they already see if something is happening or not: With the subway in Munich it’s the same thing.

Steve:  So, they’re looking at their cell phone going down?


Marc: Yeah, so my reality is adopting to that, so that they can continue with their habit of just looking down, which is also very interesting to me.

Steve: I guess so. I haven’t thought of that. How people are probably too much involved with their cell phones. They should be talking directly to each other, I think.


Marc: To me, it’s also fascinating that it’s a very immersive experience, because you have this mobile phone as device that you use for communication, but you are not interacting with a program on the phone. Some are doing it, like playing games or something, but you also are talking to your friends.  You carry those that are significant to you with you and you are permanently connected.

Steve: That’s true, I guess you are being social in a sense. I don’t do it, so I can’t really say, but it doesn’t seem to be the same as talking to people face-to-face. Well, I guess now you can even see their expressions on the phone.


Marc: That’s right. What is interesting to me is that on the one hand it’s asynchronous: you write something and someone else can consume it whenever it fits. But at the same time, the expectations of answering fast are very high. It seems to dictate the rhythm of what people do, it’s shaking in your pocket and you have to check what happens. Then you have to answer quickly, because everybody else is also answering quickly. It’s similar to emails when you have the email notifications on. The email comes in and you immediately interrupt what you do, and you switch to the email, you answer it, and then you go back to your other task. Having lots of these context switches always is a challenge to me.

Steve: In my case, I do use email, but I don’t use it that way. I don’t feel I have to answer questions immediately. I just do it maybe a few times a day, okay now I’ll look at my 50 email messages and I just go through them. I don’t feel I have to answer them. I guess people know that and they’re not expecting.


Marc: It’s good that you did that, it’s also the thing I do whenever I get a new computer. The first thing I do is to disable the email notifications. So, it doesn’t disrupt me, but I can define when I want to look at.

Steve: Absolutely.


Marc: The thought that you just said, that there are these opportunities, but you still have to think about how we want to use the new technology. Wow much you want it to control you and not you controlling the technology. To me this is a key aspect of what we have today and also a big challenge, because there are lots of opportunities and people have to try to cope with these technological offers.

Steve: Yes, so I guess different people cope differently.


Marc: When we come from the from the challenges to the opportunities. What would you see as the most positive things? We were talking about connectivity already; this could be one answer. That you say it’s good to have this connectivity that is much faster with the email than with a letter, for instance. And also, a different form of communication, because you can play the ball back and forth faster.

Steve: That’s true. When I started out courses as a professor, then I wrote letters, actually, and then mailed them. You’re right, it takes much longer, of course, to get a communication that way. Now we can do it and at our own time, that’s true.


Marc: For you, is this the key aspect of the digital transformation? The positive one that you are personally taking benefit off.

Steve: I absolutely benefit. I will say that emails are extremely useful. I do like to make sure I go through them every day; I don’t want to let them wait too long. On the other hand, they won’t expect instant answers from me.


Marc: I think this is a really good relation to it. Coming to another aspect about this speed of technological advance. When you look back to the last 30 years, do you also have this impression that I have, that the pace of innovations and things that change your human being is increasing?

Steve: I guess that’s true, yes. I suppose the biggest change now is the threat of artificial intelligence. That’s a big deal now and in some ways a concern to us. Thinking about people who might worry about being put out of a job now ultimately.


Marc: How would you formulate the threat? Which are the relevant aspects of it?

Steve: I’m a mathematician and I’m trying to prove a theorem it’s expected that I might spend even years on working on it, but if we really have very smart artificial-intelligence computers, they might be able to do it really fast. Where does that put us as mathematicians? I mean here’s the issue: our brains are just elaborate computers, extremely elaborate. There’s going to come the time when we can build brains, and maybe better brains. There’s no reason why not. What do we do then?


Marc: When we go into that direction, what will happen with the personality? Is personality something that you would consider important? Because when we think about things such as making proofs, or theorems, or something like that, then personality might be a good tool, because it hints you in certain directions. But if you’re a fast computer and you can do brute force or somehow intelligent branching, then it will also find the solution. Because for me, personality is something that differentiates even the most intelligent machine from a human. For the machine it probably doesn’t make sense to give it too much personality, unless it’s about to interact with the human and you want to hide that it’s a machine.

Steve: I suppose you could ultimately put in personality, too, if you wanted, because I say that brains are just computers, so you just have to simulate the brain.


Marc: Would it make sense to put personality in?

Steve: I don’t know. It’s a concern what do people do then, even us mathematicians. What we do when the computers can solve problems better than we can? That’s worrisome. Right now, we may feel important and we’re really contributing to stuff. That could change, I guess. What good are people or what can we do to make ourselves happy? The only thing I can think of is competition. We can compete with each other like these athletes in sports, right? I mean when people run the hundred-meter dash, of course, there are all kinds of things that can go faster, but you don’t care. It’s about what can people can do, right? So, in mathematics maybe we just have our own puzzles and competitions. I don’t know, what else is there?


Marc: This is a very interesting aspect that we came up to. In the panel discussion that we had on Friday, Katharine Jarmul, a blogger, she said that when you have these algorithms and machines taking over jobs, then one thing you could do is to give people unconditional income and they don’t have to work. I mean you could do that, but the aspect that you were also mentioning, and which the two were also talking about, is dignity. Dignity as a human, that you feel more worth when you have something useful to do.

Steve: Yes, absolutely. That’s very important. If you are doing something useful, that makes you feel good. So, how do we manage that?


Marc: We’re already coming to the end. What do you connect with the motto “Being Human with Algorithms”? What does this slogan tell you, what does it mean to you?

Steve: Humans are our algorithms. I’m not sure what to say here. We have to find a new way of being happy and feeling good. The only way I can think of offhand is we can’t cheat and use computers; we have to use ourselves only.  I don’t know what else. It hasn’t quite happened yet, so I haven’t thought this through carefully there, but it’s a looming problem.


Marc: If you allow me to ask even another question: Algorithms are something that exists since humankind or at least for a very long time, when you see at as a rule for doing something. What is your current definition of what an algorithm is?

Steve: What to do, how to solve this problem of what people can do? I don’t know.


Marc: No, I mean when you want to explain someone what an algorithm is? What would be your definition?

Steve: Oh, what definition. An algorithm is just a set of rules to solve a problem, I suppose.


Marc: The reason why I asked the question is that in the discussion in the media the term algorithm often seems to be negatively connotated today. Because it’s going into the direction of artificial intelligence, something like this HAL in Odyssey 2001, some super intelligent power that wants to take the humans out of earth and rule the earth instead. Indeed, algorithm in itself is not negatively connotated.

Steve: The fact is that our brains are using algorithms, we’re all using algorithms. Maybe you’re right and it has somehow come to “If you’re using creativity, you’re not using algorithms”. Well, even that isn’t clear.


Marc: Peter Weibel was one of our people in the symposium he’s the director of the “Zentrum für Kunst und Medien”, so centre of art in Karlsruhe.

Steve: Art and …?


Marc: Art and video installations and media. He was citing, I guess it was Newton who said, that the book of nature is written in the language of mathematics. Do you have a thought about this? Was there math first or nature first?

Steve: I don’t know. What is this book?


Marc: It’s just a quote that is said to be Newtons. It means that when you have processes in nature, you can describe them with mathematical rules. It is like the hen-and-egg problem: Is mathematics the universal rule of the universe, so that you the processes can be described in a mathematical way and then the nature follows these rules? Or is mathematics more the human brain understanding processes in a way that can be very well described with mathematical rules, so for us humans it’s a good tool to describe the perception and the processes that we are able to perceive.

Steve: As I say, I think our brains are all just following algorithms. We can’t dodge them. Whatever we do we’re going to follow some kind of algorithms, maybe very sophisticated algorithms.


Marc: Would you say that this is something only humans do? Or do animals also follow algorithms?

Steve: I guess they do. Their brains control what they do. So they are, yes, absolutely.


Marc: I think we have very nice insights and I thank you very much. That was very interesting. This math-nature thing is always puzzling me. Is the math something that correlates with our perception? Are mathematical rules something that we can very well use as humans because it’s something that is connected to our perception? And, as we can only perceive a certain part of the reality, math is a good tool to describe this part of the reality. Or is it something more universal that is only to be discovered by humans? This would have also been an interesting question.

Steve: I guess there are a couple things. One is physics, the laws of physics. Presumably they can be expressed mathematically, that’s what people think and actually with quite a bit of success so far. That’s one thing. And of course, it’s huge mystery where all these physical laws came from. That’s another fascinating point. I think the physical universe is following algorithms. Maybe probabilistic algorithms, I don’t know. But that’s okay, that is a kind of algorithm.


Marc: Is math something that was developed or discovered by humans?

Steve: Well for the universe, presumably, it was all just made somehow. We don’t know how explain that.


Marc: But then it would be more discovery. The math is there, and the humans have to discover it.

Steve: That’s right, we don’t invent the laws of physics.


Marc: That’s, at least hopefully, certain.  So that the models won’t break down one day. Pleasure, thank you very much.

Steve: You’re welcome.

Marc-Oliver Pahl founded "Being Human with Algorithms / Mensch Sein mit Algorithmen" in 2018 within the German Chapter of the ACM together with Gerhard Schimpf, Ruth Stubenvoll, Ernst-Oliver Wilhelm, and Eberhard Schmolz. He is also the originator of the motto and the logo. Marc-Oliver is Research Director at the Institut Mines Telecom (IMT) Atlantique in Rennes, France. He also heads the IoT Smart Space Orchestration team at Technical University of Munich (TUM), Germany. His research is on enabling an open, secure, and fully connected Internet of Things, where everybody can contribute software programs that literally change the world. Fostering a dialog between technology leaders and the rest of the society is a central goal of Marc-Oliver. Besides this website, a major contribution in this direction is his interview series with relevant people about aspects of the Digital Transformation. Marc-Oliver holds several teaching prices including the Ernst Otto Fischer prize for excellence in teaching. He is responsible for the Massive Open Online Course (MOOC) "iLabX - The Internet Masterclass" ( on edX. It teaches the technical aspects of the backbone of the Digital Transformation: the Internet. Marc-Oliver is a long time member of is a professional member of the Association for Computing Machinery (ACM), the Institute of Electrical and Electronics Engineers (IEEE), the German Society for Informatics (GI), the Deutscher Hochschullehrerverband (DHV), the German Chapter of the ACM, and Faculty Sponsor of the ACM Student Chapter in Munich. He is vice president of the German Chapter of the ACM (2020-2023). In his spare time he is also a photographer, designer, musician, and enthusiastic sportsman.

Leave a Reply

Your email address will not be published. Required fields are marked *

WP2Social Auto Publish Powered By :