--- Video Title: How Many Gates? Description: Theory of Computation https://uvatoc.github.io/week4 8.3: How Many Gates to Implement any Finite Function - Upper Bounding the Number of Gates - Constant Burglary Alert - What does this mean in practice? Nathan Brunelle and David Evans University of Virginia --- So we know that every single function can be implemented. Now let's see how many gates this is going to require. How many gates is it going to require? How inefficient could this be? Let's say that I have this finite function with n inputs and m outputs. I'm going to show you that this can be done in c times m times 2 to the n gates. Your book, by the way, Theorem 4.16, provides a tighter bound than I do, that requires a little bit more care than I'm going to do in class, but just know that that bound can be shrunk. So this procedure can certainly implement any function in some constant, whatever c is, some constant times m times 2 to the n gates. So let's see where this comes from. So basically there's three steps to implementing our function. Whatever our function is, there's three steps. The first step is to create a variable for every input. The second step is to assign 0 and 1 to each of those variables. And the third is to actually do the lookup. How many variables do we have? If we have n input bits, how many variables are we going to need? So n is the number of inputs, so how many variables do we need if we have n inputs? Yes. Yeah, so we're going to need 2 to the n variables. Because I needed a different variable per each possible input that we might have. And if we have n input bits, there's 2 to the n different inputs we could see. And then we need to assign 0 and 1 to each input. To each of those variables. How many gates does it require in order to assign 0 or 1 to a single variable? What's the maximum number of gates that could require? 3 gates each. Or 3 times 2 to the n gates total. And then finally, we do the lookup. We're going to have to do the lookup m times for all of our outputs. So once per output bit that we might consider. So if we only have one output, we have to do the lookup one time. So we're going to do the lookup. How many gates does our lookup take? Does each lookup take? How many gates does one lookup take? Yes. It's going to be 4 times 2 to the k is roughly how many gates a single lookup takes. How many remember this? So roughly 4 times 2 to the k. What is k here? So k, remember, was the size of the index. So what is the value of k and the lookup we're doing? Yeah, so n. So the lookup we're doing, we're doing the lookup, which is a lookup sub n. So we're going to do 4 times 2 to the n gates for that lookup. And then we're going to have to do that m times. So the number of gates total that we're going to need in order to do this is 3 times 2 to the n for assigning the values to all the variables plus 4 times 2 to the n times m. Yeah, so the 3 came from this. This was 3 gates. So when we're assigning our inputs, every time we needed to do a 0, we had 3 gates. So an upper bound for the number of gates we'd have to use to assign our inputs was when we had to assign 0s to everything. So 3 times the number of variables. So we have 3 times 2 to the n plus 4 times 2 to the n times m. So basically what we're doing right now is we're counting the number of gates that this procedure, an upper bound on the number of gates that this procedure is going to use. This is mostly for saying, like, we know now that for any n input m output function, I can implement it in at most this many gates. There are no functions of n inputs and m outputs that strictly require more gates than that. So this is an upper bound. So we're already doing upper bounds because we don't know whether or not we need 2 gates versus 3 gates to assign the constants. So just to make things easier, I got rid of that minus 4. But this is still going to be an upper bound. There are no functions that require more than that many gates. Yeah. M is the number of outputs that the function is going to have. Basically, if you have multiple outputs, you just say, here are all of the things to return. We're just going to say you can have, like, multiple return statements, essentially. And then everything with the return before it, since we just have this straight line, you go in order. It's not like when you return, you necessarily need to bail because there's no ambiguity for where to go next. So we're just going to say that you can have multiple return statements for our outputs. Our definition of circuits that we originally discussed had that. I just never actually showed you an example of a program that had it. And I apologize for that. Your book does have such examples, though. Our goal was to show that it was... What just happened? Oh. That is terrifying. Yeah. If this is home for you, then wait for the all-clear. So 14th and Wirtland. If that's home, don't go straight home after class. Yeah, that's jarring. So we wanted to show that it was a constant times m times 2 to the n that we needed at most that many gates. So let's see where that is here. 4 is our constant times m times 2 to the n. So we kind of see that pattern over here. And then this 3 times 2 to the n, we can think of that as being washed away by another constant. If I just multiply this whole thing over here by 2, then I can just get rid of that additive thing over there. This tells us that we're going to have a c times m times 2 to the n mini gates. We can be upper bounded by that. I just washed away a bunch of constants. That's something computer scientists like to do. There exists a c such that no function requires more than c times m times 2 to the n gates. So let's think a little bit about what this means in the real world. So your laptop is kind of a 64-bit machine, most likely. So that means that the length of the bit strings on your laptop is 64 bits. So that means that if I gave you as many transistors as you could ever want, you could implement any function at all that maps inputs of 64 bits to outputs of 64 bits. Your computer with its 64-bit architecture, if I gave you enough transistors, you could do that many things. How many transistors do you need? Well, you're going to need at least m times 2 to the n, which in this case is going to be 64 times 2 to the 64. What is that? Does anybody know what this is? A really big number? Let's see if Google can tell us. So what is 2 to the 64? What is that? 1.8 times 10 to the 19? Yeah, that's a pretty big number. More transistors than you're actually going to be able to put on there. So this tells us we can do any function if I give you enough transistors. Maybe not all of them are going to be practical, but all of them are possible if you don't care about the size of your circuit or the power it requires or something like that. All right.