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

## ← 20-27 Undecidability

• 1 Follower
• 16 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=jQmLypSDoE8" data-team="udacity"></div> ``` 1 Language

Showing Revision 1 created 10/03/2012 by Amara Bot.

1. Okay, so now you might be thinking--well, okay, so programs can become so complicated
2. that no algorithm can decide whether they run infinitely or not.
3. So is there a short program for which I could show you undecidability.
4. Oh yes, there is such as a program--it's not very practical but it is an example
5. for undecidability for very simple program.
6. Here's a simple example of a problem that is actually
7. not decidable, although it's very simple to write.
8. So the input to that problem is an integer and we will just call that integer i
9. and the output is the number of iterations that it takes to get to i=1 using the following two rules--
10. If i is even, then set i to i/2 so they divide by 2. If i is odd, set i to 3i+1, just two simple rules.
11. And so for example when you start out with i being 10, then we first apply the first rule.
12. We get down to 5, 5 is odd so the new value is 16 and then we divide by 2, we divide by 2,
13. we divide by 2, we divide by 2, so we have 1, 2, 3, 4, 5, 6 iterations.
14. So i=10, then the answer is 6.
15. So now we're going to let you play a little bit with this algorithm
16. and then discuss the undecidability for it.