---
Video Title: On Uncomputable Numbers
Description: Theory of Computation
https://uvatoc.github.io/week8

17.5: On Uncomputable Numbers
- What is means to "compute" a number
- Are there numbers that cannot be computed by any machine with a finite description?

David Evans and Nathan Brunelle
University of Virginia
---

What it means for a machine
to compute a number is

that it can write it down
with arbitrary precision.

So, for most interesting numbers,
we can't write them down exactly.

But we can write them down,
and if we're willing to wait

long enough, we can write them
down as precisely as we want.

So, let's see if that definition makes
sense, at least intuitive.

So, is one-half computable?

Can we write down a decimal representation
of one-half?

I think so.

What is it?

In binary?

I know you know 0.5 in decimal.

What's the binary representation of
one-half?

Yeah, 0.1.

That's one-half.

Okay.

And so, certainly we can write a machine
that's going to output...

And he was saying, well, we're dealing
with real numbers between zero and one,

so all we've got to do is write a machine
that outputs one.

We have shown that one-half is computable.

Okay.

What about one-third?

Is one-third computable?

Yeah.

The answer whether
something is computable

shouldn't depend on
our output representation.

So, in that sense, it's a good answer to
say yes.

If we were using ternary notation,
it would be 0.1.

But it should be the case our answer
doesn't depend.

And what is one-third in binary?

You know how to do division.

This is...

This is one, right?

One-third.

This is three.

So, if we do...

Our old familiar fourth-grade long
division works perfectly well for binary.

We're just not used to doing it that
often.

Eleven is not bigger than ten.

But this is one times one.

This carries.

Subtract.

I think this is going to continue forever.

Point 0, 1, 0, 1, 0, 1, 0, 1 is one-third
in binary.

Can we produce a machine that will output
exactly one-third?

No.

This goes on forever.

So, you have to be careful how you define
a computable number.

But we can get as close as we want.

We can write a machine that's going to
print out 0, 1, 0, 1, 0, 1.

And as long as we run it, it's going to
get closer and closer to one-third.

It's going to get arbitrarily close to it.

So, that's computable.

Okay.

What about tau?

Tau is the ratio of the circumference to
the radius.

Some of you might prefer pi.

Tau is two pi.

Tau is a much better number to use than
pi.

Is tau computable?

What we want to know is, can we get a
machine to print out this?

It's the decimal part that we care about.

The whole number of parts are always easy.

You can always output the whole number
part.

Yeah.

So, there are things that we can compute
that get arbitrarily close to tau,

just like we can get arbitrarily close to
one-third.

And that's what it means to be computable.

There are lots of formulas that have been
known.

One is attributed to Leibniz.

There were actually Indian
mathematicians who knew

about a general version of
this even before Leibniz did.

We can have a machine that's going to
compute these things.

We know how to
compute all these, and the

further we go, the closer
we get to tau over two.

Leibniz had computing machines.

He built a machine that could do all four
basic operations in the 1670s.

But more than that, he
actually had an understanding of

universal computation,
which we've seen for circuits.

He had a more powerful one, which we'll
get to.

He was pretty well ahead of this time.

So, it sounds like everything is
computable, right?

At least so far, everything we've thought
of is computable.

Is there anything that's not computable?

So, can we answer this without finding an
uncomputable number?

So, it sounds like any number that we can
think of, any number that we can describe,

if we can describe it, and we understand
what it is, we can probably compute it.

Because the fact that
we can describe it means

we have some finite
description of the number.

If it's a regular mathematical finite
description, we should be able to compute it.

So, how would we
answer this question without

actually finding an
uncomputable number?

Yes.

Yeah.

Right?

Remember how we showed there were functions
that couldn't be computed by circuits.

Right?

We didn't find some specific
function and said, here's

a function that you can't
compute with a circuit.

We looked at, given a circuit of this
size, how many functions can you compute?

And how many functions are there?

And if the number of functions there are
is bigger than the number you can compute,

there must be some you can't compute.

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

We're going to do the same thing.

Instead of starting from, well,
let's think about numbers and try to

figure out if there's a way
to compute it, which is a

much tougher thing to find a
specific uncomputable number.

Let's just look at the sizes.

So, how many computable numbers are there?

Our definition of a computable
number is something

that a machine can
output to arbitrary precision.

And our machine is what we can describe as
a Turing machine.

We've got a
representation that we think

captures something
important about all machines.

So, we've got our representation of Turing
machines.

So, how many different computable numbers
can each Turing machine produce?

Each single Turing machine can produce
just one number, right?

This is why we went to the no input model.

Because it's easy to
say, if there's no input,

the machine runs the
same way every time.

It's totally deterministic.

We follow our transition rules.

We run it for as long as we want.

And we're getting arbitrary close to
whatever number it will produce, right?

So, each Turing machine produces one
number.

So, that means that the
size of the computable

numbers is the cardinality
of the Turing machines.

Given that we can describe a Turing
machine in a finite way.

Our Turing machine is what we can describe
with this.

There's a finite function that's the
transition function.

Well, we can write that down as a finite
binary string.

We can write down our transition function.

This is finite.

So our transition function is a lookup
table.

And we can certainly write that down as a
finite binary string.

That means that the number of Turing machines
is the number of finite binary strings.

How many finite binary strings are there?

Yeah, it's countably infinite.

It's the same as the number of natural
numbers.

We know that.

So we've got the number
of finite binary strings

is the same as the
number of natural numbers.

Well, how many real numbers are there?

We said the computable numbers is a subset
of the reals.

How many real numbers are there?

Yeah, it's more than this.

So the real numbers have cardinality
higher than that.

The real numbers have cardinality equal
the power set of the naturals,

which is greater than the cardinality of
the naturals.

So that means there must be some real
numbers that are uncomputable because

there are more real
numbers than there are Turing

machines and each Turing
machine only produces one number.

Are we happy about this or are we sad
about this?

Does this mean there are interesting
things we can't compute?

Well, not necessarily.

Most numbers are totally uninteresting.

What's an example of an uncomputable
number?

There isn't an example, right?

If you give an example,
anything that you can

use to describe the
example makes it computable.

But if you think of numbers are just
infinitely long strings of digits, right?

If you take, say, tau and you randomly
replace three of its digits with something

else, well, that's probably not
computable.

But if I tell you which three I've
replaced, it's easily computable because I

compute tau and I replace those digits
when I get to them.

But most numbers are not interesting.

And all the uninteresting numbers are not
computable.

But if we can describe
them in a straightforward

way, well, then we know
how to compute them.

This argument works for functions as well.

The functions that involve
most things that we care

about have a cardinality
larger than the natural numbers.