---
Video Title: Why Study Theory of Computation?
Description: Theory of Computation
2.1: Why Study Theory?

David Evans and Nathan Brunelle
University of Virginia
https://uvatoc.github.io
---

I want to follow up on the first class.

And you talked about why to study theory.

And I think this is a pretty good list.

I think this is a list mostly things the
class came up with.

And then after class Wednesday,
you filled in your registration surveys.

And we see the majority of
you are here totally under duress,

despite that really good
list of reasons to take theory.

So I feel like I should say a
little bit more, at least why I

think you should take this
class, even if you're not forced to.

For those of you who are forced to,
that I guess doesn't really have any

direct impact on what you do because
you're forced to take the class anyway.

But hopefully you'll at least see the
reasons why you're forced to take it.

And I will admit that when I was forced to
take a theory course, when I was both an

undergraduate and graduate in computer
science, I also only took it because I was

forced to and was very unhappy about being
forced to take a theory course.

Because most of us, at least many of us,
get into computing because we want to hack

code and build cool things and make stuff
on computers.

And the things that are done
in theory are sort of the reason

why we decided not to do math
and did computer science instead.

So I hope by the end of this class,
or actually, not by the end of the

semester, by somewhere during the
semester, if you're coming in from that

perspective, you will at least see more
value in actually learning theory.

So let me give you my
answer of why everyone

should take a theory
of computation course.

So the first answer to that is, this
is the way to think bigger and better.

By looking at problems from the
perspective of theory, by thinking about

things at the level of abstraction that we
think about things in a theory course,

you will be able to think
bigger and think better

and more ambitiously
about everything you do.

And I'll point to a recent talk that
Leslie Lamport did.

He's famous for the Paxosynchronization
protocol.

He's also responsible for the LaTeX
type-setting system that you will be using.

That's a useful practical contribution,
not the reason he won the Turing Award.

From the talk, he's talking about
mathematical thinking.

And he has a quote from someone talking
about TLA+, which was one of the tools he

developed to allow you to reason about
systems in a formal way.

And he's saying the real thing you should
say is that, you know, mathematical

thinking as a skill is the thing that he
found was most valuable.

And it both changed how he works and
changed how he thinks.

So I think thinking about things from the
theoretical perspective, even though most

of you will not become
theoreticians as your day job, is

something that should be very
valuable in how you think and work.

The second answer is very subjective,
but something that people who do work in

math and work in theory will say there's
intrinsic beauty in these things.

It's hard to convince
people that might not

see it as intrinsically
beautiful what that is.

But hopefully you'll
see some things in this

class that you will find
intrinsically beautiful.

One of those, which is
the pictures we won't talk

about today, but is in
chapter two of the book.

And we will talk about next week is that
the proof from Cantor using diagonalization.

And the third answer is a correlation
answer.

That there seems to be a really strong
impact in computing and a track record of

people who've done work in theory having
great impact and great success.

This is not necessary causality.

It's hard to know what causes success and
whether it's just a coincidence.

But if you look at many of the most
successful computer scientists,

as well as the most successful companies,
they grew out of people working in theory,

much more than out of
people working in systems,

relative to the number
of people working in age.

And I'll just mention one example.

So this is from a theoretical computer
science paper.

Does anyone recognize this definition?

Yeah.

So this is PageRank.

This is the paper that led to Google.

The start of it, it's all about a
definition.

It's not that they came up with some
better algorithm.

It's not that they came up with better
code or better system design.

What led to what I think is arguably the
most formidable and terrifying in many

ways, company in the history of mankind,
was a better definition.

There were some other
bumps along the way that

were necessary for Google
to get where it is now.

But it all started with coming up with a
better definition.

And definitely, both Sergey
Brin and Larry Page were

working in theory groups and
came from a theory background.

Sergey's degree was
actually math with computer

science, not a computer
science degree.

Hopefully those reasons will
at least make a case why this

is a required class, and
hopefully you will find value in it.