---
Video Title: Self-Rejection (An Uncomputable Function)
Description: Theory of Computation
https://uvatoc.github.io/week9

18.2: Self-Rejection
- Defining a Language/Function
- The Self-Rejecting Language
- Proof that Self-Rejecting is Uncomputable

David Evans and Nathan Brunelle
University of Virginia
---

Is there any interesting number that can't
be computed?

The fact that our machines
can't compute every number

shouldn't bother us because
most numbers aren't uninteresting.

We should only be sad if there are things
that we care about that we can't compute.

And numbers probably... at least it's
unclear if that's the case.

But functions... well, we know what
interesting functions are.

Maybe we can think of some function or
describe some function that can't be computed.

So that's the question that we want to
focus on.

We know that there are some that can't be
computed.

Just by this simple cardinality
argument, the number of.

Turing machines isn't enough
to compute all the functions.

So we're going to start looking for a
specific function that can't be computed.

What we're going to do
first, we're going to define a

function that maps a
description of a Turing machine.

It's going to take a string.

So w is any finite binary string.

And either that's a valid description of a
Turing machine.

We'd have to specify carefully how we
write down our Turing machines.

But based on however we specify that,
some machines are going to be valid,

some machines are not.

And what we're going to produce,
if it's a valid description, we're going

to produce the machine that that
represents.

If it's invalid, well
then we're going to

produce this special
machine, which is this.

This machine is just one state,
no transitions, empty transition function.

So what does this machine do?

Our rules of how to execute a training
machine say...

So we start in state zero,
tape index zero, and we

look up our transition
function for what to do next.

What's going to happen
with this machine when we

look up our transition
function for what to do next?

Yeah, it's undefined.

The transition function is a partial
function.

We haven't defined a total function.

So we need to reconsider a little bit and
at least be more careful.

Our step here assumed that we always get
an output from our transition function.

It assumed that it's a
total function, or at least

it's defined on all the
things that we evaluated on.

But in this case, it's not.

The way that is dealt with is to say,
well, if you get in some state and your

transition function is not defined,
then you're stuck.

The machine doesn't produce a value.

It's like if you ran forever.

So we need to be a little more careful how
we define our machines.

So what we're going to say is,
if our transition function is not defined,

if we ever encounter an input where it's
undefined, then we're going to stop

execution and our output is this bottom
symbol, which means there's no output.

Okay, so now we know what this machine
does is it rejects everything.

It's going to get stuck.

It never produces an output.

But it's a very rejecting machine.

The other thing that is going to help us
to think about these things is to get

comfortable switching around between
functions and languages.

The two can be viewed as essentially
equivalent.

So we're going to define a language of a
machine as the set of strings where the

output of that machine on that string is
one.

We've got the set of all binary strings.

We're going to define the
language as a subset of

those strings where the
output of the machine is one.

And that's the language of that machine.

Can we go from a function to a language?

We just need to
evaluate the function on all

of the inputs that it
could be evaluated on.

And that defines the language.

Of course, we don't actually have to
evaluate it.

That's how we're defining it.

So now we can define a
language that is the language of

strings that the machine that
we've defined here outputs one.

So we've got a machine described by some
input string.

And now we're going to define the language
the way we did it.

So that's the set of all
strings where evaluating

that machine results
in one as the output.

And now we're going to define a new
language, which is all the strings where

the machine that
that string defines, the

language of that machine,
does not include itself.

That means that if we ran that machine on
the string that described that machine,

it would not output one.

It might output something else.

It might run forever.

It might get stuck.

It doesn't output one.

This should start to seem pretty strange,
what we're defining.

We will get to see why
this is interesting and why it

helps us see lots of other
functions that we can't compute.

We are defining a function that takes in a
string.

So any finite string of zeros and ones,
that's our sigma here.

We're going to produce the Turing machine,
right?

The output of the fancy M function is a
Turing machine.

And it's either the Turing machine that
that string represents.

If that string represents a valid Turing
machine, the result of the fancy M

operating on that string, this is a
function that takes a string as input,

is a Turing machine.

That is the one that W describes.

So for us to actually define
what fancy M does, we'd have

to find some specific way to
write down a Turing machine.

So each of our transition rules is from a
state and an input to some other state,

could be to the same state, to what we
write on the tape in a direction.

And when we write them,
or we draw machines,

we use all sorts of
symbols and funny notation.

So if we're going to describe a Turing
machine with a string of just zeros and

ones, we'd have to have some way to convert
that into just a string of zeros and ones.

Maybe that's what it converts to,
that rule.

I don't know what it should convert to.

But you can come up with some way of mapping
the rules to strings of zeros and ones.

And some of them are going to represent
valid Turing machines, some of them are not.

If we tried to come up with a mapping that
could only represent valid Turing machines

with every string, that would be really a
pain, maybe not even possible to do.

But it's easy to just say, well,
if it is a valid Turing machine,

this fancy M function produces the machine
it represents.

If not, we still need to output a Turing
machine, because we want the M function to

be defined on all strings, so it's a total
function.

We're going to just output a machine that
rejects everything.

Whatever input it runs on is always going
to reject.

If we want to describe
machines, so now we've

got a machine
represented by this string w.

Here's our string w.

That machine defines a function.

And we can write that function down.

That's just a lookup table.

So on every input string, we can order the
input strings.

We have some way of ordering the strings.

How can we represent the function?

We can just look at its output on every
one of those strings.

So if the machine represented by 0,
1, 0, on input, empty string, outputs a 1,

we could put a 1 here.

If it does something else, we could put a
dash there.

Or we could put checks in the ones where
it outputs a 1.

Either it accepts the input or it doesn't,
there's two possible outcomes.

Either it accepts it or not, and we'll put
a check in the spaces where it accepts.

So we can do that.

We can imagine we've got some table like
this.

It's an infinite table.

There's unbounded length of the binary
strings.

But each one of these we can write down in
this table.

It's defined on infinitely many inputs,
so it's not a finite function.

For any likely encoding,
all of these small

strings, what are they
actually likely to encode?

Yeah, they're probably all reject
machines.

At a minimum, to represent a Turing
machine, we need to list the alphabet,

we need to say the number of states,
and we need the transition function.

So probably, if our W string is three
symbols long, we don't have space to do that.

We'd have to have a really strange
encoding.

But I don't have room to show a table with
hundreds of entries, so let's assume that

these are valid Turing machines, and
some of them, like these are rejecting.

These might be the reject
machines, at least what

we see, assuming there's
no checks anywhere else.

And some of the other ones are accepting
some strings.

So that's our table of machines.

We can think of all the Turing machines
there are, represented by some string,

and we can look at that machine as a
function on inputs.

Each input is a finite binary string.

Okay.

So now let's define the self-rejecting
language.

What the self-rejecting language is,
is the set of strings where the language

that the Turing machine, described by that
string, does not include itself.

So that's why it's called self-rejecting.

W is here, we're looking at that input as
a weight-encoded machine.

That machine has a language.

And to be within the
self-rejecting language, that string

should not be in the language
that its own machine describes.

Does it seem useful?

Probably not for anything
other than proving

something, getting
some kind of contradiction.

Well, unless you're really into rejection.

But it's a perfectly valid language.

And we can define it.

We can also define a function.

We said what a language is, the set of
strings where the function outputs one.

So what would the self-rejecting function
look like?

If we wanted to think of this as a
function, how would we do that?

So what are its inputs?

Languages are sets.

Functions have inputs and outputs.

What are the inputs to the self-rejecting
function?

Yeah, it's just a string.

It has one input.

That's a string.

Like, we use w to represent it here.

It's a finite binary string.

And what its output should be is,
well, we're going to run that machine,

the machine that that string represents.

This is a Turing machine.

What are we going to do with this Turing
machine?

So we want to run that Turing machine on
some input.

The input we're going to run it on is the
input w.

The way we wrote that was kind of like
this, right?

We're running this Turing machine on this
input.

If it produces a one, what should we do?

What should the output of self-reject be?

If running the Turing machine described by
w on w produces a one.

Yeah.

We should negate it.

We should flip the result.

So it's going to be something like this.

If we assume not, it flips everything else
in the right way.

Got to be defined on
more than just booleans,

because the output
of this is some string.

But that's basically what it does.

We're defining our self-rejecting function
as takes the string as input, and it

outputs one if the Turing
machine defined by that string

running on that input does
not accept, does not output one.

This M is this function.

It means make a Turing machine described
by that string.

The other M is the one that we defined
last class.

This is the evaluation.

M of X is the result of evaluating a
Turing machine on input X.

That's what we defined in our execution
model.

What we're defining as the function M of
X, the machine running on that input,

is the output of that machine as defined
by this process.

This is actually the wrong
one because this is the no input

machine, but we also define
the one where it's running on X.

That means what's here is we're running
the Turing machine that the fancy M

produces, which is basically the Turing
machine that that W string represents.

Now we're running that machine on input X,
which in this case is W.

Yeah, it's a little bit of a confusing
notation with the two M's.

So we've defined self-rejecting language.

How do we identify
the strings that are in the

self-rejecting language
by looking at the table?

Is there an easy way to do it?

Yeah, it's going to be on the diagonal.

If the diagonal is empty, we are in
self-rejecting.

If the diagonal has a check, we accepted
ourself.

We are not in self-rejecting.

Anyone bothered by this yet?

Going down diagonals, if
you remember, some of our

accountability proofs might
start to worry you a little bit.

But so far it looks pretty good.

If we can compute self-rejecting,
that means there's some machine that

represents the Turing machine that does
self-rejecting.

There's some Turing machine that can
decide this language.

And that means that the machine
corresponding to that string, so there's

some string, which must
be somewhere in this

table, that computes the
self-rejecting language.

And it must be somewhere in that table.

Okay.

So what should the value on its diagonal
be?

We're going to have some string.

So we'll call MSR is the machine that
computes self-rejecting.

And that means there's some way to
represent that machine.

We'll call that WSR.

That's some string of zeros and ones.

So is it in self-rejecting?

So we have two options.

This is a binary question.

Either it's in the set or it's not.

So which one do we think it is?

So could this be true?

Could it be in the language defined as
self-rejecting for its own machine?

What it means to be in that language is
that... this is coming straight from here.

It means that it's not in the language of
the fancy M of WSR.

What is fancy M of WSR?

Well, we pick WSR as
the input that represents

the machine that would
compute this language.

I'm being a little cavalier with my terms
about compute and recognize and decide.

We haven't defined those quite formally.

And we've mostly been talking about
functions.

So we're going to try to use compute.

The equivalent of compute is to decide a
language.

That basically means we can say for every
string, yes or no, is it in the language?

But that's what we define.

This is the machine MSR.

So is this okay?

This is WSR.

Well, that's not okay.

We started option one by saying it is in
the language of MSR.

So it better be option two.

We've excluded option one.

So option two, well, we tried being in it.

The only other option is to not be in.

So if it's not in it, that means it's not
in self-rejecting.

So it is negating this in this language.

These are the opposite of each other.

We have a contradiction.

Neither option makes sense.

Both lead to saying that something's both
in and out of the same set.

What do we do?

Something must be wrong.

Well, what's wrong?

We assume something that's not true.

We assume that the
machine that computes the

self-rejecting language,
we assume that that exists.

We've got a contradiction.

It cannot exist.

There's no machine.

We didn't put any other constraints on the
machine.

We just said there's some
Turing machine that can

decide this language or
can compute that function.

And that leads to this really clear
contradiction.

So that assumption must be wrong.

And that means this must not exist.

So we have a function that cannot be
computed by any Turing machine.

It's a pretty big result.

We said we were going to get to an
interesting uncomputable function.

Are we satisfied?

Have we got to something that we think is
interesting or is self-rejecting kind of a

nice way to see something that's
uncomputable?

It is a specific one.

It's not just saying the cardinalities are
bigger, so there must be one.

It is a specific one.

But maybe it's not an interesting one.

But we have proved there's an uncomputable
function.

But we want to get to something
that seems more interesting

than self-rejecting as our
uncomputable function.

Before getting to that, we're going to get
to universal machines.

Let's do this.

Let's do it.