---
Video Title: Making Zero and One
Description: Theory of Computation
https://uvatoc.github.io/week4

8.2: Making Zero and One
- Making 0 and 1 from NAND Straightline

Nathan Brunelle and David Evans
University of Virginia
---

If we were to define one of these, we could,
with a single NAND gate, get the other.

How can we do that?

If I had one of them, if I
had implemented either 0 or

1, I could get the other one
using a single NAND gate.

How can I do that?

Yeah, so we could just do NOT.

If we were to implement, let's say,
0 first, one way I could implement 1 is I

could just say NAND
of the result of 0 with

itself would give us
NOT 0, which should be 1.

And we could do the opposite if we decided
we wanted to implement 1 first.

Which one would you like to implement
first?

Do you want to implement 0 first or 1
first?

0?

People want to implement 0.

Okay, so how can we do 0?

Yeah.

NAND AA.

NAND AA gives us NOT A.

And so we can say NOT A equals maybe NAND
A with A.

So we can then say RETURN NAND with A and
NOT A.

So, yeah, I think we just did 1,
didn't we?

So... 1.

Okay.

And then this one can be 0.

So in this case now we
can say that 0, we can

have... well, 1 is going
to be equal to 1 of A.

And then we can, for instance,
RETURN NAND of 1 with 1.

How many gates did we use for 1?

Which is now on the left.

2.

So we used 2 gates for 1.

How many NAND gates did we use for 0?

3.

So we can do our constants 1 and 0 using
at most 3 gates.

There it is written in something,
not my handwriting.

So, how is it that we're going to compute
any function then?

So basically what we can do then is we can
just take each of these and instead of

saying f of 0, 0, 0 equals
0, we're going to say

this is maybe equals 0 of
x0 or something like that.

Doesn't matter what input we gave it.

Whether or not that
input was a 1 or a 0, 0

is still going to give
us 0 as the result.

How many get that?

So now once I've done
this, I can just put all

of those variables into
one big long bit string.

And then the input variables used as an
index tell us what the output ought to be.

Because if these were 1, 0, 1 or something
like that, then that is going to

correspond exactly with whatever bit that
was, which is what the table said our

output should be when we got 1,
0, 1 as the input.

So this is going to implement that
function for us no matter what it was.

So now we know we can implement any
function at all using a circuit.

Using a NAND straight line program or
equivalently a NAND circuit or an AND or.

NOT circuit or an AND or NOT straight
line.

Yes.

Because I didn't care what this table
looked like.

Basically, I described this in
a general enough way that any

table you handed me, I could
convert that into a program.

So we could have programs that represent
tables in this case.

So since we can have a program that does
the same thing that that table describes,

any table can become any
program and any function

we should be able to
describe with a table.

Is this function bijective?

No.

So you mean the mapping from table to
program?

No, it is not bijective.

So just like there are boundless different
ways to implement the same thing in Python

or Java, there's going to be
lots and lots of different ways

you could implement the same
function in NAND straight line.

This just says that for any
function you give me, I can

always find at least one program
to implement that function.

But there might be others, there might be
some that are going to be more efficient.

Like if you tried to do this for XOR or
something like that, if you use this

approach to implement XOR, you would have
a lot more gates in your XOR program than

you could do if you sort of did it more
carefully.

But we know that any function we have,
I can find at least one program for it.

Yes.

How do we get two digit output?

This is something that I
haven't spent much time on

in class, but your book
does discuss this quite a bit.

Basically, what you would do is you would
just say return lookup3 as well as if of

something, as well as the and of something
else, and so forth.

So you can just list a
bunch of things to provide

as output, if you
wanted multiple outputs.

Does that answer your question?

That's not good for you.

So right now there, I put a whole session,
it will be a wrap.

But if you wanted to get some back.