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

12.2: Functions and Languages
- Decision Problems
- Languages
- Relationship between Functions and Languages
- What languages can computers recognize?

Nathan Brunelle and David Evans
University of Virginia
---


So we've been talking so far about trying
to find formal definitions for what it

actually means to compute something,
and very early on in the semester,

we gave one idea for what it looked like
to compute things.

And in order to have a vague idea of what
it looked like to compute things,

we had to say, what is a thing that gets
computed?

So before we could talk about what it
meant to compute something, we had to say,

what is the type of thing that we might
compute?

And we started by saying, well,
that type of thing that we might compute,

that was going to be taking a string as
input.

Why did we take a string as input?

Why did we like strings?

Yeah, because pretty much
anything that we could ever

want to write down, we
could represent with a string.

Our English language is sort of built on
strings.

We have text with characters that can be
strings.

So basically, anything
that humans can think

about, we can write
down as a string somehow.

So we liked strings for that amount of
generality that we had.

We could use strings to represent music or
numbers or anything that we wanted.

If we can have a model of computing that
operates on strings, then so long as we

can figure out how to represent the actual
thing we want to compute on as a string,

then we can compute on whatever we'd like.

So we said that the things that we
computed was going to be some function

that took a string A string is input and
produced a string is output.

The strings, we say, are going to be some
sequence of characters.

Those characters are drawn from some
alphabet.

And this alphabet is always going to be
finite, in our definition of a string.

There is always a finite number of things
in our alphabet.

So, somebody asked this question on the
previous slide.

Is it a finite alphabet?

The answer to that is always yes.

So this is a yes or no question for which
the answer is never no.

We want to compute
some function that takes

strings as input and
produces strings as output.

This sigma star here says zero or more
things from the alphabet.

A sequence of zero or more things from the
alphabet.

So sigma star was sigma to
the zero power, union sigma

to the one, union sigma
to the two, and so forth.

Sequences of zero or more things from the
alphabet.

And for circuits, we
in particular talked

about the alphabet
being bits, zero and one.

And then we were restricting the input and
output size to be a fixed size.

So when we had the star, that meant any
finite length string, as opposed to when

we put like the n here, that means only
these fixed length strings.

So that's what we've been working with so
far.

We're going to expand this a little bit
next.

So these are different ways to think about
what is the same thing.

But there's going to be
some advantages to thinking

about what we're computing
in a slightly different way.

So it's going to be equivalent to what
we've talked about so far.

But we're going to think about it in a
slightly different way.

When we have a function that computes on
the domain of strings, And then the

codomain is bits like true or false,
or 0 or 1, or something like that.

We call those decision problems.

This particular kind of function,
where our input is going to be whatever,

whatever string, and
our output is going to be

either 0 or 1, we call
those decision problems.

Because we're just trying
to essentially decide whether

or not the given string is
going to have some property.

Any question for which there is a yes or
no answer, any question of strings for

which the answer is yes or no,
we call that a decision problem.

So functions where the output is Boolean
or binary.

All of these questions that we asked up
here, all of these are decision problems.

Because we're asking a question about a
string.

So we can think of each of the questions
up here as a function.

Where what our function is going to do is
it's going to accept some sort of string

as input, it's going to take in some sort
of string as input, And provided the

answer to whatever
question we asked was yes,

it is going to give as
the result true or one.

Whenever the answer was no, it's going to
give as the result zero or fault.

We call these decision problems.

Most of the functions that
we've been talking about

so far have secretly been
decision problems all along.

We're also going to be talking about
another slightly different idea,

which is this idea of a language.

A language is just a set of strings.

So a language in this context is just a
set of strings.

And in particular, we define
a language by saying the

property that all of those
strings are going to have.

So a language is some set of strings.

This is different from what you might
think of as like a spoken language or a

programming language, where a language is
maybe a bunch of vocab words plus the ways

that you arrange them together to make
meaningful statements.

What we're going to be talking about here
when we refer to the word language in this

context as something
that we compute, we're

essentially just saying,
this is only the vocab.

You hand me a string
and I just want to know,

is it one of the words
that's in my set?

A language is just some set of words.

All of these things are sort of related to
one another.

Functions, decision problems, languages,
and so forth.

Any of the things we've discussed so far,
we could think about them in any of these

contexts, and we'd get basically the same
properties.

So for instance, I could look at XOR,
and we could think of the generalized XOR.

So an XOR, where I can hand it any number
of inputs I want, rather than just two.

You can think of it as a binary string of
arbitrary length.

And the decision
version of this might be,

are there an odd number
of ones in the string?

So XOR for an arbitrary number of input
bits should return one whenever the number

of ones was odd, and it should return zero
whenever the number of ones was even.

So to express this as like a
decision problem, we're asking

this yes or no question, are
there an odd number of ones?

And if I were to represent that as a
function instead, this would be a function

where we'd take some bit string as input,
and we'd say that the output should be

zero whenever the
number of ones was even,

and one whenever the
number of ones was odd.

Or I could think of this same
thing as a language, where

I said it's the set of all
strings from sigma star.

In this case, sigma would be equal to zero
and one.

So it's the set of all strings from sigma
star, such that that string has,

oops, an odd number of ones.

Or if we talked about majority,
I'm going to give you a bunch of bits,

and I want to know if I gave you more ones
than zeros in my bit string.

So that was this majority function.

So as a decision problem, it asks, of this
string, are there more ones than zeros?

As a function, it could be something like,
the function returns zero if the string

has more zeros than ones, or the same
number as, as more or equal.

Or it returns one if there's more ones
than zeros.

I could think of this as a language by
saying it's the set of all strings,

such that that string has more ones than
zeros.

In general, if I have some thing to
compute, so if we have, like, this is a

thing to compute, if we're asking the
decision version of this idea,

of the idea of the thing
we want to compute, this is

going to be, like, a yes-no
question about strings.

So the decision problem is a yes-no
question about strings.

We could think of it as a function by
saying it's going to be some function f f

that goes from a string to 0, 1,
where the 0 case is the answer equals

false, and then the 1 case is going to be
the answer equals true.

Or we could think about this
as a language by saying it's

the set of all the strings,
such that f of b equals 1.

So it's the set of all strings where the
answer was yes or the function returned 1.

So for anything that you might have in
mind that you want to compute,

if you can think of it as a yes-no
question, then you could think about it as

a function that gives a boolean output,
or as a language where the things in that

language were all of the strings where the
answer was yes.

This means that we could
think of XOR as being the

language of all strings
with an odd number of 1s.

We could think of majority
as being the language

of all strings with With
more ones than zeroes.

If we go back to this cover page,
I could talk about this question.

Is it at least seven characters long?

Is the string at least seven characters
long?

So as a language, that
would be the set of all

strings that are seven
or more characters long.

So that's what that decision problem would
be as a language.

This is it empty?

How many things are in
the language that we can

associate with this decision
problem, is it empty?

How many strings are in that language?

Yeah, one string.

What is that string?

Yeah, the empty string is the only one for
which the answer here is yes.

So in that case there is but one string in
that language.

Yes.

You can have infinite languages.

For instance, how
many strings are in this,

is it at least seven
characters long language?

There's an infinite number of strings in
there.

So I can't just exhaustively
say, is this equal to any

of the strings It's in that
infinitely long language.

We have to do something else.

And that's where computing really starts
to get interesting, is when you start

saying, there's an infinite number of
possibilities here.

When there's an infinite
number of possibilities,

how do I know that
I'm looking at one?

You can say pretty much anything there.

It's very open-ended what you're allowed
to fill in the blanks with, and that is

powerful because you can now use this idea
of a language to talk about lots and lots

of different computations or things that
you might want to compute.

However, it also means that you can very
easily get yourself saying nonsensical

things or things that are
way more complicated

than you might have
anticipated before.

Some of the things that
are on this slide, you're

not going to be able
to do with a computer.

Some of the things you are going to be
able to do.

For instance, is this program going to
halt?

That is something that
you could never have a

computer determined for
you in the general case.

Is the program eventually going to print
high?

That is something that
you could also never

write a program to
do in the general case.

So some of these are pretty easy to
compute.

Some of them are hard to compute.

The idea is that this construct of a
language is just a quick way of describing

a computation that is very related to what
we saw as functions.

And this is going to be handy going
forward.

So for much of the rest of the semester,
we are sort of going to be talking about

languages as the thing that we are
computing.

But know that when we
are talking about languages,

they have this
relationship with functions.

When we say to compute a language,
we are really saying I want to compute

this function that returns
zero for the things not in the

language and one for the
things that are in the language.

So that is largely what we are going to be
working with going forward.

And that is not very specific.

Thank you very much.
I will charge the language to do capacit
for these things.
And of course get my grades here.
I will charge for that.

Take琳.