---
Video Title: Finite is Undecidable
Description: Theory of Computation
https://uvatoc.github.io/week10

19.5 Finite is Undecidable
- The Finite_TM Language
- Proof by Reduction that Finite is Undecidable

Nathan Brunelle and David Evans
University of Virginia
---

So let's do another example.

So let's say that I want
to ask this question, is the

language of some Turing
machine a finite language?

So is the number of
things that's accepted by

that Turing machine a
finite number of things?

Are there only finitely many inputs for
which we return one?

So you give me a Turing machine
description m, we're going to return true

if the number of things that machine
accepts is a finite number of things.

We are going to return false if it was an
infinite number of things.

This one, it turns out, is going to be
non-computable as well.

This is another non-computable function.

We are going to use a reduction to show
why.

And the way that we are going to do that
is we are going to reduce some language we

already knew to be impossible,
to be undecidable, to finite.

In this case, we are going to use halt.

So, we are going to use finite in order to
solve halt.

So, if we had a program
that could do finite for

us, we could build a
program that would do halt.

Since we just proved
that halt was impossible,

that must have meant
finite was impossible as well.

So, that is what we are going to do.

So, we are going to be showing that finite
is at least as hard as halt.

That is, we are going to reduce halt to
finite.

The arrows point in opposite directions
for reduce versus hardness.

I know that's confusing.

I'm sorry.

There's nothing I can do about that.

This was decided like 40 years ago.

Probably about 50 years ago by this point,
actually.

Anyway, the idea is, let's
say that we're given some input

where we are asking this
halt question on that input.

On the MW pair, M is a machine
description, W is an input string.

So for this instance of halt, so for this
machine input pair, where we wanted to

answer this halting question
about that machine and input,

we're going to use those to
build a brand new machine.

Let's call that M prime.

And the idea of this machine M prime is
that by answering the finite question of

this machine M prime,
that's going to give us

the answer for the halting
question for M and W.

So we're going to use M and W to create
this new machine M prime, so that if I

could answer the question of whether or
not the language of M prime was finite,

then that was secretly the answer for
whether or not M halted on W as well.

More specifically, how we're
going to define M prime is we're

going to say that if M halts
on W, I have this backwards.

If and only if M on W runs forever.

Okay.

We're going to define this
machine M prime so that its

language is the empty set
if and only if M runs forever.

So whenever M ran
forever on that input W, the

language of M prime was
going to be the empty set.

So it's going to reject everything.

So we're going to reject everything if M
runs forever.

We're going to accept everything if M
halts.

So reject everything if M runs forever.

Accept everything if M halts.

So the language of M' is either nothing, or
the language of M' was equal to everything.

It's going to be one of these two.

Which it actually is depends on the
behavior of M on W.

Notice that when it's nothing,
the nothing language is finite.

It has a finite number of things in it,
that being zero.

The everything language is infinite.

Because it has all infinitely many bit
strings that belong to that language.

So that means that if I knew whether or
not this language was finite, I knew

whether or not it was going to be nothing,
so I could tell you if M halted on W.

So let's see how this works.

Here's some pseudocode for what I'm going
to do with M'.

We're going to talk about this in the
fashion we saw before in a moment.

But this is the pseudocode for what things
are going to look like.

Let's say that I'm trying to write this
function that's going to solve halt.

So that's my goal.

My goal is to write a function that solves
halt.

So I'm trying to do def halt on M and W.

So that's my goal.

To fill in the body of this function to
solve halt for me.

This machine here.

So you can write Python programs to create
other Python programs.

Has anybody ever done that before?

Written a Python program that would write
another Python program?

Okay, a couple of you have.

How many have written a Python program
that would write some other program,

potentially in a different programming
language?

Okay, a few more of you have done that.

This is something that I do all the time.

I'll write Python programs
to generate, let's say,

JavaScript in order to do
things for webpages and so forth.

So this is something that is just a handy
thing to do.

Oftentimes you call those macros.

So basically what we're doing is we're
defining a macro.

We're writing a Python program where one
of the steps of writing this Python

program is to write just an entirely
different Python program.

And which Python program that is that we
wrote depends on the input.

So what this other Python program is going
to do, I'm going to call it m prime.

I'm going to be creating this Python
program.

I'm never going to run it.

So I'm going to create this Python
program, but never run it.

So I'm going to create this Python
function m prime.

And it's going to receive some
hypothetical input x.

I actually don't care what that x is,
because I'm never going to run this.

I'm never going to provide an argument for
that parameter x.

So I don't care what it is.

Let's just say that this is
going to take some input,

whatever that is, some
input bit string, let's say.

I'm never going to provide one,
but it could take one if I wanted to.

So what it's going to do, what this
program is going to do, is it's first

going to do that universal Turing machine
thing.

So it's going to run that machine M on W
using that universal Turing machine thing.

And then maybe assign the result of that
to Y.

I'm never going to use it, so I don't
care.

But it's going to do the universal
Turing machine thing with.

M on W, and then once that's
done, it's going to return true.

So all it does is say, simulate the
operation of that Turing machine M that

was given as input to
HALT on that input W that

was given also as the
second parameter to HALT.

And then once you're done simulating that,
throw away the result and return true.

If this runs forever, we can't execute
that line of code.

This is why we don't want to run the
program.

But if this line ran forever, if the
simulation of M on W ran forever,

if that never halted, then we can't return
true.

The only way we could ever return true is
if M on W finished.

So this is acting sort of like a
gatekeeper.

This line where we said, run M on W,
that's acting sort of like a gatekeeper to

our actual accepting statement,
to where we actually accept our input.

So if M halted on W, then that meant no
matter what input I might have provided to.

X, M' is going to accept it, is going to
return true.

No matter what I filled in for X,
M' was going to return true on that input.

The input didn't matter.

If, however, M ran forever on W,
then no matter what X I provided,

this was never going to return true.

So, if M halts on W, then the language of
M' is going to be all possible strings.

However, if M on W ran forever,
then the language of M' was none strings,

the empty set.

The empty set of strings.

There were no strings in that language.

In this case, it was infinite.

In this case, it was finite.

That is, like, impossible to read.

Let's do this.

That one was infinite.

This one was finite.

So, if you could answer the question of
was this infinite versus was this finite,

then you had to know
whether you were in this

condition that M on W ran
forever versus M on W halted.

So, if there was some sort of,
like, magic little elf or something like

that that could tell us whether or not
languages of machines was finite,

we could say, all right, clever little
elf, then what does M' do?

And then we could
use that answer for M' to

answer the question
about Halt for M on W.

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

Why is this still in Java format?

Sorry.

Ignore these.

And then this should be a semicolon
instead.

And then this goes away.

Hopefully, it's readable enough.

So, now, if we have this finite function,
we can use that finite function in order

to solve Halt by saying, first,
we're going to make M' equal to the string

that results from maybe
this function that says,

invoke the macro to
build the code for M' prime.

So, this make M' basically says,
build the source for M' using M and W.

And then we have that string as M' prime.

If finite were to exist,
we could invoke finite

of M' and that's just
going to tell us the answer.

So, here's what this looks like.

Assume towards reaching a contradiction
that finite is going to be decidable.

That we can compute finite.

That must have meant
that there was some Turing

machine that we could
use to define finite.

So, what we're going to do is we're going
to use this Turing machine R that decides

finite for us in order to build this
machine D that decides Halt for us.

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

this machine M' prime that
says, run M on W, then accept.

So, we're going to build this
machine M' and then take the

source for M' and then
give that as the input to finite.

So, if R tells us, yeah,
the language of that

machine was finite,
that meant it was empty.

So, it must have been that M on W ran
forever because we never accepted anything.

So, we can return the opposite.

If, however, the language
was infinite, well, that

must have meant that it
was the set of all strings.

So, M on W must have halted because then
we got to this accept line.

So, the answer was accept.

M on W did halt.

So, by knowing the behavior of M' by
knowing the language or some property of

this language for M' we could determine
whether or not M halted on W.