---
Video Title: Proving Computability and Noncomputability
Description: Theory of Computation
https://uvatoc.github.io/week10

21.1 Proving Computability and Noncomputability
- Ways to Prove a Function is Computable or Uncomputable
- Example: Adding is Computable

David Evans and Nathan Brunelle
University of Virginia
---

One of the things you should all be able
to do is, for some description of a

function or a problem
or a language, be able

to prove whether
that's computable or not.

If the question doesn't tell
you which, you've got to have

some intuition about which
is the right one to try to do.

So what are the strategies that you can
use in general?

If you want to prove something is
computable and that something could be a

function, usually when we talk about
languages we use the decidable,

undecidable terminology, but we're going to
use those to mean basically the same thing.

So, yeah, what do we do to show something
is computable?

Rice's theorem.

Okay, so we could use Rice's theorem.

That is mostly helpful for showing us
things that are uncomputable.

Good, yes.

The most natural way to prove something is
computable is a construction.

If you can show how to make a machine that
computes it, there's an implied,

in this question, computable by a Turing
machine.

If we asked if this is computable by a
circuit or by a finite state machine,

that would be a different thing you have
to construct.

But what you have to
do is construct some

machine that computes,
let's say, a function f.

And what does it mean to have a machine
that computes it?

Well, it has to, for all possible inputs,
produce the correct answer.

And that means it always finishes and it
always produces the right answer.

Yeah, question?

Good question, yeah.

So what does it mean to do a construction
proof?

So if our goal is to
show a Turing machine,

would it be enough to
show a Python program?

What would make you really convinced that
the answer, if you show a function,

show Python code that computes it,
that that's a satisfactory answer to prove

something is computable by a Turing
machine?

Yeah.

So how do we know that?

How do we know that anything
we can construct in a Python

program, we could also
write in the Turing machine?

To show that something is computable by a
Turing machine, if we're going to do it by

writing something else, we've got to show
that whatever we did that something else

in, we can simulate with the Turing
machine.

So if we can write a Python
program and we can show

that there is a Turing
machine that simulates Python.

So once we've shown that there's a Turing
machine that can simulate Python,

then anything that we can do in Python,
we can also do with a Turing machine

because we can simulate Python with that
Turing machine.

If we wanted to show the opposite,
we'd have to show if we could show writing

a Python program that simulates a Turing
machine.

And that would mean
anything that we can do with

a Turing machine, we
can also do with Python.

At least in our idealized version of
Python, we could do both.

That would show that they're equivalent.

But if our goal is to
show something that's

computable, we just
need the one direction.

If your goal is to show something that's
computable, and you say, well,

I know that I can write a Turing machine
that simulates Python, then I can show my

computability proof by writing
a Python program, because I

know that there is a Turing
machine that would simulate that.

It's easier to write Python code than to
write Turing machine code.

That's the usual way we're going to prove
something is computable is by

construction, by showing a way to compute
it.

And that doesn't necessarily mean we know
the specific code or we know the specific.

Turing machine description, but we know
that there's a way to make it.

So what about proving something is
uncomputable?

If we're going to prove uncomputability,
what do we have to do?

Yeah.

So we have two main strategies.

One is contradiction.

We're showing that if we could compute
this, something impossible would result.

The other main strategy is, it's also kind
of contradiction proof, is to say,

here's something we know is uncomputable
that we could build if we had this.

This is a special kind of contradiction.

So we have to do a
reduction that shows some

problem that we already
know is uncomputable.

Any problem that you already know is
uncomputable can be used for this.

Let's try an example.

Is addition computable?

What would your intuition tell you?

It would tell you probably yes.

The other thing it should tell you is,
well, define addition.

We can't answer a question
about whether something is

computable or not unless it's
defined in some precise way.

So we better define addition.

How should we define addition?

How do we define a function?

Yeah.

Good.

So let's assume we've got a
mathematical...

We've got the mathematical definition of
addition already.

Let's assume we have plus defined on the
naturals.

We know plus is a function that takes two
naturals in and it outputs a natural.

And that function is defined and we have a
good notion of what addition means.

If we're asking, is it computable by a
Turing machine, we've got to define it as

a function that makes sense to a Turing
machine.

So we've got to say what the input is.

What is the input to a Turing machine?

Is it two natural numbers?

It's got to be something
that we can encode

on a tape with a finite
sequence of symbols.

So we've got to describe the input,
and the input, if we're being careful,

right, so the input is some
string of zeros and ones, or

maybe we could add some
other symbols to our alphabet.

Maybe it's going to be useful if we add a
plus symbol.

And let's say it's of the form,
the sequence, we've got all the little a's

and little b's are zeros
or ones, and we're

using our special plus
symbol to separate them.

So that's our input.

And now we've got to say what the output
should be.

So how will we define the output?

Well, we want, at the end of the machine
execution, the tape's going to contain,

and now we're going to say, like, these
are binary representations of naturals.

And then the output is going to be the
binary representation, a plus b,

where that plus is the natural number
plus.

So if we want to ask a question whether
something's computable by a Turing

machine, we've got to define a problem,
we've got to define the inputs,

and what the required property of the
output should have.

Now we've got that definition.

How do we prove it's computable?

Yeah.

So certainly this is one
where it would be nice to

have a Python program
rather than a Turing machine.

But it should also raise the little
questions of how, if we built our Turing

machine to simulate
Python, it would need to

include a way to simulate
what plus does in Python.

So we're sort of offloading all the
complexity of this to assuming this Turing

machine that implements Python exists,
and we haven't actually done that.

If we didn't want to do that, we'd have to
get some sort of intuition of,

well, if we're going to do
add as a Turing machine,

we're going to start
with this as the input.

Writing a full Turing machine
like this would probably take

longer than you have for the
exam and is not that interesting.

But you should have a sense that you could
do it.

Well, you've got to probably look for the
number before the plus.

So you're going to have
something that's going to

move right without changing
it until you see the plus.

And then you're going to move left.

And then based on whether that's a 0 or a
1, you're going to probably have to erase

that with something and start moving
right.

You're going to move right to the end.

Maybe we should put an
equals in there so it ends up

looking like a nice output or
we could change how we do it.

And then you're going to need to keep
track of these states And you're going to

end up with sort of another copy of all
these states for when you had to carry.

And then you're going to get
to some output based on if this

was a 0 or this was a 1,
you're going to write a 0 or a 1.

That would be really tedious to do the
whole machine.

But that would be a proof that it's
computable, that you are convinced you

could do it, and it's always going to
work.