--- Video Title: Computing Any Finite Function Description: Theory of Computation https://uvatoc.github.io/week4 8.1: Computing any Finite Function - Functions at Lookup Tables - Why isn't this (yet) a valid NAND straightline program? - Try to implement 0 and 1 yourself before watching the next video Nathan Brunelle and David Evans University of Virginia --- We want to show that, in some sense, NAND is universal. The things that we can do with just NAND straight line or NAND circuits, and in particular, we're going to show that this is something that we're going to call universal, which means that we're going to be able to do every finite function here. So when we say universal in this context, we mean every finite function. We're going to show that any finite function you could ever come up with, we can make a circuit that's going to do that. So this says every function is a valid function for you to try to implement in your circuits. Some of them are going to require more gates than others, but any function that you could ever think of that's a finite function, you can create a circuit to do it. So what we're going to do is we're going to show that any finite function at all can be computed by some NAND straight line program. Or equivalently a NAND circuit, or equivalently an AND or NOT circuit, or an AND or NOT straight line. Any of these. But we're going to do it from the perspective of NAND straight line. That's going to be easiest, as it turns out. Let's consider that I have this function that takes three bits as input and gives one bit as output. So this box over here, this is where I'm defining my function. Here is the input-output table to that function. I didn't pick any particular function for this, I just picked some random things. That's kind of the point, that it doesn't matter what function we write down in this table. We're just going to be able to implement whatever that is. So let's consider that we have some function, some finite function. So we've got a fixed number of input bits, we've got a fixed number of output bits. In this case, the number of inputs is three, the number of outputs is one. And we're going to write down this table that represents what each output should be for every input. This table is perfectly identifying the function. This is everything we could ever want to know as far as the identity of this function is, is contained in this table. Given this table, we know exactly the function we're trying to implement. This is every input and its output for this finite function. So the idea for how we're going to implement this function, no matter what it is, is we're going to show that in our straight-line program, we can sort of have one variable to represent every single possible input. So we're basically just going to, in our program, have a variable that's like row 0, and then a variable that's row 1, and then a variable that's row 2, and then a variable that's row 3, and so on. So we're going to have a variable for every single row in this table, And the value of that variable is going to be, if we had that row's input, the value is going to be the output for that row. So the variable that's representing row 0, its value is going to be the value of the output for input 0. So whatever input 0 ought to be. The value that the variable for, say, row 3, the value that's going to have is whatever the output should be when the input was 3, and so forth. Once we have all of these variables, we're going to do a lookup with all of those variables and the actual input we were given in that case in order to get the proper output. So essentially, once we have a variable for each row in the table, we can make one big long string that has all of those variables in it. That's just the concatenation of all of those variables, essentially. This right-hand column is one big bit string, and then we use the index to find which bit to return out of that string. In this case, here is that same table again. What we're going to do is here are my variables, one for each row in the table. Right now, this is not quite valid straight line. There is one issue with this, but bearing with me for a moment, the idea is going to be that, say, the variable where we execute the function on the input 000, the value that we're going to assign to that variable is going to be 0, because that's what we said the output should be for that input. When the input was 010, our table told us the output should be 1, so that's the value that we gave to that variable. Why is this not proper or NAND straight line? What are we doing that is not allowed in our model of computing so far? Okay, so we're not using NAND. We're using lookup, but we defined what lookup meant, and we also said that having defined functions, user-defined functions, doesn't increase the power of our programming model. So this is something that we're allowed to do. So our model of computing for NAND circuits was that we could have new variables being set equal to something. What could variables be set equal to? Yeah. Right, so we can only assign it to NANDs or the outputs of functions or something like that. Here, I'm using the constant 0 or 1. That is not something we've ever talked about are we able to do yet. So we need to talk about how I can avoid just saying this is set equal to 0. I need to somehow calculate 0 in order to actually get this to work. So we need to somehow create a function where maybe the output we can just guarantee is always 0. And then we can invoke that function instead of getting 0. And then have another function where the output is always 1 and so forth. See if you can come up with functions, two functions, one whose output is always 0 and then a second whose output is always 1. Thank you very much.