---
Video Title: Equivalence of Two Computing Models: NAND and AON
Description: Theory of Computation
https://uvatoc.github.io

5.5: Equivalence of NAND and AND, OR, NOT
- The NAND Programming Language
- Proving two computing models are "Equivalent"
- NAND = AON

Nathan Brunelle and David Evans
University of Virginia
---

Let's say that I wanted to define a new
programming language.

So before we had the and or
not programming language, so

the operations we were allowed
to use were and or or or not.

Let's say that I restricted this to being
only NAND.

We're no longer allowed to use and or or
or not.

We're only ever allowed to use NAND.

So this could be still a totally
legitimate programming language.

It would be exactly the same thing,
but with only NANDs.

Is it any better?

Is it any worse?

Yes.

Okay, so maybe it's equivalent.

In what way would it be equivalent?

If you could express all the first
operations using NANDs.

Exactly.

We can actually say that NAND straight-line
programs are equal in some way.

They're in some way equivalent to
straight-line programs.

And the way that they are
equivalent is we can show that

any function that I can
kind of describe, let's say.

Any function I can write an algorithm for,
a process for, or describe.

So we'll say any function
that I can describe

with one, I could
also do with the other.

So when we talk about models of
computation being equivalent, one way that

we might be talking about that is whether
or not we can write the same functions.

We can define the same functions with
them.

In this case, it turns out that using only
NANDs, we can do all of the same things we

could have done with all of and or and
not.

How would we actually go about showing
that?

Yes.

So we can write and, or, and not using
only NANDs.

So if we can take each of and and kind of
redefine that in terms of NANDs.

And do the same with ors and then do the
same with not.

Then that demonstrates to us that anything
we could have done with and or not

straight line programs,
we also could have done

with these NAND straight
line programs as well.

So essentially what we're doing is we're
writing a compiler.

You can think of it in that way.

We're writing a compiler that can translate
an and or not program to a NAND program.

And then we also are going to want the
other way as well.

We also are going to want
to have a compiler that can

convert our NAND program
to the and or not program.

Kind of like in order to show
that two sets were the same

size, you wanted to find a
bijection in between them.

So some sort of function that's going to
map both ways.

We want to find a conversion that's going
to map both ways between these two.

If we can convert any NAND program to an
and or not program, that doesn't guarantee

us that there wasn't some
and or not program that was

out there that I couldn't
have written with NANDs.

So in order to prove that they
are exactly equivalent to one

another, we need to show kind
of this two-directional translation.

And this is going to be a
consistent theme that you're

going to see with all of
these models of computation.

You're going to see a lot of things where
we look at a couple of different models of

computation, and we want to prove which
one is more powerful than the other,

or if they're equivalent.

And the way that we can do that is with
this idea of compilation, or simulation,

or something like that.

Can we transform any algorithm
or any process expressed

using one model as a process
using the other model instead?

Question.

Because and and not are
used in the definition of and, well,

and and not don't have to be
used in the definition of NAND.

I could instead just directly define NAND
in the same way that I did and,

or, and not here.

I could have just said, well, NAND is
going to be a function that maps two input

bits to one output bit that was zero if A
was equal to B was equal to one,

and one otherwise.

Yes.

So there's a difference between it being
automatic and us having done it already.

So essentially, we've already done one
half of that translation.

We've already said that we can take NAND
and rewrite it using just ands,

ors, and nots, because we did it right
here.

But that doesn't mean that it was
automatic.

Do you see the distinction?

Okay.

As we said, we've already done one
direction.

So now in order to finally show that these
are two equivalent models of computation,

we need to show the other direction as
well.

So we need to show that
I can take any and or not

program and rewrite it
using exclusively NANDs.

If I can do that, then that means that I
could have taken any program I wrote as an

and or not program and
rewritten it as a NAND straight

line program that computes
exactly the same function.

If I have two models of computation,
and I want to show that they are,

in this sense, equivalent,
that they can compute

the same functions, I
need to do two things.

I need to show that any process or
algorithm that I can implement with model

one can be converted to model two,
and I need to show that anything

implemented with model two can also be
converted back to model one.

One of these directions has already been
done for us.

We can convert NANDs to ands, ors,
and nots.

We saw this already.

So this one is done.

This one is the one that remains to be
done.

How can we express and or not straight
line programs into NANDs?

And when we talked about
the definition of what an and or

not program looked like, we
basically had three components.

We could have ands, we could have ors,
or we could have not.

Those are the only three
things that we really could

have seen in this and or
not straight line program.

So I could show how to convert the and or
not to a NAND by just taking each one of

these totally separately
from one another and showing

how to re-express that
using exclusively NANDs.

Let's start with not.

How can we rewrite not as NANDs?

The way this is going to work is we're
going to say that whenever I saw something

of the form X is equal to
not A in my program, I want

to rewrite that as one or
more NANDs in that program.

So what I could do is I could translate
that.

So I'm going to do this
translation every place

in my AON straight line
program that I saw in not.

I'm going to do this translation where I
instead say X will be equal to NAND A-A.

Because with NAND, what we're doing is
we're saying it is the opposite of A and A.

So whenever A is one, that means A and A
is one.

The opposite of that is zero.

So that is not A.

Whenever A was zero, then A and A is zero.

So the opposite of that is one.

So by doing NAND on A with itself,
we have done what is equivalent to not.

Let's do and next.

We've already shown how to translate not.

Yes?

Okay, so maybe what we
could do is we could first

compute a NAND and then
compute a not of the result.

So what we're going to
do then is this is going to

become Y is going to be
equal to the NAND of A with B.

And then we can make it so that X is the
NAND.

We wanted to do the not of the result of A
NAND B.

That's going to become the NAND of Y with
Y.

That's how we did not using exclusively
NANDs.

I'll leave it to you to convince
yourselves that that works for OR.

But we can do this for OR as well.

So we have shown NAND
straight line programs and and or

not straight line programs
are in some sense equivalent.

Because anything we could write with one,
we can write with the other.

In what way might they not be equivalent?

Can anybody think of any ways that they
might not be equivalent?

Yeah, so they are equivalent.

In the sense that anything one can do,
the other can do as well.

So they have the same things are possible.

So in that sense, they are equivalent.

Because the same things are possible.

However, they're not necessarily
equivalent.

Because it could be that one is slower
than the other.

So when we did this
translation, it might end up being

that we now had more steps
in, let's say, the NAND program.

Than we had with the and or not program.

So maybe that's going to be a slower
program than what we had before.

There is going to be this
distinction between what's

possible and maybe what's
easy or what's efficient.

In some cases, we're going to see that
there are relationships between what's

going to be efficient among our different
models of computation.

So we might find that even as we're
showing relationships between different

models of computation, we might find that
even if they're equivalent, in the sense

that all the same things are possible,
it could be that one of them is just

always going to be faster, or one of them
is always going to be at least as

efficient, or we might
have more complicated

ways that they're going
to relate to one another.

We're going to talk about some of those
ideas as well.

So...