---
Video Title: Introducing EVAL
Description: Theory of Computation
https://uvatoc.github.io/week4

8.4: Introducing EVAL
- From "Any" to "Every"
- Introducing a Universal Function

Nathan Brunelle and David Evans
University of Virginia
---

So we just showed that
we can do any function

with our circuit, but we
need to pick which one.

So rather than being forced to
pick one, what I'm going to do

is I'm going to write a circuit
such that I don't have to pick.

So in order to implement
my hardware, I need to pick

a function because I don't
want to be nailed down.

I'm a free spirit and want to be able to
roam with my whims.

I'm going to pick some circuit that allows
me to do every circuit.

I can do any circuit at all that I might
want.

So why not pick to implement
the function that allows

me to implement every
function of a certain size?

So that's what we're going to do next.

So we can compute any in-bit function
using circuits or straight-line programs.

What we want is we want a machine that can
compute every in-bit function.

So the way that we're going to do this,
in order to have really, really general

hardware, the way we're
going to do this is we want to

define a function that's going
to simulate other programs.

That is, I want to have a program where if
I hand you a program of a certain number

of inputs, outputs, and lines,
you're going to be able to tell me what

that program is going to output for a
particular input.

So any says every option is available to
us.

We have to pick one.

The one I'm going to pick is one that
allows me to do every function I hand to it.

So what I mean by
this is I'm going to define

a function that
simulates other programs.

So by doing this, since I could write any
of these functions as a program,

that one circuit can do every program.

So I can do every function I had in mind.

Keeping in mind, the program
that I write is going to have

to be a little bit bigger than
the program that I simulate.

To give an idea for how we
might do this, let's actually

look at how programs get
run on your computer a little bit.

So what actually is your computer doing
when you run a program?

Basically, what your
computer does is it's going to

have some table that
represents all the variables.

Typically, you hear
it referred to as like

the stack or the heap
or something like that.

You've got some memory
that your computer has that

keeps track of all of the
variables and their values.

And then as you execute your code kind of
line by line in sequence, your computer

updates the values of all of those
variables as your instructions dictate.

So you execute your code while executing
your code.

You update the values in the table until
eventually when you're done, one of those

values in your memory is what you end up
returning.

At a super high level, this is what your
computer does when it runs a program.

We're going to do the same thing.

We're going to write a
NAND straight line program

that is basically going
to do that same thing.

So first of all, let's look at an example
of what your computer is going to do.

So let's say that I have this program for
XOR.

I've got a NAND straight line program for
XOR.

What the computer needs
to have is it needs to have

this table where it's got
every variable in the table.

So in this case, we have
1, 2, 3, 4, 5, and then we're

going to say the return
is the sixth variable here.

What are our variables?

We have A, B, U, V, W, and return.

And as we execute our
program, we're just going to

assign each of these
variables the value that it needs.

For instance, if I run this input on,
let's say, 0, 1, we start out with A and B

being defined, because those were my input
variables.

And then the next thing we do is we figure
out what should the value of U be.

Well, U is the NAND of A with B.

So A NAND B, that is 1.

And then the next thing we do is we figure
out V.

What is V?

Well, V is the NAND of A with U.

So that's 0 NAND 1, which should be 1.

And then what is W?

Well, W is B NAND U.

So what is that?

Well, that's 1 NAND 1, which is 0.

And then we're going to return V NAND W,
which 1 NAND 0 is 1.

So our return value is 1.

So this is essentially what your computer
is going to do while it's doing XOR,

this implementation of XOR.

If we can figure out a way to represent
our program as a bit string, and we can

figure out a way to do this
table updating thing with

just NANDs, then we can
simulate any program at all.

So this procedure that I just described,
we're actually going to be able to write a.

NAND straight line program that does the
same thing as that procedure.

For every single line in the program, we
sort of update the value in that memory.

And we're going to see that we can
simulate that program.

So the first thing that we're going to
need to do in order to actually simulate

our program is to figure out how we can
represent our program as bits.

We're going to define this function that
I'm going to call EVAL.

We're going to hand it a description of a
circuit or a description of a program and

an input, and it's going to evaluate that
program for that input.

It's going to do the same thing that that
program did on that input.

So eval is going to be parameterized based
on the size of the program.

We're gonna have a different
eval function depending on

how big the program is that
we're gonna try to simulate.

And we're gonna be handing it,
the program, as the input.

We can only do programs up to a certain
size, is the issue here.

So in this case, essentially, what eval is
gonna be doing, is we're going to give it

as input a string representing a program
plus Plus the input values.

And its output is gonna be the result of
running the represented program,

the program we represented with those
bits, on that input.

We hand it the program
and the input, and it gives

us what that program
would return on that input.

So, this s represents the program size.

We're gonna show that, no
matter what your program length

is, we can find a function
that's gonna work for that.

We need the number of inputs.

So this eval function is only going to work
if you have the proper number of inputs.

We're going to say something like,
this is the eval function that will

simulate any 27-line program that's got 8
input bits, or something like that.

And then we're also going to need the
outputs here.

So we're going to be defining
a function, this function eval,

or if we said we had eval
27, 8, 4, or something like that.

This is a function where no matter what
program I give this function as input,

so long as it is 27 lines long,
has 8 inputs and 4 outputs, that eval

function is going to
be able to simulate the

behavior of that program,
is what we're going to do.

So next class, what we're
going to do is we're going

to talk about the details
of this eval function.

We're going to talk about how this could
work, how it is that we can represent

programs as bits, and
exactly all the pieces

for how we can do
this table simulation.