In the last video, we drew some pretty pictures of triangles and squares.
In this video we're going to, look at some pretty pictures too.
We're actually what we're going to do is we're going to look at some of the math
or, or very simple function. It's not math.
It's a very simple function. Behind a pretty picture.
There's this thing called the [INAUDIBLE] conjecture, and it's about a sequence of
numbers that work like this; if the current number is even, then the next
number is n over two, if the current number is odd, then the next number is 3n
plus one. And what I've done here is, using the
recipe for generative recursion, I've designed a ISL function for hailstones.
That's what this sequence is historically called.
Which basically says, look, when we get to one, we stop.
So if n is 1, we produce the list 1. Otherwise, we cons n onto the next call,
which is if n is even, we call ourselves recursively with n over 2.
And if n is not even, in other words, if n is odd, we call ourselves recursively
with plus 1 and n times 3, which is exactly this rule up here.
So there's hailstones, and the reason it's called hailstones is that if you
compute the sequence for very, for a number of values, I'll just do it for 10
now... Now if you compute the sequence for a
number of different starting values and then you measure the length of the
sequence and you plot that, you get a picture kind of like that.
Let's talk about something else for a second.
Look at Hailstones. Hailstones is a recursive function that
calls itself with either n divided by 2 or n times 3 plus 1.
Let's compare Hailstones to the Sierpinski's Triangle function.
As tried, the Sierpinski Triangle function Is a recursive function that
calls itself recursively, with s over 2. Now if you think back a bit, when you
first saw recursive functions, I think you probably got a bit concerned.
Hey is this ever going to stop? This function is calling itself.
Why will it stop? And then I convinced you not to worry
about that. Because we've talked about the notion of
a well-formed self-referential type comment, it had a base case and a
self-reference case and having resistance of the base case meant that recursive
functions operating on this kind of data would always stop.
And the reason they would always stop is that if it wasn't the base case, they
were going to take a subpiece of the current data.
And by taking subpieces of the current data, in the case of lists, by taking the
rest of the list each time, they would eventually reach the base case, again, in
the case of lists emptied. And so that's why we were happy with
those recursive functions and we knew they would stop.
What about these recursive functions? They're not operating on a well formed
self referential data definition. So that previous proof that they would
stop doesn't apply anymore. What we need for these functions is a
three part termination argument. Let me show you what I mean.
I'm still in termination starter. And the problem here is to do a three
part termination for s-try. Okay?
Now what I'm going to do actually is I'm going to pick this up.
And take it over to fractals view one I want to put the termination argument
right there. We'll paste it in right here to fractals
v one and. I'll get rid of just the description of
it. I'll pull just that part.
So now, this is going to be the three-part termination argument.
The first part of a termination argument is the base case: When does the function
stop? You can usually pick these right out of
Of the definition of the function. It stops there.
The next part of the argument is the reduction step.
What is the argument to the function in the recursive call?
What is the thing which the template calls the next problem?
Well, again, that's usually pretty easy to pick out of the function definition.
In this case, it's S over two. And then there's the argument that
repeated application of the reduction step will eventually reach the base case.
What that means is that if I start with a legal s [INAUDIBLE] and I keep doing the
reduction step over and over again, I will get to the cutoff.
And in this case that's fairly straight forward, as long as the cutoff is greater
than 0, and S starts greater than or equal to 0.
Repeated division by 2 will eventually be less than the cutoff.
I promised we wouldn't do much math in this course.
I'm still keeping my promise but I'm getting a little bit close to it.
But, I think that even people who don't love math will agree that if you keep
dividing a number by two over and over and over again, that number is eventually
going to get right up to an approaching zero.
And so, as long as the cut off is bigger than zero you'll eventually get to be
less than the cutoff. The point of the three part termination
argument isn't to talk about how fast you're going to get there, it's just to
prove that you will eventually get there. So with these three part termination
argument, which you should always include when you use generative recursion, we now
know that stri will stop. Let's do another one.
And this one is so simple that you might find it too simple, but I want to do it
because as soon as I do this one, then I'm going to do a trickier one.
I'm going to go back to fractals v1, and I'm going to do the three part
termination argument for the carpet. Okay?
And in fact, what I want to do, Is let you do the three part termination
argument for the carpet, okay? So there is the carpet.
You want the base case, the reduction step, and the argument that repeated
application of reduction step will eventually reach the base case.
This is going to be almost exactly like the one we just did.
I'm aware of that but please do it anyway.
Okay, now here is my answer to the three part termination argument for the carpet.
Base case is, again, is s less than cutoff.
The reduction step is divide s by three, and the argument again is as long as
cutoff is greater than zero, and s Starts greater than or equal to zero, repeated
division by 3, will eventually reach base case.
Great, there we go. That's two three-part termination
arguments. Seems pretty easy, right?
Let's go back over here to termination starter, and do the three-part
termination argument for hailstones. What I'll do is I'll bring it up to right
next to hailstones function. What's the three part termination
argument for hailstones? Well let's see the base case is that n is
one, and the reduction step is, what's the reduction step?
Well it's right here, in this case I can't quite pull it directly out of the
code, but it's if N is even, then N over 2.
If N, if N is odd, then Plus one times n three.
That's the reduction step so now we need to argue that the repeated application of
reduction step will eventually reach the base case.
Well. You know, this first line looks pretty
good, n keeps getting smaller. And if I'm going to argue that n reaches
1, n getting smaller all the time is good news.
But on this next line, n gets bigger. It multiplies by 3 and adds 1.
Hm, this could be hard. And in fact, this is hard.
It's extremely hard. It's so extremely hard that the
mathematicians haven't been able to prove it yet.
And they've been trying for years. And that's despite the fact that no one
has ever been able to find a counterexample.
No one's ever been able to find a number n such that if you do the hailstones
sequence on it. You don't reach one.
Every number n that they've tried, always reaches one.
But no one has approved that every number n will always reach one.
The reason I'm showing you this trick problem is to show you the importance of
termination arguments. The 2 termination arguments we did over
here in fractals were so simple, that you might have thought termination arguments
are always simple. And they're not always simple.
They're both essential because when you have generative recursion, we don't know
whether these functions are going to stop without a termination argument.
So they're essential. And while they're sometimes quite simple,
like they are in the triangle in the carpet, even simple functions like hail
stones can sometimes have termination arguments that are so hard that they're
not possible. Now this is a bit of an extreme case.
In the functions that you are going to write, you are unlikely to encounter
termination arguments that are impossible to prove.
I'm just showing you this example as a way of helping you see that the
termination argument can be hard and is worth doing.
Usually termination arguments are going to be quite possible, and they're
often going to be a little bit harder than the ones in fractals.
And we'll see some of those in the remainder of this material on gendered
recursion.