---
Video Title: The Natural Numbers are Computable
Description: Theory of Computation
https://uvatoc.github.io/week10

21.2 The Natural Numbers are Computable

David Evans and Nathan Brunelle
University of Virginia
---

We proved in class that, and this was the
basic question that Turing started with,

that there are numbers that are not
computable.

That there are uncomputable numbers.

That was clear because
the number of numbers

was more than the
number of Turing machines.

That there must be some we can't compute.

So what about the naturals?

Is every natural number computable?

Does our proof that there are some
uncomputable numbers break?

So it better break, otherwise the natural
numbers would be uncomputable.

So we proved that the reals included
uncomputable numbers.

And this is saying every natural number is
computable.

So why does that proof break?

Well, there are more reals than there are
naturals.

That proof depended on the number of reals
being uncountably infinite.

Okay, so if we're going to prove that
every natural number is computable,

that's proving that for any
natural number there's some Turing

machine that outputs that
number, starting with a blank tape.

Constructing one machine would not prove
this.

How are we going to prove this?

Yeah.

If we allowed anything on
the input tape, we could start

with an input tape that had
any natural number on it.

And then we don't have to do anything.

The same notion that Turing had was this
is a machine that starts with a blank tape

and prints out the number.

Definitely, if we could start with
anything we want on the tape, we could

start with different things
on the tape that would add,

but we don't even need to
add to produce all the naturals.

Okay.

So we need to show that there's some
machine for any natural number,

there's some machine that can print that
number.

Pretty close.

Well, do we need to do anything that
complicated?

By any representations, a bit of a pain.

Let's use unary.

So we could do it with binary.

That would be complicated.

But let's just do it like this.

Machine k is going to be a machine that,
for k states, it's going to, for a blank

on the input, it's going to write a one,
and it's going to move right.

And it's going to have k states that do
this, and it halts after the kth state.

Is that a valid proof?

It's not one finite state machine.

But for any k, the number of states is
finite.

And we know how to construct a machine
that prints k1s.

A perfectly valid term machine is not a
very interesting one.

Definitely you could do a more compact
one.

And if you were writing the numbers in
binary, you could use less tape.

But it's an IFA tape.

So we don't need to conserve tape.