---
Video Title: Representing Programs
Description: Theory of Computation
https://uvatoc.github.io/week4

9.1: Representing Programs
- Representing Programs as Bits
- How many bits do we need?

Nathan Brunelle and David Evans
University of Virginia
---

Last time, basically, what we did is we
started out by showing that we can use.

NAND or ANDORNOT to compute any finite
function, any finite function at all.

We can do with NANDs or ANDORNOT gates.

And we started this discussion of showing
how we could have some function that

basically simulates programs, that we
could write a function where the input to

the function is going to
be like a program and an

input for that program,
an input for the program.

And our output is going to be what would
happen if we ran that program on that input.

So we can define a function that does
this.

Programs, in the way that we described
them, are going to be of finite length.

The input is going to be of finite length,
so this is going to be a finite function.

We should be able to have
some circuit which implements

this function of doing what
the program is supposed to do.

What we started with last class is talking
about exactly what that function might

look like, how we could define that
function.

And our idea was to look
at how programs end up

getting run to help us to
implement this function.

And the way that your computer is going to
run programs is essentially when you hit

run on your computer, you're going to have
this table.

And in this table, you're going to have
like a list of all the variables,

one variable per row.

And then you're going to have the value of
each of those variables.

And essentially what you do is you,
in this table, just fill in all of the

values of the variables, like maybe a is
zero and then b is one.

And then as you go through the lines of
your program, you can start to update the

values of all those variables are going to
be.

Until eventually you get to the return.

And then that tells you what you should be
returning from this function.

This is basically how your computers
execute functions.

And we're going to make a circuit which does
this same idea for executing a function.

So the first thing that we're going to
need to do in order to implement this

function is we need to talk about how we
can actually represent our programs as bits.

We need to give the program as an input to
a circuit.

That means, since circuits
can only take bits as input, we

need to figure out how can
we represent a program as bits.

So in this case, the
program that we're going to

be talking about is going
to be NAND straight line.

The reason that we're going to
be talking about NAND straight

line is because it's equivalent
to something like AND or NOT.

It's universal, and
there's only one kind of

operation that we really
have to worry about.

We only have NANDs,
which is going to make things

really simple for us, or
much simpler at least.

We're going to start with a NAND straight
line program.

And we're going to come
up with a way to convert

that NAND straight line
program into a bunch of bits.

And the way that we're going
to do this is we're going to first

represent our program as a
list of triples of natural numbers.

We're just going to have triples of
numbers that represent that program.

And then we could take that triple of
numbers and maybe convert that to bits.

Because we know how to take numbers and
convert those into bits.

So this is our idea.

We are going to take our program,
written in NANDStraightLine, convert it to

a bunch of numbers, convert
those numbers to binary

strings, and now we have a
binary string for that program.

Every single line in a NANDStraightLine
program has this form where we have a

variable, and then we have
the equal sign, and then

we have NAND, and then
we have two more variables.

Every single line looks like that.

There's a lot of details that
are in that line that I don't

necessarily need to fill in, because
they're just always the same.

For instance, I could leave out the equal
sign.

And if I just had temp1 NANDAA,
then it would not be too difficult for us

to understand that temp1 was going to take
on the value of doing NAND on A with A.

That's sort of extraneous.

That's nice for readability, but it's not
totally necessary.

I could also get rid of the NAND.

If we're doing NANDStraightLine, NAND
is the only operation we're allowed to do.

So if I just say temp1 AA, then I could
just understand that the last two things

I'm doing a NAND on, and then assigning
that to the first thing.

So this means that I could do something
like rewrite OR as temp1 AA, temp2 BB,

return temp1 temp2.

We could easily understand that as exactly
the same program we started with before.

We could also get rid of
fancy meaningful variable

names, and I could just
number my variables instead.

So I could say that A is 0, and B is 1,
and temp1, well that's going to be 2,

and then temp2 is going to be 3.

This return thing, that's going to be 4.

So instead of having nice readable
variables, I could just number them instead.

If we number our variables and get rid of
the stuff that's just always the same,

we can represent each line of this program
as just three numbers.

This line becomes 2, 0, 0, which means I'm
going to assign as the value of variable 2

the result of doing a NAND with the value
of variable 0 with the value of variable 0.

And then this line says, I'm going to
assign as the value to variable 3 the

result of doing the NAND on the value of
variable 1 with the value of variable 1.

So essentially what we've done is we've
taken this table that we talked about your

computer sort of has while it's running
your code.

So we have this table where we've got the
variables and then their values,

and we're essentially saying each variable
gets a number.

And then we're going to end up having a
table where that table is going to

represent the value of the variables in
order of their number.

So this list of triples, we can think of
that as now representing OR.

All right, so all I've done is number the
variables and recognize that just listing

three variables in some
order, I can understand that as

being assigned to the first one,
the NAND of the second two.

That's how this works.

Yes.

So step one is we're going
to number each variable

where the first n
variables go to the input.

When we're going to be implementing this
function, so this function that's going to

be running programs for us, the function
is going to be this eval n, m,

and s, where n is going to represent the
number of input bits, m is going to

represent the number of output, and s
is going to represent the number of lines.

The reason we're doing
this is because since we're

using a circuit, it has
to be a finite function.

So we have to sort of pick the number of
input bits we're going to have in advance.

In order to actually write
down the function, we need to

know exactly the number of
input bits we're going to use.

Since we're giving the input that's going
to go to the program as one of the inputs

to the eval function, we
need to know how big the input

is, so we know how many
of the bits go to the input.

Since we're giving a
description of the program,

we need to know how big
the program is going to be.

We have to pick a size
of the program in order

to be able to take
that program as input.

Also, we need to know how many
bits we're going to be returning,

so we need to know the size
of the output of that program.

So we're actually going to have a slightly
different eval function for programs of

different sizes or programs with different
numbers of inputs or outputs.

So if you change any of
those one things, you're

going to need a different
eval program to do that.

The first invariables we're going to say
are like our parameters for this function.

Those are where the
inputs to the function

are coming from, are
the first invariables.

The last m, we're going to say those were
the output bits, the last m variables,

their values, you kind of concatenate them
together in order, and that's your output.

We can represent every single line of our
program as three numbers, and we can

represent the entire program as the number
of inputs, and then the number of outputs,

and then the list of the lines as our
triples here.

So these three things describe our program
for us.

That gives us exactly the same information
that we would get here.

So in this case, n is
going to be two, m is going

to be one, and then our
list of lines are over here.

So everything that was in the nice
Python-looking code is also present in

just this kind of triple, where one of the
triples is a list of triples.

So let's look at how we can do this with
XOR.

So with XOR, what is n?

What is n for XOR?

2.

We have two input bits.

What is m?

1.

We have one output bit for XOR.

What is s?

S is the number of lines that are in our
program.

So what is s?

S is going to be 4 in this case.

So now, let's look at how we can represent
our XOR as bits.

All of the variables that we're going to
see throughout need to go in our table.

So we have, for instance, A, we have
B, we have U, V, W, and then, like, return.

And now we're just going to give them all
a number.

So A gets 0, B gets 1, U gets 2,
V gets 3, W gets 4, return gets 5.

So now I can represent each of these lines
as a triple of three numbers.

So U is 2.

So the first number in this triple is
going to be 2.

That's the variable we're assigning things
into.

And which variables are we doing the NAND
on in order to make that assignment?

Well, that's A, which is 0, and then B,
which is 1.

So that triple represents the first line.

The next line, we have V, which is
variable 3, being assigned the value of

doing the XOR of A, which has value 0,
and U, which is variable 2.

And then W, well that's variable 4.

That gets the result of
doing the NAND with B,

which is variable 1, and
U, which is variable 2.

So this list of triples represents the
source code of that program, so to speak.

Okay, so now let's look at
how many bits it is that we're

going to require in order
to represent this program.

Yeah, so how many
bits does it take for me to

represent n in this
situation, where n is 2?

How many bits does that take?

Yeah, 2.

Yeah, piece.

So we're going to have the number of bits
we need to represent n, which is going to

be 2 bits for n, plus the number of bits
that it's going to take to represent m.

How many bits is that?

1, so that's 1 bit for m,
plus the number of bits

it takes to represent
all of my lines of code.

So this is kind of the complicated part.

How many bits do we need to represent all
of the lines of code?

Each line of code is going to be 3 numbers
long.

So we're certainly going to have a 3 in
here.

And then also, we have s triples that we
need to represent.

That's how we defined s.

So this is going to be 3
times s, times, and then the

number of bits we needed
to represent each variable.

How many bits do I need to represent each
variable?

Okay, so let's say
that I'm going to use the

same number of bits to
represent every variable.

Okay, so how many bits do I need in that
situation?

Yes.

It depends on how many variables I have.

What's the maximum number of variables I
can have?

Let's say that I have s lines.

What's the maximum number of variables I
can have?

So it's going to be s
plus n, because every

return is going to have
kind of its own line.

So the number of
returns is kind of going to

already be captured
by our choice of s here.

So we don't need to add in m, but we do
need to add in n, the number of inputs.

So it's the number of inputs plus the
number of lines is going to be that.

If the maximum number of variables I can
have is n plus s, how many bits do I need

to represent them if all of them are the
same length?

Yeah.

Yeah, so this is going to
now be the ceiling of the log

base 2 of n plus s is the
number of bits I'll need for that.

So if we have a set of n plus s things,
the question is how many bits are we going

to need to uniquely
represent everything in

that set with a bit
string of the same size?

So in this case that's going to be the log
of the number of things in the set.

So basically to summarize what we're doing
here, the first thing that we need to do

when we when we represent our program as
bits, we're going to need a number each

variable so each variable gets some sort
of number.

The number of variables,
so the number of variables,

we said was going
to be equal to n plus s.

So we're going to have n plus s variables
in here.

So that means that to number
each variable, we're going to

need the ceiling of the log
base 2 of n plus s bits each.

And then we're going to represent each
line as three numbers.

So we have 3 times s times the length of
the variables for that.

So 3 times s times however long our
variable representation was.

We have s lines, each
line had three numbers, and

we needed log base 2
of n plus s bits per line.

And then we can represent our program as
n, m, and then that list of lines.

And this is going to be 2 times the log
base 2 of s.

If we work all of this out, we know that
an upper bound for the size of our program

is going to be... we'll just round this to
4s log s.

We can just get rid of this and things are
still going to hold.

You can do sort of the arithmetic on your
own if you want to.

But if you look at like the fact that n is
going to have to be less than or equal to

s, because we can't have
fewer inputs than lines if

we're going to have all of
the lines depend on the input.

Right?

If we have all of the lines... if we have
every... or every input be used in the

body of the function, then we need to have
at least as many lines as inputs.

So if we make that assumption,
then basically we can say that an upper

bound for s of s is
the size of the program

of s lines in bits is
what s of s represents.

We can say that an upper bound for that is
basically 4s log s.

Something like that.

Yeah.

The book is going to have more details.

I'm trying to gloss over some details.

But what what we're going to work with for
now is that the number of bits required

for our program is going to
be upper bounded by let's say 4

times the number of lines
times log of the number of lines.

Intuitively, this is going to be
approximately what our answer ought to be.

We're going to have like three numbers per
line.

There are s lines.

And then we're going to have about log s
things per line.

And then there's some extra noise we had
in there.

So what I did is I just
increased that 3 to a 4

to account for that noise
and make things easy.

IC3