---
Video Title: Cost of LOOKUP
Description: Theory of Computation
https://uvatoc.github.io/week3

7.5: Cost of LOOKUP
- How many NANDs are required for each LOOKUP?
[Note: the proof shown doesn't quite work - see the Week 3 problem on fixing it.]

Nathan Brunelle and David Evans
University of Virginia
---

Let's look at how many gates we had to do
in order to do this.

So I'm going to show that we could do this
using, at most, 4 times 2 to the k gates.

So we're going to do
this by induction, so we're

going to have a base
case, where k is equal to 1.

In our base case of k is equal to 1,
we required 3 gates.

And it was 3 gates because if required 3
gates.

We said lookup1 was just the same as if,
if required 3 gates.

So our base case, where k is equal to 1,
that requires 3 gates as well.

I'm going to get that.

Okay, so now we're going to have our
inductive hypothesis.

Our inductive hypothesis
says, let's assume

the number of gates
for lookup sub k minus 1.

We want to show that that is going to be
less than or equal to, at most,

4 times 2 to the k minus 1.

So we're going to assume that this is
true.

And then what we'd like to do is,
I'd like to show that the number of gates

for lookup sub k is less than or equal to
4 times 2 to the k minus 1.

Sorry, forget the minus 1.

4 times 2 to the k.

So that's what we'd like to do.

So in order to do this, let's identify in
terms of lookup sub k minus 1,

how many gates lookup sub k is going to
need.

So when we did lookup sub k, the number of
gates we used, what we had to do,

if we look at this, we had to do 1,
2 lookup sub k minus 1s.

So we had to do our k minus 1 lookup
twice, and then we had to do an if.

However many gates lookup sub k minus 1
required, we're going to do 2 times that,

and then we're going to add 3 more gates
for that if.

So if lookup k minus 1 requires
however many gates, twice

that plus 3 is how many
gates lookup sub k requires.

Our inductive hypothesis
said that this was less than

or equal to 2 times 4 times
2 to the k minus 1 plus 3.

This is equal to 4 times 2 to the k plus
3.

And why do I have an extra plus 3?

Yeah, I definitely did something wrong
here.

What did I do wrong?

Essentially, the idea is that we require
roughly twice as many gates to do lookup

sub k as we had to do lookup
sub k minus 1, because we

had to do 2 lookup sub k
minus 1s in that situation.

All this exercise of doing syntactic sugar
is to show you that we can start doing

more and more and more complicated types
of functions using only NANDs.

So everything that we've
discussed, we now know that

we could do all of that
using exclusively NANDs.

The next thing we're going to do next
class on Thursday is we're going to use

this syntactic sugar in order to show that
NAND is, in some sense, universal.

And in this case, when we say universal,
we mean that we're going to be able to use

only NANDs to compute any finite function
at all.

So no matter what finite
function you want me to

implement, we know that we
can do that using only NANDs.

So NAND circuits, they can do any finite
function ever, is what we're going to show

next class, which is
going to imply that and

or not circuits can also
do any function ever.