---
Video Title: Defining the Binary Strings
Description: Theory of Computation
https://uvatoc.github.io

3.5: Can the Binary Strings Represent the Natural Numbers?
- Defining the Binary Strings

David Evans and Nathan Brunelle
University of Virginia
---

We want to understand what are the things
we can represent with strings of bits.

If they're going to be in a computer,
they're going to be finite.

They can be any length.

When we say finite, that doesn't mean the
length is bounded.

But it does mean it always eventually gets
to the end.

It can't go on forever.

But there's no limit to the length it can
be.

Can we represent the natural numbers using
finite binary strings?

The natural numbers suddenly go on
forever.

Do the finite binary strings go on
forever?

There's a finite, finite string of any
length.

There's no limit on the length of a finite
binary string.

Just like every, every natural number is
finite.

Even though there are infinitely many of
them.

Any specific one is finite.

Before we try to answer this, maybe we
need to define the binary strings.

There is a definition in the book.

Binary strings of all lengths.

These are all the finite strings.

He provides three
different notations that mean

the same thing, tended
to define binary strings.

They're all kind of complicated.

This is picking any
natural number, and it's a

sequence of either zeros
or ones of that length.

So now do we have an
easy answer to, can we

represent all natural
numbers with binary strings?

Right?

This is all the natural numbers.

So there is a binary string zero when n is
zero.

Just one sequence.

There's a binary string zero zero when n
is two.

There's a binary string zero zero zero
zero zero zero zero.

We don't even need ones, right?

Ones are just the way.

So we can represent all the natural
numbers with just strings of zeros,

of length, whatever the natural number is.

Ones are useful for
making those notations more

compact, but not necessary
at all to represent them all.

So that, I hope, gives you an intuition
that we can do this.

It's not a proof, because it's using dot
dot dots.

So let's see if we can do a proof.

And we're going to do a proof using
induction.

I want you to think about this for a
second, and we'll do a slack poll.

It's a little bit of a trick
question, but mostly hope to

get you thinking about what
the proof is going to be like.

One is very unpopular.

Why is one so unpopular?

And zero is popular.

Are those choices numbers or something
else?

Which you can't really tell from the slack
notation.

Those are strings.

Our goal is to define binary strings.

So zero means the string containing just
the bit zero.

One means the string containing just the
bit one.

And empty means the string with no bits.

One is unnecessarily unpopular.

Both one and zero are equally not the
ideal base case.

You could start from both of them if you
don't want to include the empty string.

But if you look at... This
gets back to the question.

Is the empty sequence a binary string in
the book's definition?

Yeah, it is.

Because n is the natural numbers,
which includes zero.

And the sequence from, in this case,
zero minus one, that's an empty sequence.

The sequence from zero to...

This is a little bit wacky
as well, to have the

end of the sequence
be before the beginning.

But that suggests it's an empty sequence.

So we want to start from the empty string.

And there are lots of different ways we
could write it.

It's hard to see empty strings,
because they don't look like anything.

We can write this as lambda or epsilon.

They're different symbols people like to
use.

But it's an empty string.

It's a string with no bits in it.

So that's our base case.

What's our inductive case?

So we do want to produce all the binary
strings here.

Not just the ones.

It looked like just zeros was enough to
represent the natural numbers.

Which is kind of unsurprising.

So we can add a zero in front or behind.

But we also want to produce strings with
ones.

Yeah.

You have two options, but you have one.

Right.

We can put either a zero or a one.

We can add either a one or a zero.

Right.

We could put it at the beginning.

We could put it at the end.

Either way is going to produce our set of
binary strings.

Okay.

The kind of tree structure?

Like we start out with...

I guess we start out with nothing.

And then that splits off into zero,
nothing, one, nothing.

And then that splits off into...
So we start with empty string.

By the rule, now both zero and one are.

By rule two, now for both of those,
we can add a zero in front.

So now from this one, we get zero,
zero, and one, zero.

And from this one, we get zero,
one, and one, one.

We can apply the rule again.

For this one, we're going to add a zero in
front of it, and a one in front of it.

And we can do that for all these.

So yeah, it will look like a binary tree.

Every time you apply
the rule to the previous

generation, you're going
to get twice as many strings.

So this is going to produce all binary
strings of finite length.

Can we represent all the natural numbers?

Yeah.

So we should intuitively see that we can.

We already saw we could do it with just
zeros.

So we could prove...

If we needed to prove this to someone who
was more skeptical, could you do it?

We'll see.

Maybe we can put that on the home record.

We'll see.