---
Video Title: Boolean Circuit Execution
Description: Theory of Computation
https://uvatoc.github.io/week3

6.2: Boolean Circuit Execution
- Defining the Boolean Circuit Computing Model
- What happens when an invalid circuit is evaluated?

David Evans and Nathan Brunelle
University of Virginia
---

We've seen how to represent billion
circuits, but to have a computing model,

we also have to define how they execute.

The book has a definition that does this.

We're going to develop an alternate one.

One way to think about a circuit,
and this is very natural if you think

about circuits as hardware, the edges are
really wires.

They carry values.

They're not unlabeled.

The edges are unlabeled.

They're just connections.

Well, for real, they carry values.

Well, not for real.

This is a model.

But if we think about how a circuit works
in hardware and our intuitive thought of

how it executes, we can think about those
edges carrying values.

They carry values that represent the bits
in the circuit.

That means we can define a function that's
going to map any edge to its value.

This is like a label of
a node on a graph, but

now we're labeling the
edges with their values.

But I've added one little wrinkle to this.

We might not know the value.

This is a symbol sometimes called bottom,
but it's used often to mean undefined.

If we think of this as a function,
we're saying, well, we're turning a

partial function into a total function by
saying for the things where it's

undefined, we're going to use this special
symbol to represent undefined.

So in that sense, it's still kind of a
partial function.

It's not always defined, but it's going to
make it easier for us to work with it if

we can explicitly say when it's undefined,
its value has this special value.

But if it's defined, it has zero or one.

If we have that definition, then it's
easier to talk about the output.

The output is what are the values on the
special wires that are the output wires.

And we're going to define the output of
the circuit now as the values on those

wires where the yi value,
the ith bit of the output,

is the value on the wire
from some gate to yi.

We're numbering all the
inputs and outputs, but

these special output
vertices always just have one.

It's maybe unnecessary, but it's to be
consistent.

Of course, for this to make sense,
for the output to be unambiguous,

there better only be one edge from a gate
output to a circuit output.

If there was more than one edge,
then we don't know what the value means.

Certainly, we haven't done anything in
this definition to say there can't be,

but we better say, to be a valid circuit,
there better only be one edge.

Have we defined the model of computation?

Do we know how to execute a circuit now?

What don't we know?

What do we need to do?

Yeah.

We've defined our output now in terms of
the wire labels.

We haven't defined w.

W is the function that goes
from edges to values, and we

defined output in terms of
w, but we haven't defined w.

We just made it up.

We have to explain what w means.

So how do we define w?

Any ideas how to define it?

So are there any special edges that we
need to know the value of w for?

Yeah?

Yeah.

Yeah, good.

All right.

The input edges, we better have some magic
way to know their value.

The circuit's not going to tell us their
value.

They came from outside.

The input's actually a gate.

So the input is some gate that is labeled
input.

It doesn't have any edges into it.

It has an edge out of it.

We've got to know that the value on any
edge where it's from an input to anything

else, we better have a way to get that
value, right?

That's from outside the circuit.

The point of the circuit is it can take an
input from the outside world, or our

mathematical outside world, and do some
computing on it.

So those are going to be special.

That's going to be defined by some input
function.

That tells us what the input for that gate
is.

Everything else better be defined in terms
of things that are inside the circuit.

So how do we define the other wire labels?

When we start, we better know the input.

The others we don't know.

Well, good news.

We have this special symbol.

That's what we define them as.

We define w on edges.

It's more useful to think
about, as long as the

value from the input to
the output doesn't change.

If we have an edge like this, what matters
is that value.

So we can define it just on the outputs.

Part of the awkwardness, or at least one
of the difficulties, these edges are

connecting outputs to inputs, and we
defined our wires.

Wires connect outputs to inputs,
right?

If we think of physical wires in a
circuit, or edges in a graph.

But we know the value on the wire just
from the output.

And it's always going to be the same.

The same output is connected to different
things.

All of those edges better have the same
wire label.

So we're going to
change, instead of this,

we're going to just
define the val function.

We can define the wire value in terms of
just whatever the first gate in the pair,

that's its value.

So initially, all the values are bottom,
unknown, except for the ones that are

inputs, which get their value from
somewhere outside of the circuit.

You're going to get their value from some
function input that has to be defined.

And if we're going to actually get an
output from the circuit, we've got to get

real values that aren't the undefined
values on the output gates.

So we need some way of making progress.

So how do we make progress?

Yeah.

Excellent.

Yeah.

Any gate that has all of its inputs
defined, we can determine its output.

And its output depends on the type of
gate.

And this is where you get into the
question of, are the gates total functions?

Or how do we define what gates compute?

But they definitely can't compute until
they have all their values.

Once they have all their values defined,
any gate, once its inputs are defined,

we can compute its output.

Do we know there are any gates that we can
compute outputs for?

Yeah.

So certainly, without constraints on the
circuit design, we do not know that.

With constraints on the circuit design,
we would like a well-behaved circuit to

say, every gate is connected to other
gates, and if they're in topological

order, eventually the gates before it are
going to know their values.

That's the intuition that we want this
definition to capture.

Here's the way we're going to write that.

We're going to say, here's our initially.

It should make you a little bit
uncomfortable that trying to provide a

mathematical definition here,
and we're using something kind

of like a while loop, which
looks a little more like code.

So that should make you a little
uncomfortable.

We would have to be pretty
careful to make sure that,

yeah, this is well-defined
what we're doing here.

But it's actually just saying,
well, we're going to keep doing this as

long as we can, which is easily defined
mathematically.

If that doesn't depend on any particular
programming language way of implementing a

while loop, we're just saying,
as long as there exists some edge in our

set of edges, so as long as we can find
some edge, it doesn't say which one,

pick any edge that
satisfies this property,

that currently we don't
know its output value.

If we didn't have that, what would go
wrong?

At least the way we've defined it.

Yeah, so this gets into, like,
if this was sort of, maybe if we had a

careful mathematical notion of what while
meant, it would be okay.

Because it doesn't matter that we can go
forever.

But it's kind of a lot more comfortable to
say, well, we're going to be done when

there are no other edges that are missing
their label.

We're going to look for
a gate that doesn't know

its output, and all of
its inputs are defined.

Any gate we find like that, we can
evaluate.

And we're going to evaluate it by applying
whatever this function is.

Although we've been calling the labels,
things like input, and, or, and not,

they're functions.

So we're going to take
whatever the label is,

which is a function, and
apply it to those inputs.

And now we know the value of the output of
that gate.

Are we happy with this definition?

What are the things we should
want to know about a definition

like this, especially one
that's got a while loop in it?

Yeah.

Go ahead.

Yeah.

So, we would like to know, for this to
match our notion of a Boolean circuit,

we want it to finish, and what should be
true when it finishes?

Yeah.

We should have the correct output.

Well, correct is defined by this,
right?

We're defining what it
means to execute, but

we have some notion
of what it should mean.

So it should produce the output that we
expect.

This is just putting that a little more
for this.

We've defined execution in terms of the
output that's produced.

That's the result of completing that
definition of assigning the values to all

of the wire labels or the outputs of
gates.

Before we try to see
that it behaves well, what

would it mean if it behaved
badly for some circuit?

So suppose there was some...
we complete this process,

and there is some yi that's
value is still undefined.

Good.

Yeah, it means it's a bad circuit in some
way.

So it's certainly the way we've defined
circuits.

If we don't have any constraints,
there are plenty of circuits.

Let's draw a simple one.

If this is our input and our output is
this, there's no connection.

It's never going to be defined.

What's another thing that could go wrong
with this without any other constraints?

Could we have a fully connected circuit
that still doesn't evaluate correctly?

What could cause that to happen?

Yeah, we could have a cycle.

If we have any cycles, no matter how much
they go through, they end up having

outputs that depend on inputs that depend
on outputs of the same gate.

We're never going to end up with a defined
value.

And sometimes this is kind of a nice
property.

At least it's a nice property.

Instead of saying we only allow circuits
that are well-behaved, say we've got a

definition, we've got a
computing model, and if you give it

a circuit that is bad in some
way, it's going to not blow up.

It's going to give you
something with this definition,

but it's going to give
you an undefined output.

That's kind of desirable.

Yeah.

So it doesn't have a value computed unless
all of its inputs are defined.

If we had a circuit like that,
this value is never going to be defined

because we can't get this output until
this input is good and we can't get this

output until both its inputs are defined
and they all start undefined.

So we're never going to define those
wires.

Great.

Thank you.