---
Video Title: What was Turing’s Model Modeling?
Description: Theory of Computation
https://uvatoc.github.io/week8

17.1: What was Turing's Model Modeling?
- Why model computing?
- What makes a good model
- Turing's model
- Why finite alphabet? Why finite states?

David Evans and Nathan Brunelle
University of Virginia
---

The big question that we are answering
this week is understanding what functions

can, and more interestingly, cannot be
computed by this Turing machine model,

which seems like a powerful model of
computing.

And we'll actually see that it's as
powerful as necessary to capture some

large intuitive sense of what machines can
compute.

So that's where we're going over the next
two classes.

We're going to start by a little bit of
recap.

We've seen a bunch of computing models.

We started with Boolean circuits.

Those correspond to things that we might
be able to build with transistors.

But we have a mathematical
model, and we can

describe all circuits as
the set of nodes and edges.

It's a graph where we're doing some simple
operation at all the nodes.

And we can define the computing model.

We need two pieces.

We need some way of showing what we can
represent and what it means to execute.

What it means to execute is
how we get from a representation

of our computing model, and
maybe some input, to an output.

And we've seen that for Boolean circuits.

We've seen that for the NAN-CIRC language.

Here, our representation is really simple.

It's lines of this form.

Our computing model
tells us how to take a.

NAN-CIRC program,
evaluate it, and get an output.

Each function that
we can define with our.

NAN-CIRC or Boolean
circuit model is finite.

It works for a finite number of inputs,
so we could always just do a lookup table.

But it's still interesting to look at what
circuits can do more compactly.

We started looking at unbounded models of
computation, where, with some short finite

description, we can now define a computing
model that can work on inputs of any size.

And we had a finite state machine,
where we can roughly describe how to

evaluate with a few short lines of
Pythonic code.

So certainly that's not a precise
mathematical definition of how to evaluate

a finite state machine, because it assumes
we know what all sorts of complicated

things like for loops mean in going
through input bits.

But we could define that more precisely
mathematically.

But it should correspond to your
understanding of what it means for a.

Python program to execute
and a precise notion of

what it means to evaluate
a finite state machine.

And then, last class, we
started talking about Turing

machines, which add to the
finite state machine some memory.

Some memory that's unbounded.

And we can think of that as being a tape,
which goes on forever.

So all of these are models of computation.

So what's the purpose of these models?

What are we modeling?

Normally when we think of building models,
right?

Most of science is about building models.

We're trying to build models to understand
something.

Is that what we're doing here?

We've spent about half the semester
talking about models of computing.

I hope there's some good reason for doing
that.

Because if there's not, then you should
have been taking some other class.

So what conceivable value could these
models have?

Yeah.

Model of thinking?

Okay.

Thinking like what goes on in your brain.

That's an interesting way of thinking
about it.

So how close do they come?

If our goal is to model how humans think.

At least all of us have some intuitive
sense of how humans think.

Because we're humans and presumably we
have thought at some point.

How good are these models?

Do these correspond well if our goal is to
model human thinking?

Probably not.

It doesn't feel like how I think I think.

None of these models are too close to
that.

Maybe at some deeper level we could think
about whether any of these models...

Of the models we've seen, which one is
closest to modeling human thinking?

I see.

Okay, yeah.

If we think about modeling what's going on
in a brain, now we know a little bit about

neuroscience as opposed
to what we intuitively

think is happening
when we're thinking.

And you had, I think on one of the problem
sets, a question about can we implement

something like a Boolean circuit using our
model of an artificial neuron.

So in that sense maybe it's kind of a way
we could think about how we think.

Definitely our brain is finite.

So any of these infinite models probably
have some problems.

We don't have... we have a lot of memory in
our head, but it's definitely not infinite.

So what else?

It seems like if our goal is to
model human thought, this is

not where we should have started
or where we should have gone.

Yeah.

I'm surprised no one give the answer,
and I think most of you are computer

science majors, that we want to model
computers.

That would be the most, at least, the
answer I would have most expected to get.

It's too obvious.

Okay, that's why no one give that answer.

Either that or it's been a long... it's
been a long week.

It's already Monday afternoon.

Certainly, modeling computers is useful.

If we want to build computing systems and
have them work and be able to reason about

what they can do, having some kind of
model for that might be useful.

But Turing came up with this
model of a Turing machine,

which he called an automatic
machine, in the 1930s.

He was not modeling computers.

There were some sort of glimmers of
computing machines starting to happen.

There actually were computing machines
going back to the 1600s.

But that's not what a computer meant in
Turing's day.

He was trying to model something else.

Let me just have a little detail.

If you think of scientific models,
these are all models of the universe.

They go back thousands of years.

Which one's the best?

Why is Einstein's the best?

Yeah?

So it's the one that is closest as far as
we can measure to physical reality.

Is it the most useful model for most of
what we do every day?

No, right?

Part of the goal of a model in science is
to understand physical reality.

So the most useful model is the one that
matches closest.

Another part of the goal of a model is to
be something simple that we can use to

reason about things that matter in our
life or that we're building.

Right?

And there are some
things, like if you're building

GPS, you better worry
about Einstein's model.

If you're building a bridge, you're
probably okay with Newton's model.

If you spend your time worrying about
quantum relativity when you're designing a

bridge, you're probably not going to build
a good bridge.

For understanding the seasons and stuff,
maybe Copernicus model is better.

Ptolemy's model is not a desired model for
anything we do today.

But it was pretty good for a long time.

So this is what Turing was modeled.

Computers in the 1930s were humans who did
calculations.

This is the Bonus Bureau Computing
Division, 1924.

Does anyone know what the Bonus Bureau was
doing with all these human computers?

What would you guess the Bonus Bureau is
doing?

They were calculating bonuses.

This is how they figured out how big a
check to send to the veterans.

So this is calculating the bonuses for
veterans of the army.

You needed, and I don't
know if this is everyone, but you

needed a pretty big room of
people to calculate those bonuses.

That is something we would think, yeah, you
can probably write a very short program.

Like, I don't know exactly how complicated
the rules of bonuses, but it's probably

just some very simple function of how long
they served and what rank they were.

And you would be done.

But you needed room of people like that.

But two things to notice, and this is if
you're thinking about a model.

They had little machines.

They had infinite
rolls of tape, or at least

they had scratch
storage to do their work.

But there were people following rules to
do these calculations.

So this is from Turing's paper from 1936.

I'm going to show you
various quotes of this that

explain why he came
up with the model he did.

But it's also been a very long-lasting and
useful model.

This is what he's modeling.

He was writing about elementary
arithmetic, what kids do in school,

where they might be dividing their paper
into squares and following some procedure

to do division or multiplication or
something.

This is from the paper which introduced
this model.

Turing did not call it a Turing machine.

That would have been arrogant and
presumptuous.

He called it an automatic machine or a
machine.

The goal of the paper was not about
modeling computation.

The reason that he came up with this model
and needed a formal model of computation

was to answer this question of what
numbers can be computed, thinking about

what it means to compute a number as we
can describe that number in a finite way.

So if you have some finite program,
some finite set of instructions that

you're going to follow in a mechanical
way, which, remember, that means human

computers following it, writing down what
they're doing on scratch paper,

the question of what can and cannot be
computed, what numbers you can produce.

So this was the question that drove the
model.

The intuitive notion of a computable
number is a number that we can write down.

We can have a machine write that number
down.

And it's a finite machine.

We'll look at some examples of computable
numbers soon.

But this is the model.

This was introduced last class.

I'm going to write it using the notation
that's in the book.

So we have an alphabet.

That's a finite set of symbols.

The way it's defined in the book,
which is a little nontraditional,

is there's always these four symbols in
that set.

The alphabet is a superset of 0, 1, which
are the values that we use for the input.

And then this symbol,
which unfortunately looks

a lot like a 0, you
can think of as a blank.

That's a square that doesn't start with
anything in it.

And then there's a
special symbol that's a

triangle that's used
for the start of the tape.

Nothing other than 0, 1 is necessary.

We need two symbols.

We can do everything else, but it makes
life simpler to have those extra symbols.

But the key part of the machine is the
transition function.

And the transition function is what tells
us how to execute the machine.

This is just the representation of the
machine.

For this to be a model of computation,
we have to say what it does.

But we have a function that takes in a
state and a read symbol.

There are two things that determine what
the machine is going to do next.

It outputs the next state.

This is the symbol that's written.

And a move.

So you can move left.

You can move right.

You can stay where you are.

That's also optional.

And I think I would prefer
the definition without a

stay where you are, but
that's what the book uses.

And then the halt is when you're done.

And so far, we've only defined the
representation.

What it means as a computing
model depends on saying,

well, now you've described
the machine like this.

You've described the machine by giving the
transition function.

And then we want to say, well, what
does it mean for that machine to execute?

But before we do that, we want to answer
two questions.

Both the alphabet and the states are
finite.

So why is the alphabet finite?

Why not allow an infinite number of
symbols in the alphabet?

So I think it's more than the meaning be
unclear.

What else would be unclear if there are
infinitely many symbols?

So certainly, mathematically, we can do a
lookup.

A lookup is a function, right?

And we have plenty of functions that take
any natural number and output something.

So there's no reason we couldn't do a
lookup that's infinite.

And in fact, we're going to need one for
the tape, right?

The tape is basically an infinite lookup
function.

So that isn't quite the reason.

Yeah.

So we can certainly define total functions
on infinitely large sets of input.

Addition is one example, right?

So let me give you one more hint.

Because I think we're not quite going in
the right track.

Remember that our tape is divided into
squares.

And let's assume the squares are all the
same size.

Why can't we have infinitely many
different symbols?

Good.

Yeah.

We've got to be able to read the symbols.

So if we have infinitely many different
symbols that we can fit in one of these

little boxes, well, at some point,
the difference between any two symbols is

going to get so small we can't tell it
apart.

That's the justification Turing used to
say why the alphabet has to be finite.

And I think it's a pretty good one.

Otherwise, there's not a real
justification for this.

And if you could have infinitely many
symbols, well, that would open up lots of

questions about, well, now you've got to
define a transition function.

Maybe the symbols can encode things in
different ways.

But if you make it finite, then all those
problems go away.

And if it's finite, well, you can have two
or you can have a hundred million.

It's the same thing, right?

If it was infinite, things would get more
complicated.

So this is how Turing said that.

So he's assuming the tape's divided into
squares.

And if we allowed an infinity of symbols,
then they would differ by some arbitrarily

small extent, and we couldn't tell them
apart.

He gives a nice example of...

We can make 999 a
single symbol, but it's

really hard to tell if
those two are the same.

I don't know if anyone's
read the paper close enough

to know if those are
actually the same or different.

But either way, it's a problem.

There's this little footnote here,
which actually gets more at what you said

is, well, if we have to print this,
we can think of putting dots of ink or

something like dividing our square into
pixels.

But eventually they're going to be too
small, and we can't distinguish the symbols.

So he had a good reason why the alphabet
had to be finite.

What about the number of states?

Why is the number of states finite?

The tape.

So the tape is actually not finite.

The tape is the one thing that's infinite.

And remember what the tape is modeling.

The reason why the tape is infinite,
this is the tape.

It's not actually infinite.

That physical tape is not infinite.

But when he thinks about modeling this,
the amount of scratch paper any of the

human computers can
use to do their computations

is reasonable to
think of that as infinite.

They can keep getting more.

It's not really infinite because you need
trees to cut down to make more paper And

eventually the whole universe,
you're going to use up all the trees and

not have any paper, but...
Reasonable to think of that as infinite.

That's the one thing that is infinite, so
why not make the number of states infinite?

So it would definitely be harder to draw
machines with infinitely many states,

but there's no reason we
couldn't define the transition

function that worked
for infinitely many states.

We're pretty good at defining functions on
sets of inputs that are infinite.

What is he actually modeling with the
states?

Remember, he wrote about
children doing arithmetic

as his more concrete
thing he wanted to model.

What are the states?

The state is the state of mind of the
computer you're modeling.

What a human can keep in their mind is
limited.

That was how he stated the justification
for keeping the number of states finite.

If what you're trying to model
is humans doing computation,

it's easy to think of the
amount of paper being infinite.

It's really hard to think of what you can
keep in your head being infinite.

This is how he describes that in more
detail.

And it's kind of the same as the
character.

If you could have infinitely many
different states in your head,

you couldn't tell them apart.

Just like if you could have
infinitely many different

characters in one square,
you couldn't tell them apart.

So both the number of states of mind,
which are the number of states in the

state machine, and the
number of symbols that

you can write on the
tape have to be finite.

That's how we're going to represent our
computations with this model.

What else do we need to do to have a
computing model?

We've got to explain how they execute.

So that's what we need to do next.

We're going to do the following months