It's a little easier to read. And then again, we have s of y instead of just simply saying y plus 1 for the reason I just said, because technically you want the right-hand side to be in terms of y. What you do with y is your business, including adding 1. It's not that we have access to the left-hand side. We're trying to build the left-hand side. And just to remind you, I'll put a note here. All right, that's actually the case in discrete mathematics. All right, so you can add all things up and you could multiply all things. All right, now we get into a little bit more important, and these are called existential quantifiers. Very fancy name. What's really fancy name is that existential quantifiers. Quantifiers means adding things up or counting things. Adding or counting or, you know, doing something to a series of numbers. That's the, right, you have multiple numbers and you're dealing with it. So that is, that is what? That is quantified. Existential is a play on words from the word exist, which is interesting because it's not just exist, it's also for all. For all. There exists is one of them, but for all is the other. They use the A and E upside down and backwards. In other words, mathematicians. Maybe we should put a note in that. So the mathematicians use the following. For all. Mathematicians, mathematicians use the upside down. A, all, for all. And mathematicians use for notation, notationally. And mathematicians use the reflected E. You turn E on its, you rotate it, rotated E. You wrote, well, okay, reflected. You reflect E, mirror image of E. So the E is backwards. Reflected, oh, backwards better? Backwards E? Maybe backwards. I don't know. Whichever works for you. The backwards E notationally for there exists. Which here is just called exists. All right, you know what, let's say backwards. Backwards E. For there exists. Okay, so just in terms of notation. All right, anyway, we're going to use, anyway, for all and exists. I'm going to, because I like to have words, if possible, for documentation purposes. All right, maybe I should have done above, sum and product. Hmm. Maybe I should have. Let me just think for a second. Well, it's going to get messy later, so, okay. Anyway, so what's the, what's the, what you call it, what's the mathematical definition equivalence to for all? So now, for all. So now, for all, now in this case, it's existential quantifiers, is that they're Boolean here. So existential quantifiers on a, on Boolean predicates. Existentials. Existentials are philosophical terms, so it makes sense that it's on Boolean, where Boolean is true or false. Anyway, so for all, t less than or equal to y, p of t, x1 through xn. You want to know, is it true, is that value true for all in the range? Is p true? Is p true, you know, that's, that's the question, is p true for all values in the range, right? Is p of x, and I don't mean just p of x, p of t dot dot dot, is p true for all values in the range, t less than or equal to y? Okay? That's, that's what you want to know. So for all, it's a statement that it's true and maybe it's false. Alright, so that's what you want to figure out. So here's the idea. The idea is ignore the eq. eq means equal. Concentrate on the pi first, the product. How could it be, if, if, if it were true, right? If, if it were true that, that, that, that p is true for all the values t less than or equal to y, then p of t will be outputting one continuously. Right? So be, and if you multiply them, it'll be one times one times one times one times one. Right? Because for all is basically and, which is product. So you want p of zero to be true and p of one to be true and p of two to be true and p of t to be true and p of y to be true. So then if you multiply those ones, you better equal to one. So the product, test out the product of all those Boolean predicates and report back whether it's equal to one or not. Okay? If it is, then p was true all the times in all those values in that range. Now what about there exists? Is p of true for some value or values? It could be more than one. But we only need to show one in the range. But once one is true, you're done. It could be that more than one is true. All right. So exists, there exists a t, some t less or equal to y, such that p of t is true. All right? And that's on line 56. I'm sorry. On line 56 is our, is our, what you call it, is our stimulation equivalence in mathematics. All right, so why is, how does this work? So over here, let's add them up. Let's add up. Ignore the alpha, ignore the EQ. Concentrate for a second on summation, the sigma. Sigma is summation, right? I could have done sigma there too. All right, I don't know. Maybe I'll change it later. See if it's trivial. I'm curious if it's trivial. Oh. Not bad. Well, that one went over pretty well. One second, let's bold that. Not bad. All right, so let's see if we could do the same thing with pi. Not bad. All right. Yes, we can. In Excel, it's sometimes tricky to do this, but it seems to be working, so. All right, here we go. So that's pi. Good. All right, nice. I thought I bolded this. All right, not bad at all. What's going on here? Okay, good. Now, oops, one more time. Sorry. One more second. Good. All right. Okay, so there exists. So one more time. Let's concentrate on sigma. If we add up the values of f. Okay, so instead of p, I used o. Why did I use p? F. It's p. If you add up the values of p. So if p were false. Imagine p is always false. Then the summation is zero. If the summation were zero, then it's equal to zero. So equal will be one. But then alpha will be... is the not, and it will change one to zero. Now let's imagine the summation is... p is true. It may be one or more times. So the summation is a positive integer, greater than zero. In which case equal to zero is false, which is zero. And then alpha will turn that zero into one. So if there exists any value, t, such that p of t is somewhere equal to true. So then the... So then what? So then if that were the case, so then the summation will be greater than zero. In which case the equal is false, it's not zero. And then the alpha will turn false into true. Because there exists some value where it's true. Okay, now comes the main... the main character, the protagonist of our play. All of this is to lead up to bounded minimization. That is going to be the key discussion. Bounded minimization. Now bounded minimization is a... it takes a little while to get used to. So, the concept is straightforward. I'll mention it to you in a second. But why the following function works... is the... why this... sigma pi alpha. I always used to say... imagine... no, it's sigma pi alpha, just to remind you of that. It would be... that should be... sigma pi alpha. It's possible someone did it already. But sigma pi alpha should be the... name of the computer science honor society. Because of this. It's great. Sigma pi alpha. But anyway, bounded minimization... is a critical... is a critical... component of understanding primitive recursive... what it is and what it isn't. All right. Bounded minimization. So... see here the function bounded minimization... I'm just... I'm only going to... make this... highlight it... so you realize that this is not the next line. The next line is the implementation. Okay? But the notation is M-I-N... min. And what you want to know is... the first time... we're... well, in spirit... we're dovetailing exists... but it's much more than there exists. Okay? But in spirit... because exists says... that somewhere between 0 and y... p is true. Bounded minimization wants to know the first time... that p is true... between 0 and y. Okay? The first time... that p is true... right here... on line 64. What is the first time... that p is true... in the range? Okay? That's what we want to know. All right. So... well, I have... the diagram... I would put maybe separate... I'm leaving it here for now. We're gonna get to the diagram in a second. But let's just take a quick look... what's going on. No, I guess not. Okay. So... we're gonna... the next tab is below right now. See next tab... for... see next... diagram... all right. Whether it be next tab or not, I'll decide later. Whether... I'll put it in a separate tab or not. When I send you the notes, I'll figure that out. Anyway... let me just highlight that so I could... make note of that later. Okay. So... in the example we're about to do... go through... to understand this... pi... sigma pi... alpha... the... we're gonna... the... the situation is that t is... p... p is true... when t equals 5. Okay? That's the first time. So p of 0 is false. p of 1 is false. p of 2 is false. p of 3 is false. p of 4 is false. Now, what's interesting is... because we start from the value 0... right? t equals 0 to y. So at... since we start with the value 0... so it comes out... that when t is 5... we have... five... falses... before it. It's always gonna be that way. When t is a positive number... let's say 5... that's the first time. p of 5 is true. So let's count... how many numbers... before it... was p false? Because... 5 is the first time. So p of 0... 1 is false. p of 1 is false. That's the second. p of 2 is false. That's the third. p of 3 is false. That's the fourth. p of 4 is false. That's the fifth. And then... p of 5 is true. And that will always work out. So that's very, very important. So on line 63... if t is not yet 5... concentrated on the alpha... then the p up to that point... will be false. And alpha will make it true. In which case... multiplying those trues... is still true. Again... t equals 5... is the first time... p is true. It's false... from 0 through 4. Up to that point... the alpha of those falsities... is true. Which is equal to value 1. Multiplying those ones... is still 1. Now add it in. Add it in that 1. Which is going to count... how many... of the values before t... is it all false. And that's going to be 5. Which is going to turn out to be... the first time that p is true. Okay? That's the essence of how it works. Let's go through the example. Okay? So p... p is true... for 5. That's in this example. Alright? Again... garbage in, garbage out... on the assumption... I just put a note... Geigo... i.e. on the assumption... that y... will be at least 5. If you don't have y equal to 5... then you're not gonna... it's not gonna work. This is only gonna work... if you can actually get to 5. Alright. Now... So... let's do column by column. When t is 0... Okay, no, I'm sorry. Again, when t is... 0 through 4... Let me see if I can do that better. I'm hoping that doing the following will make it simpler. At least hope. Okay. 1 through 4. Okay. One second. Let me do a little bit more here. Okay. Excellent. So when... When what? When... So here, this is our p. In other words, this is our p. p of x. Okay. That's our p of x. And the outputs are stored in this array. On line 81. Alright. That's our array. Maybe it would have been easier. Would it have been easier? Maybe. Let's see. Maybe it would have been easier to put it... first. Oops. Wow. I jumped a lot. Alright. So let's call that p of x. Alright. Maybe that's about it. Alright. So this is our p of x. Now. What happens when t equals... What happens when t is equal... Okay. Let me just think for a second. See really... I'm sorry. Okay. No. So the idea is when t is zero... Okay. While you're iterating through... So maybe I shouldn't have called that t. These are just the inputs. These are the t's. Give me one second. Maybe I... This is just inputs. So technically this is x. These are our inputs. Okay. That's better. Okay. Fine. Now. Let me... The last one. I'm almost there. Good. Alright. Now. When t is zero, what happens? When t is zero... Interesting. I'm hoping... Would it make... Would it make sense to put lines here? Let me think. Yeah. Maybe it would. Alright. One second. Oops. See. The problem is the first line is not the... One second. I'm exactly happy with that. Oh. Okay. So I know what to do. That's better. Yeah. That's it. Okay. Good. Alright. So on line 80 and 81, that's the P. P has inputs and P has values. Right? P has inputs and P has values. On line 80 and 81. Right? What are those values? P of zero is zero. P of one is one. P of two, three, and four is zero. I'm sorry. Let me do that again. That was a mistake. P of zero is zero. P of one is zero. P of two, three, and four is zero. Finally, P of five is one. That's the first time. Alright. And what happens afterwards, we don't care. Right? Not really relevant to us. Dot, dot, dot, dot, dot, dot. Whatever those values are. All right? Eh, I don't like that. That's better. All right, fine. Now, when t is zero, so you're only going to explore... t is going to explore how many times is p zero up to t. So when t is zero, then x equals zero is false. And then the not function, the alpha, becomes one. The pi of one is one. The multiplying of one is one by default. Right? And then that's it. And then summation will add one to it. Now, when t is one, then at that point you're exploring x equals zero and x equals one. Right? For index x equals zero, and here it's for indices... I'm just trying to throw in the word... I'm doing it. Okay. In a second. Indices. Oops. Okay. Good. Okay. On line 84, when t is one, so then the alpha of x, p of zero is... Zero becomes one. The p of one is... Zero alpha becomes one. One times one is one. And then you add it in. Right? So we're adding in a one when t is zero. We're adding in a one, the summation. We're adding in a one when t is one. When t is two, so those zeros, alpha becomes one. Multiplied becomes one. Added in becomes three. When t is three. When t is three, there are four x's involved. x equals zero, one, two, and three. So then you... Alpha of those zeros are one. Multiply them together is one. Add it in. And then finally when t is... That becomes four. And when t is four, there are five. Indices x equal to consider zero, one, two, three, and four. The alpha of those zeros is one. Multiply them together is one. Add it in. It becomes five. Now, the question becomes what happens afterwards? All right. What happens afterwards? That's really key. Because if... let's say y is 100. Right? Suppose y equal to 100. So you keep on going. The function does the summation till y. Right? What happens? But at that point... at that point... what happens is... that you now have a one in the mix. You now have a one in the mix. Right? So at that point, alpha... alpha is... okay, so alpha here... Oh, that's interesting. Give me one second. These are... I'm sorry. No. Alpha is one. Alpha is one. Because alpha of zero is one. But now you have a one here. And alpha of one is zero. And that will... that will always be the case. Right? Alpha of one is zero. Let me get the real alpha. Alpha of zero is one. Alpha of zero is one. Right? But then... Alpha of one is zero. And then when you multiply it from that point on, the value is zero. Okay? So at that point, the value is always zero. Alpha of p of x is zero. Thus the product is... alpha of p of x. At this point on, right over here. That point on is... will be... just to emphasize that, let me fill it in with a different color maybe. I'm hoping this is helpful. Emphasize this point. What's a good color to use? Okay? At this point... yes. Okay? Alpha of p of x is... at that point is zero. From this point on. Thus the product is zero. And the sum up to this point does not change. So we're good. That is what's called bounded minimization. Amazing. Brilliant. Davis, to figure this out. Davis, Karp, each of these people were super brilliant. So that's what's called bounded minimization. The first time that the... the minimal... the first time that p is true. Now, some technical issues... Turn this over. Some logistic issues that we have to mention... With bounded minimization. So two... there are two logistic issues. We're not going to change anything. But you have to be aware technically. Okay? What happens if p is false for all values t less than or equal to y? Right? This whole discussion assumed... this whole discussion assumed that it eventually becomes one. Right? That was the assumption. That it eventually becomes one. But what happens? Okay? So that's a really good question. Should I bolt it? I don't know. Then the above formula would return y plus one. Not zero. Since alpha p of x is one for all those indices. Now... so then what do you do? Because that... you're getting a false hope. It's not true. It's... it's never true. So that's the question. What do you... that's the issue. What do you deal... how do you deal... with the issue of... that... what do you deal with... if p of x is false? So there are those who instead embed the above formula within an if-then-else. So that if p is never true over the stated range, then the output will be zero. However, the above formula also returns zero if, in fact, p of zero is true. Thus you would actually need to test if p of zero is true after computing this embedded if-then-else. So it's a mess. It's not... there's nothing you could do about it. We're not going to change this beautiful formula here on line 63. Line 63 is a really beautiful formula. And we're not changing that. Okay? That's our mega formula here. Right? That's our major formula. We're not changing that. Okay? We're not. But there is this issue. What do you deal with if it's true? Well, how do you deal with it if, in fact, the output is... if it's always false? All right. So keep that in mind that this... you're going to have to do a bunch of Boolean tests after the fact in order to be careful to make sure that it's not always false. All right. There's nothing you can do about it, but that's what you got to do. All right. Davis also shows a number of prime-based functions to be primitive and recursive. While very interesting, the purpose of today's lecture was to concentrate on Boolean predicates and to lead up to boundary minimization. See, Davis had all the book. If you would like to explore those other functions. So Davis didn't stop here. Davis uses this for primality testing, which is fascinating. Prime functions. Did I see you right there? Yeah. Prime. Prime number functions. So that's really interesting. But the key we need is this boundary minimization. All right. Now, so they realized... So we have to show this, but we don't have it here. Let me see if I can throw this out. Give me a second. I got to get a definition for you, which isn't... Whatever. It's a technical definition. One second. Called Ackermann's function. Let me see. The easiest way to define it. One second. That is the easiest way. But I need it in a simpler form. Give me two seconds. I don't like the way that's written. Give me one second. Oh, yeah, that's the way it's written. Okay, fine. So let me... Ackermann's function. You'll see why it's important in a second. It's really important in a second. So Ackermann's function is a function A of M comma N. And it's recursively defined based on the following, depending on whether or not... Certain... Okay, we'll tell you what it's based on. So it's equal to N plus 1 if M equal to 0. If M equals to 0, all you do is add 1. All right. If M is greater to 0, but then N equals to 0... In other words, if it's not the case that M equals to 0, but rather... It's the case that M is greater than 0, but N is the one that's equal to 0. So then it's A of M minus 1 comma 1. Okay? So that's a recursive step. Finally, if M and N are greater than 0... If M is greater than 0 and N equals 0, and N is greater than 0. So then this is A of M comma A of M comma N minus 1. Let me double check. Something like that, but let me get the right indices. One sec. A... Okay. So it's M minus 1 and N minus 1. Oh. Close. All right. Oh. One second. The prethesis is in the wrong place. All right. There you go. That's Ackerman's function. So one more time. If A of Mn... It's recursive. If... If what? If M equals 0... If M equals 0, then it's N plus 1. Okay? So if M equals 0, it's M plus 1. If... If what? If it's... If M is greater than 0 and N is what? N is equal to 0. Then it's A of M minus 1 comma 1. And if... If both of them are greater than 0. So then... It's going to be A of M minus 1 comma A of M comma N minus 1. All right. That is... That's how Ackerman's function is defined. Now... For homework... Which I'm not going to collect. But this homework, I got to forewarn you. Try... To compute... A of 4 comma 4... By hand. Pencil and paper. Yuki's pen. And stop... When one of two things happen. Either one. A... Your hand gets tired. B... You filled up... A sheet of paper... And still have not computed... A of 4 comma 4. Try it though. I know it sounds like a futile experiment. But what it will give you the experience... First of all... It's a wonderful experience for following recursion. But independent of that... What's amazing about it... Is that... If we just take a look at it... All it does... Is plus and minus 1. Right? It's just plus or minus 1. And recursion. Right? Plus is primitive recursive. Minus 1. The predecessor is recursive. Primitive recursive functions. Other than that... We have composition and recursion. Right? Right? So... Maybe more than just a note. Because this is the key. This is why... This is why we're discussing it. The above function... Has only plus and minus 1. Right? N plus 1. N minus 1. N minus 1. That's it. Which are successive... Predecesive primitive recursive functions. Other than that... We have composition and recursion. Yet... Davis and others... He's not the first... Prove... That Ackerman's function... Some people... I should mention... A mathematician... Also... Okay, based on Peter's function... Out of fairness... There's a fellow Peter... Who contributed to this... On Peter's function... Anyway... Ackerman's function... At least the way we're presented... Based on Peter's function... He did a lot of the work... Las... Laszlo Peter... I think it's Laszlo... Peter's function... Okay... Yet Davis and others... Prove that Ackerman's function... Cannot be primitive recursive. Unbelievable... It cannot... Alright... So... The question... Which is another homework... I'm not gonna ask you to prove it... The proof is really interesting... Very algebraic... Okay... I'll add one more line here... Okay... Let me just say the homework first... And then I'll add the one line... The homework is... How is... The above... Formula... Philosophically... In essence... Not just the fact mathematically... It does something different... Philosophically different... Than primitive recursion... There's something here... That I would like us to realize... Which may not... You may not think... It should be so significant... But in terms... But it actually is... Very significant... There's something very different... Than all of our primitive recursive functions... And yet... Ackerman's function... Not just the plus and minus... One... In other words... We do plus one... This is minus one... Ignore that... Ignore... The... Previous... Ignore the... Issue of... The level... Descending... Top down... Top down... Versus bottom up... I think I can rewrite this... Our way... Let me... I'll check if I can rewrite this... Our way... Bottom up... That's not the issue... Not... Not our issue... But there's something... Very majorly different... And I need you to realize it... The one other thing... I wanted to say is... They... And then we'll have to stop... At the end of the class... They proved this... By showing... That Ackerman's function... Grows... In value... Faster... Than any possible... That's... adviser... davon sustainable... Primitive recursive function... They... They... They call this... Dominating... I don't know... Why... That's... That's what they call... A... Feature... They termed... As... Dominating... Dominating function... It is... Where... It grows faster... Not any other function... Anyway, that's their terminology. That's in the literature. Okay, so that's the end of class. If you didn't have a chance, kindly text the word PRESENT. I will edit this later and email it to you. And thank you all for attending. Oh, I'm tired. Whoa. Thanks a lot, guys. I may email you. I have to think. Monday was it? No. Next Wednesday's class, I may have to send you a media to do offline. Because I may be attending a conference. I won't know. Probably until Monday. But in case, I will email you. It'll be about... it'll be a pleasant discussion of data structures the operating system uses for recursion. So it'll be related to our topic. But I may have to do that. Just in case. All right. Thank you all. Bye now.