---
Video Title: Defining a Computing Model for Boolean Circuits
Description: Theory of Computation
https://uvatoc.github.io/week3

6.1: Defining a Computing Model for Boolean Circuits
- Two Things we need to Define a Computing Model
- Modeling Boolean Circuits
- Representing Circuits, Assumptions Implied by our Definition

David Evans and Nathan Brunelle
University of Virginia
---

What are the two things we need to define
a computing model that apply to any

computing model anyone's ever going to
define?

If you don't want to think
about Boolean circuits,

think about Python
programs or Java programs.

If you're going to define a computing model,
what are the two things that you need?

Yes.

Between the three answers we got,
we kind of got the two pieces.

We need something that represents the
computation.

Here's all the programs that we can write,
what the things we can represent are.

With a Boolean circuit, it's the graph of
the gates and the gate labels.

This is the representation.

And the other thing we need, we need some
way to say what it means to execute.

We need to define what it means to
execute.

These two are closely related.

When someone defines a programming
language, they don't just define the

syntax usually, they're sort of mixing up
the syntax and what it means.

And the same thing with Boolean circuits.

Well, there's the representation of the
circuit and then there's how does it execute.

Those things are very
closely related and sometimes

sort of defined without
clearly separating them.

But they're really quite different,
right?

One is just saying, here's all the
possible computations we can represent.

And one is saying, here's what it means to
execute an instance.

If we're going to have a computing model
about Boolean circuits, we need some way

to represent a Boolean circuit that makes
it very clear what it is.

It should be unambiguous.

It should define the circuit.

So then we can actually execute that
circuit.

But first we've got to represent it.

And we can do it with pictures.

This is from the book.

We've got a notion of gates.

We've got inputs.

We've got outputs.

And that graphical representation and
thinking about inputs and outputs and the

way values move along wires, that might be
enough, right?

If we're informally thinking
about Boolean circuits

and what they do, we
might be okay with that.

If we're trying to do things like prove
whether some set of gates is universal,

maybe that's not enough.

Maybe we want to formalize this a bit
more.

So that's what we're
going to try to do first is try

to make this representation
a little more precise.

This is our starting point, which is
similar to what the book does.

We've got a graph.

We do have labels on our graph.

We have a set of vertices which are the
gates.

We have labels which determine what a gate
does.

And we have edges.

An edge connects two gates.

And we have some set of outputs,
some subset of the vertices.

The way I've defined it, this includes the
inputs.

The output gates are separate.

You should be a little careful.

Either V includes O.

And this is a subset of V, saying these
are the ones that are output.

Probably what would be better is to say
this includes the output.

We can have an edge from a gate to an
output.

This definition could have been more
precise.

It seems pretty awkward to have outputs
separately from regular gates.

So we're going to try
to fix that to not need

something special in
our definition for outputs.

That definition was not
the best way to define it

with outputs, but I'd rather
get rid of them anyway.

So now we're going to say there are just
the set of vertices.

We don't need a set of outputs anymore.

And the vertices are the gates and the
inputs.

And an edge can go to either vertex,
which is another gate, or it can go to one

of these special places, which is an
output.

And we've defined the number
of outputs because one of the

inputs is a natural number
that tells us how many outputs.

Are we happy with this definition?

Yeah, good.

So certainly there's a lot of constraints
required for a circuit to be valid.

This definition allows lots of things that
are not correct circuits.

It doesn't say anything about if something
is a not gate, it needs to have two inputs.

We'd have to say some constraint on the
edge set is a not gate.

There have to be exactly two edges.

Sorry.

How many inputs are not?

One.

And gate we have two.

Or gate we have one.

Right.

So there are lots of constraints that this
doesn't actually capture.

So there are lots of invalid circuits.

Let's take the analogy to a programming
language.

When someone specifies the
syntax for a programming language,

does it allow you to write
programs that are invalid?

Yeah.

Right.

So how the representation is defined of,
say, Python, the vast majority of programs

that you could create with that
representation are invalid.

Right.

The chances that you would hit a correct
program are basically negligible if you

just generated valid inputs from the set of
all Python things that you can represent.

Maybe that's okay.

Maybe we're okay with this allowing us to
represent invalid circuits.

What about circuits we might want to
represent that we can't represent with this?

Another way to ask that is
this definition assumes a lot of

assumptions about the kinds of
gates we can have in our circuit.

So here we've said,
well, maybe if they're only

and or and not gates,
we're okay with this.

It might assume other things.

So I want you to think about that for a
while.

We can make this a slack poll.

So I've listed five
possible assumptions that

this definition might
or might not imply.

When I say, you know, does it imply this
assumption?

What that means is, if
that assumption doesn't

hold, does the definition
still make sense?

Is there something about the definition
that, without that assumption,

the definition breaks in some very bad
way?

That would mean that it's implicitly
assuming these things.

Is there any assumption about gates having
two inputs here?

No.

Yeah, there's no assumption.

The edges are a set,
and we can have, for a

given j, we can have
any number of I's match it.

So what about the one output?

Is there an implicit assumption here?

So certainly the graph itself,
there's nothing about this edge set that

doesn't allow a gate that would have
multiple outputs.

But does it actually
make sense with the

definition to have a gate
with multiple outputs?

Yeah, we don't actually have any way to
refer to them.

We only can have one output for each gate.

I'm going to write that that's assumed.

And that's okay for this set of gates.

Are we giving up a lot
of potentially interesting

circuit designs by requiring
only one output gate?

Sure, yeah.

So we're definitely giving up things that
might be very useful for efficiency.

We're not giving up any
power in terms of what we

can compute, because
we know this is universal.

And we'll talk that more precisely.

But once we've got a universal gate set,
which we do have with and or or not,

we're not giving up any power as far as
what we can compute.

But maybe we're giving up some useful
alternatives.

Certainly a constraint.

All gates are total functions.

Do you think we're assuming this?

So first, are gates functions?

Yeah, the gates are functions,
right?

The gates, if we think
about at least what we

mean by and or or not,
the gates are functions.

Does our representation assume that?

Does our representation even tell us that
they're functions?

Until we define how it
executes, we don't know what

they are, or at least it
doesn't matter what they are.

So we're certainly not assuming anything
about them.

Okay, what about whether gates are
commutative?

So, make sure we understand what it means.

I think I have another slide, yeah.

So for a gate to be commutative,
sort of a gate, means if we switch the

order of the inputs, the output has to
stay the same.

So is that true for the and or not gates
that we have?

Yeah, right.

We can flip the order of the inputs.

Are there gates that that might not be
true for?

Sure.

We could have a less than gate.

That could be a useful thing to have.

If we had a less than gate,

these things should be different.

0 is less than 1.

1 is not less than 0, right?

So that definitely is not commutative,
yeah.

We haven't given anything any
understanding of anything yet.

They're just labels now.

I guess it's a little confusing.

When I say what we've done, and not
like...

So definitely last class, we
said we know what an and gate

is, and we talked about
Boolean circuits with and gates.

And you've read in the
book, there is an execution

model that we all
intuitively have in mind.

But for now, we're assuming we're just
talking about this as a representation.

We're not making any assumptions about the
execution model, which means we're also

not making any assumptions about the
gates.

The intent of the question is,
we want to understand, is this

representation limiting the things that we
might explore in ways that we might not?

If we only ever want to
represent circuits with and

or and not gates, then this
representation seems fine.

It's okay to assume that all gates have
two inputs, because the ones that we

happen to be... Actually,
we're not assuming that, right?

But it would be okay too, because if these
are two input and or and...

Yeah, not definitely does not have two
inputs.

So it would be a problem to assume that.

So we're definitely not.

But the one output assumption is fine for
that set of gates.

Oh, so the one output assumption is
because if a gate had multiple outputs,

let's say we had a gate like this,
how would we represent it?

The way we represent it, there's only one
way to refer to the output of a gate.

So we don't have a way to distinguish
these outputs.

If a gate had two outputs,
the way we've defined our

circuit, we don't have any
way to distinguish that, right?

The edges are edges between gates.

So if a given gate had two outputs,
we can't refer to them.

I guess they have to be the same, then
they might as well just have one output.

The way we've defined
the circuit says there's

no way to have a gate
with multiple outputs.

Does that make sense?

People seem unhappy with that.

Are you unhappy with that because it seems
like such a bad arbitrary restriction on a

circuit or because it's not clear from the
definition why that's the case?

Yeah.

Well, so we could expand that.

Okay, so we could say we can't have this.

We could certainly have something equivalent
which would combine it into two gates.

We could do something that produces those
two outputs from separate gates.

And because it's universal and we haven't
yet defined carefully what that means,

there must be some way to replace the
three input, two output gate with some

combination of two input, one output
gates.

So we're not losing any power as far as
the functions we can compute.

Once we have universal finite functions,
we can compute every function.

In terms of what we're losing,
it's not power, it's expressiveness.

It might be that we can make a much smaller
circuit if we could have gates like this.

One of the things we care about is
efficiency in the size of the circuit.

Certainly not allowing
specific kinds of gates

in our definition means
we can't explore that.

Yeah.

The assumption about the total functions.

Without a computing model,
what the actual gates do is

going to be important when
we talk about how to execute.

The way we're representing it,
we haven't committed to that.

So we could say we're going to have gates
that when they execute, if the inputs are

wrong, what's going to
happen is undefined or kind of

the circuit blows up or
something else happens, right?

We haven't said anything about how
execution happens.

So we're not implying anything about what
the gates do other than how they're

connected in this representation,
which does imply certain things.

So it's kind of an interesting contrast
that this property of being total

functions doesn't apply until we define a
computing model.

While being commutative, not necessarily
functions.

So I didn't put function in there,
but being commutative does apply because

we can't distinguish the order of the
inputs in our representation.

If we tried to have a
gate where the order

mattered, it would be
ambiguous what the output is.

And maybe you say, well, it's okay if the
output is ambiguous, but it seems like a

pretty broken representation if we have
gates where the order matters.

We have those two assumptions that I at
least don't like.

Do we like or not like the finite
assumption?

Certainly, if we're thinking of things
that can be implemented in physical

hardware, we really like the finite
assumption.

Finite means if we have enough resources,
we can definitely implement it.

So how do we remove the one output
assumption?

We kind of hinted at this already.

If we have multiple outputs from a gate,
what do we have to do in our representation?

Yeah, we have to have some way to label
them.

We just have to say, instead
of the edges being pairs of

gates, they're going to be
pairs of outputs and inputs.

We're going to label our outputs and
inputs.

We can add some kind of index to these.

And we start to run out of letters.

But we're going to add some kind of number
here that says, this is the first input

for that gate and the third output for
that one.

We should be a little clear.

Which one of these is the input and which
is the output of the gate?

If we have an edge.

So this is the one.

GI is the output and this is the input.

We can give those numbers and distinguish
them.

And that's going to solve both problems.

If we want to care about
order, we can't make

these things only
identified by the gate now.

We've got to add an index to them.

So we're going to do that.

We can think of those as natural numbers.

Definitely, they can't be any natural number
for it to be a circuit that makes sense.

If it's an AND gate that has two inputs,
if we number them zero and one,

those are the only two numbers that make
sense.

So we're not going to try
to add all the constraints

that are necessary to
limit this to valid circuits.

That's actually a pretty hard, complicated
thing and maybe not that interesting.

So that's the first part.

We can represent every circuit
that we care about, or at least

that we've decided to care
about, with this representation.

But for it to be a model
of computing, this is

what distinguishes it from
any other kind of model.

It's got to be executable.

We've got to define what it means to
execute a circuit.

That's the same to maybe to be a new one.

Same in between, Remember around the
screen and the table, the same one or you,

the left, and the right
answer isn't the right, it's the

right answer, the null to the
left answer is the right answer,