• Managing your videos in Amara teams just got easier! Read about it in our latest blog post. Hide

## ← 01-06 Computability Or Complexity Theory Solution

• 2 Followers
• 21 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=bsmEKaOE0Ns" data-team="udacity"></div> ``` 1 Language

Showing Revision 2 created 02/06/2019 by Michel Smits.

1. And, of course, there's going to be
more challenging quizzes here,
2. but for a warmup I think it is very good
to understand the difference
3. between computability
and complexity theory.
4. The first question, how fast a computer
can find a way between 2 points on a map,
5. belongs in complexity theory because
here it's a question of resources.
6. So "how fast," that is a question about
the time that a computer needs,
7. and therefore, investigating this question
belongs in complexity theory.
8. Asking if a program can decide
if another program is malware,
9. that belongs in computability
we're just if it's possible in principle.
11. We're asking, "Can a program do that?"
12. We're not asking how fast or
with how much memory it can do that.
13. In the third question we are,
and therefore, this 1 belongs in complexity theory.
15. The question about memory is something
we are not going to look at much in this course.
16. Actually, I think we are not
going to look at it at all.
17. We're going to be
concerned mostly with time,
18. how fast a computer can
solve a given problem,
19. and, toward the end of this unit,
20. we are going to pose
the ultimate resource question
21. and ask, "What are the limits
of computation in general?