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.

Sample Pitch, Non-Technical

Mastering the Software Engineering Interview

Meet the Instructors