So could you tell me about a project you've worked on? >> Sure, so my background is in theory. And so I'll tell you a project that I worked on about the bounds of computation. And so what I really like to think about is, how far can we push computers and where are the limitations? And this goes way back to before there were computers. There were still people trying to think about what it would be like if there were computers, and what would it mean to think about computation. And so Alan Turing, in the 1930s, devised this notion of a universal machine, a Turing Machine, that could, you may have seen the movie, the Imitation Game with Alan Turing. And so we have this notion of computers being able to perform computations. And this is kind of an abstract notion, it doesn't have to do with whether you're a Mac or a PC or Operating Systems or anything to do with a nitty gritty hardware or software but just the notion of computation. And what's amazing about Turing's work is that you can actually distinguish between problems that are solvable by computers. And ones that can't ever be solved by any computer, no matter how clever we are it building that computer or how much time we give it, or how much memory we give it. They’re just some limits to computation. >> So they're completely unsolved, you could never solve these no matter what? >> No matter what, which I just think is crazy but, really interesting because there's some problems that are just so hard that computers can't access. And I actually think that's kind of cool because it means that we as human beings can think about them, but computers can't solve them. And so that's what I think about a lot. And then a very specific research project that I worked on based on this notion of computability, is trying to understand how we can recover some computability, some algorithms for solving problems if maybe we restrict the resources that we give our computers. And so we can say, let's not go hog wild and give our computers as much time as they want to solve the problems and as much memory as they want, but say, what about if we have a model of computation that's much simpler? And so this is called a deterministic finite automaton or a DFA. I don't know, have you heard of finite automata before? >> I have a bit, yeah. >> Okay, so a way I like to think about automata are as smaller computers. So the functionality of the automata is somewhat similar to a full blown computer, but it just doesn't have as many resources. It doesn't have much memory to work with. And it's gotta make decisions on the fly. It can't really store a lot of information. And it can't defer decisions. So- >> Do you quantify those amounts? Do you narrow the scope? >> Absolutely, so, all of this can be made very precise and very mathematical. But the cool thing about the research project that I'll tell you about is that you can see sort of the heart of the question without getting into all of those details. And then afterwards we can go back to them because they're really cool, too. >> Okay. >> But the idea is that when we restrict the computation power, then all of a sudden there's all sorts of questions that a computer would've been able to solve, but that these little machines, these automata, can't. And so there's particular questions that we can prove separate the class of computable objects, those that are answerable by computers, from those that are automatic, the ones that automata can handle. And so there's this very clear distinction between the automatic world and the computable world. And so then my work was to try to understand that interface, and in particular I was trying to understand the complexity of objects that live in the automatic world. So we know that these machines are weaker than computers. We know that there's sets and functions that automata just can't describe very well, that they can't do everything the computers can do. And so, is there a bound on the complexity of the objects that they can describe, because maybe we want to understand how much we've lost when we've taken away those resources from the computers, how much remains. And so we looked at a particular, and this was joint work with a couple of my colleagues, we looked at a particular measure of complexity called Scott rank, after Dana Scott, who's a computer scientist. And this measure of Scott rank tells us how complicated the objects that are being described are. And we know a lot about the Scott rank of computable structures and computable objects. And we know that the Scott rank can get pretty high up there. And so, we were thinking well, maybe the Scott rank of the automatic world is going to be bounded quite a bit lower than the computable world. Because they're so much smaller and weaker and you know these tiny little things. But the amazing thing was that we proved that you can find structures that are arbitrarily complicated in terms of Scott rank that have really, really, really high Scott rank but that are still automatic. And so even though this machines are like way smaller, and simpler and stupider than full blown computers, they can still code up objects that have arbitrarily high Scott rank, as high as any computable structure. >> That's really neat. >> It's so cool! And the key technical insight that we had to have was that we had to use really clever codings and representations of these really complex problems. So we had the really complex objects that had the high Scott rank and we had to do code them up in clever ways so that the automata could somehow still represent them. >> That's really neat. Thank you. >> Thank you.
