So we've talked about
the
partial recursive functions,
we've talked about
the lambda calculus,
these were two of
the models of computation,
and definitions of
what is computable
that were proposed
in the first half
of the Twentieth Century.
And notice that they looked
totally different from each other,
they looked, like,
utterly, completely
different beasts.
But we found that there were ways
that the lambda calculus
could simulate
some arithmetic
and we even built the successor function
in the lambda calculus
which was one of
the basic building blocks
of the partial recursive functions.
So you may already
be getting the idea
that, although these different models
of computation are very different,
they can simulate each other
to some extent.
Well, in some sense
this debate about
what is computational,
what is computable,
it may not have ended,
but it reached a huge milestone
when we came to
the Turing machine.
So, Turing machine was invented
by Alan Turing, who hopefully
you've heard of for lots of reasons,
including helping,
actually playing a leading role
in decoding the Nazi Enigma code,
coming up with mathematical models
of pattern formation in biology,
like embryogenesis, how
fly embryos get the segments
of their thorax,
or for that matter
how leopards get their spots,
and also being persecuted
by the government
for his homosexuality
and being driven to suicide by it,
which was an enormous loss
for, well, the world.
And especially for mathematics
and computer science.
So, here is his definition
of a basic computer:
we have a tape
and on this tape
are written symbols
in some finite alphabet.
These could be zeroes and ones,
they could be A through Z,
just some finite set.
Then we have a head
which moves back and forth
on the tape.
The head is a very simple machine
and it only has a finite
set of states,
which we'll call "S."
Now, all this machine
can do at each step
is read the symbol,
at its current location on the tape.
It may then,
depending on that symbol
and its internal state,
so depending on "a," the tape symbol
and S, its internal state,
it may do a very small handful of things.
It may
write a new symbol
at that location on the tape,
overwriting the "a" with something new,
a prime,
and it may then move
left or right
by one step.
And that's all it does.
So any Turing machine
can be described
just in terms of
the alphabet of tape symbols "a,"
the set of finite states S
for the head,
and what we call the
transition function,
which takes pairs "a comma S"
and produces new pairs
"a prime comma S prime."
And something like,
let's call it plus or minus one
telling the head to move
left or right.
Alright.
So, you know, you can think of this
almost as
a simple electric device
which is
moving back and forth
on some magnetic tape
or something.
It looks like something
that you could
really build.
So, we're going to add
one more thing,
there's going to be a special state
which we'll call "halt"
when the machine is done.
So how would it actually
carry out a computation?
We would give it its input
by writing
some initial string;
it could be a string of bits
representing an integer,
it could be a string of letters
or whatever,
on its tape.
We then set it up
in a special initialized state--
I guess that's another
special state--
and we let it go
and it does
whatever it's going
to do,
reading and writing,
shuttling back and forth,
until it reaches
the halt state,
and then
its output
is what is then
written on the tape.