---
Video Title: Beyond Finite Functions
Description: Theory of Computation
https://uvatoc.github.io/week6

12.3: Beyond Finite Functions
- Unbounded Model of Computation
- Introducing Finite State Automata

Nathan Brunelle and David Evans
University of Virginia
---

We've mentioned functions
that are going to work

for strings no matter
how long those strings are.

The main limitation we had with the only
model of computing we've discussed so far,

which is the circuit-based model of
computing, the key limitation for that was

that all of our inputs had to be a
specific size per implementation.

So we could not, for instance,
compute this infinite XOR where we said,

are there an odd number
of ones in this string where

the string is whatever
length you care for it to be?

We could only do XOR of exactly 8 bits per
one implementation.

If I wanted to do XOR for
9, I've got to come up with

an entirely new implementation
of that XOR function.

So Boolean circuits, they
have this drawback of you have

to have a fixed number of
inputs per implementation.

What we really want, though, is I want to
be able to do something like this infinite.

XOR, but that means that I
need a new model of computing

that's essentially going to
take infinitely many inputs.

One of any infinite number of inputs.

So we no longer want to have finite
functions.

Finite functions are those where there's a
finite domain.

The domain of that function is a finite
set.

We want to have infinite functions where
the domain is an infinite set,

meaning any one of
infinitely many inputs could

be used as the input for
this model of computing.

So that's sort of the next step that we're
going to take.

We're going to move beyond these Boolean
circuits and end up with a model of

computing that we can use to do some of
the functions that we had discussed.

So an example of one of these infinite
functions is this infinite XOR,

where what we're going
to do is I want to define an.

XOR that can take any
unbounded number of input bits.

So this XOR that can take any unbounded
number of input bits.

So we can take any string
of ones or zeros as input,

and we're going to produce
a zero or one as output.

We can think about this as a decision
problem or a language.

Because it is a function
that returns just zero or one,

we can also think about
it as the decision problem.

Are there an odd number of ones?

Or the language, all the strings with an
odd number of ones?

So what we'd like to do
is we'd like to have some

model of computing where
we can do functions like this.

Where we have any number of input bits
that you want to hand me, that same

implementation is going to be able to give
me the right answer for all of them.

With programming languages, they allow us
to do this sort of thing.

You write one program,
and that program is going to

work no matter how big the
input was that you gave it.

Like, you could write a
program that took as input

maybe a string or a list
or something like that.

You could write programs in
your programming language that

would compute some function
for any list of any length.

And the way that programming languages
manage this is they add loops.

So loops in programming languages,
those are the things that allow you to do

this behavior, that allow you to do
infinite functions.

So the idea for how it is that we actually
do infinite functions ...is we just add

some sort of mechanism for repeating
things over and over and over again.

Where the model does not itself limit the
number of times that can happen.

And the way that we're going
to represent this in hardware

is we're going to use some
idea called an automaton.

The plural in this case is automata.

Basically, the way that these work,
they're kind of like hardware,

where you've got some sort of state that
you're in.

So maybe you've got a
register in your memory,

or some small amount
of memory or something.

And there is some contents of that memory.

We're going to call that the state of the
memory.

So you've got some sort of state of your
memory.

And then over here, you've got some finite
function.

And what we're going to
do is this finite function is just

going to update the state
over and over and over again.

So this is basically the way that this is
going to work.

We're just going to say the loop that
we're going to add is we have state,

And we have one finite function that can
transform that state over and over and

over again until something happens that
tells us to stop.

So this is how we're going to be able to
do these infinite functions.

Because we're going to say that we can
repeat this any number of times,

we're not going to bound the number of
times this could repeat, that's going to

allow us to, for instance, do this
iteration more times for longer inputs,

and that's going to be
the thing that allows us

to start to do some of
these finite functions.

Just like loops do in our programming
language.

I'm going to start by sort of at a high
level describing one example of an

automaton that we could use in order to
compute these infinite functions.

This kind of automaton, we're going to
call that a finite state automaton.

So we're going to talk about what are the
components of that.

So what does an implementation look like?

And also what does an execution look like?

So just like with any of our models of
computing, we need to give rules for what

an implementation looks like and how you
execute that implementation.

We're going to have these two components
here.

First of all, let's talk about the
definition here.

Let's talk about the vocab.

So this is called a finite state
automaton.

The reason this is called a finite state
is because that memory that we had that

would have some sort
of state to it, there are

only going to be a
finite number of options.

So there's a finite number of
options for kind of the status

that our program could have,
the state our program could be in.

Depending on the input, so for different
inputs, we're going to differently change

the state as we kind of read through our
inputs.

So different inputs will
cause us to update that state

differently among those finitely
many options, is the idea here.

So the components of a finite state
automaton.

First of all, we're going to define a set
of states, a finite set of states.

The variable name we're going to give to
that is capital Q when we see it later.

So we're going to have some finite number
of states, where one of the states among

that finite number of states, we're going
to call the start state.

We typically denote that as
Q sub zero, and that needs to

be an element of a set of
all of our finitely many states.

We identify one of the states as our
special start state, the state that our

execution is in before we ever do
anything.

We're also going to have a subset of the
states that we call the final states.

So whether or not a
state is final is essentially

going to tell us how
to give an answer.

And then we're also going
to have our transitions, the

rules for how we go from
one state to a different state.

So this is going to be that finite
function that we have, these transitions,

where basically it's a function where I
hand it the state that our program is

currently in, and I give it
a character in the input,

and it tells us what the
next state ought to be.

The way that the execution works for one
of these automata...

So we begin in that state that was the
initial state, that was that start state.

And then we're going to take our input,
whatever input was given to this machine,

and we're essentially just going to have a
for loop for this string.

We're going to say, for
each of the characters in this

string, we're going to read
them once, no looking back.

And for each of those
characters, we're going to use our

transitions to go into some
new state once per character.

So using the current state that we're in,
plus the current character of the input in

that for loop, We're just going to pick
some new state.

And we're just going to do this over and
over and over again until eventually,

once we've read through the
entire character, we're going

to give some output
depending on what state we're in.

So if that state
belongs to f, then that

means that the answer
should be equal to one.

Otherwise, the answer is going to be equal
to zero.

So we're going to be computing one of these
Boolean functions, some Boolean function.

And the way we're going to
do that is we, one character

at a time, read any
string that you hand to me.

And using that string in the current state
of our system, we pick some new state.

And then once I've done that for all of
the input characters, I say, was I in a

final state versus was I in a non-final
state?

And that tells me whether the answer
should be one or zero.

Yeah.

If it's an element of f, then the answer
is one.

Otherwise, the answer is zero.