1 00:00:06,080 --> 00:00:10,560 In the last video, we drew some pretty pictures of triangles and squares. 2 00:00:12,020 --> 00:00:14,940 In this video we're going to, look at some pretty pictures too. 3 00:00:14,940 --> 00:00:17,960 We're actually what we're going to do is we're going to look at some of the math 4 00:00:17,960 --> 00:00:20,000 or, or very simple function. It's not math. 5 00:00:20,000 --> 00:00:23,410 It's a very simple function. Behind a pretty picture. 6 00:00:23,410 --> 00:00:28,890 There's this thing called the [INAUDIBLE] conjecture, and it's about a sequence of 7 00:00:28,890 --> 00:00:33,410 numbers that work like this; if the current number is even, then the next 8 00:00:33,410 --> 00:00:41,008 number is n over two, if the current number is odd, then the next number is 3n 9 00:00:41,008 --> 00:00:46,110 plus one. And what I've done here is, using the 10 00:00:46,110 --> 00:00:52,700 recipe for generative recursion, I've designed a ISL function for hailstones. 11 00:00:52,700 --> 00:00:55,130 That's what this sequence is historically called. 12 00:00:56,410 --> 00:00:59,700 Which basically says, look, when we get to one, we stop. 13 00:00:59,700 --> 00:01:08,350 So if n is 1, we produce the list 1. Otherwise, we cons n onto the next call, 14 00:01:08,350 --> 00:01:14,080 which is if n is even, we call ourselves recursively with n over 2. 15 00:01:14,080 --> 00:01:19,938 And if n is not even, in other words, if n is odd, we call ourselves recursively 16 00:01:19,938 --> 00:01:25,000 with plus 1 and n times 3, which is exactly this rule up here. 17 00:01:25,000 --> 00:01:31,080 So there's hailstones, and the reason it's called hailstones is that if you 18 00:01:31,080 --> 00:01:37,065 compute the sequence for very, for a number of values, I'll just do it for 10 19 00:01:37,065 --> 00:01:42,520 now... Now if you compute the sequence for a 20 00:01:42,520 --> 00:01:45,610 number of different starting values and then you measure the length of the 21 00:01:45,610 --> 00:01:50,578 sequence and you plot that, you get a picture kind of like that. 22 00:01:50,578 --> 00:01:57,092 Let's talk about something else for a second. 23 00:01:57,092 --> 00:02:03,740 Look at Hailstones. Hailstones is a recursive function that 24 00:02:03,740 --> 00:02:10,870 calls itself with either n divided by 2 or n times 3 plus 1. 25 00:02:10,870 --> 00:02:16,120 Let's compare Hailstones to the Sierpinski's Triangle function. 26 00:02:16,120 --> 00:02:20,410 As tried, the Sierpinski Triangle function Is a recursive function that 27 00:02:20,410 --> 00:02:27,910 calls itself recursively, with s over 2. Now if you think back a bit, when you 28 00:02:27,910 --> 00:02:32,840 first saw recursive functions, I think you probably got a bit concerned. 29 00:02:32,840 --> 00:02:35,850 Hey is this ever going to stop? This function is calling itself. 30 00:02:35,850 --> 00:02:39,840 Why will it stop? And then I convinced you not to worry 31 00:02:39,840 --> 00:02:43,100 about that. Because we've talked about the notion of 32 00:02:43,100 --> 00:02:47,745 a well-formed self-referential type comment, it had a base case and a 33 00:02:47,745 --> 00:02:54,800 self-reference case and having resistance of the base case meant that recursive 34 00:02:54,800 --> 00:02:58,230 functions operating on this kind of data would always stop. 35 00:02:59,550 --> 00:03:02,840 And the reason they would always stop is that if it wasn't the base case, they 36 00:03:02,840 --> 00:03:04,956 were going to take a subpiece of the current data. 37 00:03:04,956 --> 00:03:10,650 And by taking subpieces of the current data, in the case of lists, by taking the 38 00:03:10,650 --> 00:03:15,760 rest of the list each time, they would eventually reach the base case, again, in 39 00:03:15,760 --> 00:03:19,460 the case of lists emptied. And so that's why we were happy with 40 00:03:19,460 --> 00:03:21,560 those recursive functions and we knew they would stop. 41 00:03:23,210 --> 00:03:27,240 What about these recursive functions? They're not operating on a well formed 42 00:03:27,240 --> 00:03:31,750 self referential data definition. So that previous proof that they would 43 00:03:31,750 --> 00:03:37,020 stop doesn't apply anymore. What we need for these functions is a 44 00:03:37,020 --> 00:03:41,014 three part termination argument. Let me show you what I mean. 45 00:03:41,014 --> 00:03:47,210 I'm still in termination starter. And the problem here is to do a three 46 00:03:47,210 --> 00:03:52,070 part termination for s-try. Okay? 47 00:03:52,070 --> 00:03:56,493 Now what I'm going to do actually is I'm going to pick this up. 48 00:03:58,590 --> 00:04:02,220 And take it over to fractals view one I want to put the termination argument 49 00:04:02,220 --> 00:04:09,312 right there. We'll paste it in right here to fractals 50 00:04:09,312 --> 00:04:13,620 v one and. I'll get rid of just the description of 51 00:04:13,620 --> 00:04:15,860 it. I'll pull just that part. 52 00:04:15,860 --> 00:04:20,980 So now, this is going to be the three-part termination argument. 53 00:04:20,980 --> 00:04:26,472 The first part of a termination argument is the base case: When does the function 54 00:04:26,472 --> 00:04:30,331 stop? You can usually pick these right out of 55 00:04:30,331 --> 00:04:35,540 Of the definition of the function. It stops there. 56 00:04:35,540 --> 00:04:41,010 The next part of the argument is the reduction step. 57 00:04:41,010 --> 00:04:45,100 What is the argument to the function in the recursive call? 58 00:04:45,100 --> 00:04:47,860 What is the thing which the template calls the next problem? 59 00:04:49,270 --> 00:04:53,500 Well, again, that's usually pretty easy to pick out of the function definition. 60 00:04:53,500 --> 00:04:57,967 In this case, it's S over two. And then there's the argument that 61 00:04:57,967 --> 00:05:04,025 repeated application of the reduction step will eventually reach the base case. 62 00:05:04,025 --> 00:05:09,280 What that means is that if I start with a legal s [INAUDIBLE] and I keep doing the 63 00:05:09,280 --> 00:05:12,470 reduction step over and over again, I will get to the cutoff. 64 00:05:13,660 --> 00:05:20,030 And in this case that's fairly straight forward, as long as the cutoff is greater 65 00:05:20,030 --> 00:05:27,872 than 0, and S starts greater than or equal to 0. 66 00:05:27,872 --> 00:05:43,400 Repeated division by 2 will eventually be less than the cutoff. 67 00:05:43,400 --> 00:05:45,450 I promised we wouldn't do much math in this course. 68 00:05:45,450 --> 00:05:49,610 I'm still keeping my promise but I'm getting a little bit close to it. 69 00:05:49,610 --> 00:05:53,870 But, I think that even people who don't love math will agree that if you keep 70 00:05:53,870 --> 00:05:59,430 dividing a number by two over and over and over again, that number is eventually 71 00:05:59,430 --> 00:06:02,950 going to get right up to an approaching zero. 72 00:06:04,100 --> 00:06:07,240 And so, as long as the cut off is bigger than zero you'll eventually get to be 73 00:06:07,240 --> 00:06:11,490 less than the cutoff. The point of the three part termination 74 00:06:11,490 --> 00:06:14,920 argument isn't to talk about how fast you're going to get there, it's just to 75 00:06:14,920 --> 00:06:19,820 prove that you will eventually get there. So with these three part termination 76 00:06:19,820 --> 00:06:26,190 argument, which you should always include when you use generative recursion, we now 77 00:06:26,190 --> 00:06:30,355 know that stri will stop. Let's do another one. 78 00:06:30,355 --> 00:06:39,730 And this one is so simple that you might find it too simple, but I want to do it 79 00:06:39,730 --> 00:06:42,723 because as soon as I do this one, then I'm going to do a trickier one. 80 00:06:42,723 --> 00:06:46,310 I'm going to go back to fractals v1, and I'm going to do the three part 81 00:06:46,310 --> 00:06:52,030 termination argument for the carpet. Okay? 82 00:06:52,030 --> 00:06:58,140 And in fact, what I want to do, Is let you do the three part termination 83 00:06:58,140 --> 00:07:02,990 argument for the carpet, okay? So there is the carpet. 84 00:07:02,990 --> 00:07:07,340 You want the base case, the reduction step, and the argument that repeated 85 00:07:07,340 --> 00:07:10,390 application of reduction step will eventually reach the base case. 86 00:07:11,990 --> 00:07:14,510 This is going to be almost exactly like the one we just did. 87 00:07:14,510 --> 00:07:16,482 I'm aware of that but please do it anyway. 88 00:07:16,482 --> 00:07:23,550 Okay, now here is my answer to the three part termination argument for the carpet. 89 00:07:23,550 --> 00:07:26,790 Base case is, again, is s less than cutoff. 90 00:07:28,010 --> 00:07:36,907 The reduction step is divide s by three, and the argument again is as long as 91 00:07:36,907 --> 00:07:47,470 cutoff is greater than zero, and s Starts greater than or equal to zero, repeated 92 00:07:47,470 --> 00:08:00,081 division by 3, will eventually reach base case. 93 00:08:02,139 --> 00:08:05,314 Great, there we go. That's two three-part termination 94 00:08:05,314 --> 00:08:07,050 arguments. Seems pretty easy, right? 95 00:08:07,050 --> 00:08:13,550 Let's go back over here to termination starter, and do the three-part 96 00:08:13,550 --> 00:08:20,930 termination argument for hailstones. What I'll do is I'll bring it up to right 97 00:08:20,930 --> 00:08:30,100 next to hailstones function. What's the three part termination 98 00:08:30,100 --> 00:08:38,010 argument for hailstones? Well let's see the base case is that n is 99 00:08:38,010 --> 00:08:43,748 one, and the reduction step is, what's the reduction step? 100 00:08:43,748 --> 00:08:48,540 Well it's right here, in this case I can't quite pull it directly out of the 101 00:08:48,540 --> 00:08:59,242 code, but it's if N is even, then N over 2. 102 00:08:59,242 --> 00:09:11,255 If N, if N is odd, then Plus one times n three. 103 00:09:11,255 --> 00:09:16,320 That's the reduction step so now we need to argue that the repeated application of 104 00:09:16,320 --> 00:09:18,750 reduction step will eventually reach the base case. 105 00:09:22,080 --> 00:09:29,250 Well. You know, this first line looks pretty 106 00:09:29,250 --> 00:09:32,055 good, n keeps getting smaller. And if I'm going to argue that n reaches 107 00:09:32,055 --> 00:09:35,515 1, n getting smaller all the time is good news. 108 00:09:35,515 --> 00:09:42,140 But on this next line, n gets bigger. It multiplies by 3 and adds 1. 109 00:09:42,140 --> 00:09:45,596 Hm, this could be hard. And in fact, this is hard. 110 00:09:45,596 --> 00:09:49,916 It's extremely hard. It's so extremely hard that the 111 00:09:49,916 --> 00:09:53,948 mathematicians haven't been able to prove it yet. 112 00:09:53,948 --> 00:09:59,900 And they've been trying for years. And that's despite the fact that no one 113 00:09:59,900 --> 00:10:03,730 has ever been able to find a counterexample. 114 00:10:03,730 --> 00:10:08,460 No one's ever been able to find a number n such that if you do the hailstones 115 00:10:08,460 --> 00:10:11,010 sequence on it. You don't reach one. 116 00:10:11,010 --> 00:10:13,720 Every number n that they've tried, always reaches one. 117 00:10:14,770 --> 00:10:19,350 But no one has approved that every number n will always reach one. 118 00:10:19,350 --> 00:10:31,060 The reason I'm showing you this trick problem is to show you the importance of 119 00:10:31,060 --> 00:10:34,700 termination arguments. The 2 termination arguments we did over 120 00:10:34,700 --> 00:10:41,587 here in fractals were so simple, that you might have thought termination arguments 121 00:10:41,587 --> 00:10:45,440 are always simple. And they're not always simple. 122 00:10:45,440 --> 00:10:50,130 They're both essential because when you have generative recursion, we don't know 123 00:10:50,130 --> 00:10:53,610 whether these functions are going to stop without a termination argument. 124 00:10:53,610 --> 00:10:57,640 So they're essential. And while they're sometimes quite simple, 125 00:10:57,640 --> 00:11:03,000 like they are in the triangle in the carpet, even simple functions like hail 126 00:11:03,000 --> 00:11:06,820 stones can sometimes have termination arguments that are so hard that they're 127 00:11:06,820 --> 00:11:11,490 not possible. Now this is a bit of an extreme case. 128 00:11:11,490 --> 00:11:14,980 In the functions that you are going to write, you are unlikely to encounter 129 00:11:14,980 --> 00:11:17,231 termination arguments that are impossible to prove. 130 00:11:17,231 --> 00:11:21,236 I'm just showing you this example as a way of helping you see that the 131 00:11:21,236 --> 00:11:24,254 termination argument can be hard and is worth doing. 132 00:11:25,280 --> 00:11:29,640 Usually termination arguments are going to be quite possible, and they're 133 00:11:29,640 --> 00:11:32,920 often going to be a little bit harder than the ones in fractals. 134 00:11:32,920 --> 00:11:39,564 And we'll see some of those in the remainder of this material on gendered 135 00:11:39,564 --> 00:11:42,264 recursion.