So,
Turing machines,
we just saw,
can compute the successor function.
It's intuitively clear
that they can also carry out composition.
If I have
a Turing machine which computes
one function, f,
and then halts,
and another Turing machine
which computes another function, g,
and then halts,
well I can compose these two functions
by running one of these Turing machines
and then running the other one.
And what I really mean
is I would build
a third Turing machine
where it has the combination
of the two Turing machines state spaces
and, when the first one halts
and completes its work,
that makes the transition
to the initial state
of the second Turing machine,
which then goes to work
until it halts.
In fact, it might not surprise you
that Turing machines can do
all of the things
that partial recursive functions can do.
So, but,
Turing also found something quite lovely
and he actually designed one,
there are universal Turing machines
that can simulate any other
Turing machine.
How do we do that?
Well, you know, just as a program is,
can be viewed
simply as a text file
that you would hand as input
to another program,
I just told you that Turing machines
can be described completely
in terms of their transition functions.
So I could put
the description of one Turing machine
on the tape
of another Turing machine,
along with an input,
and then I could set this
universal Turing machine loose,
and it could, in theory,
simulate this Turing machine
on that input
and produce the results.
And, in fact,
there are Turing machines
which do exactly this.
We could call them U,
And what U does
is it takes a pair of things as input,
P, which you can think of
as a program
or the description for
another Turing machine,
and the input x
and U given the pair,
P comma x
produces
P of x:
what P would do
given input x.
Now, in the modern age,
this doesn't sound particularly
interesting or surprising,
because what is an operating system?
An operating system is a program
which runs programs.
So right now on your laptop
or your phone
or what have you,
is a program running all the time
which, when you give it a program,
it says, okay, I'll run this program
for you.
It's a program which runs programs.
An interpreter
is a program
which takes another program as input
and goes through it step by step
and simulates it.
And indeed,
people write interpreters
in undergraduate programming courses.
But in 1936,
when Turing was coming up with this,
this was a big, profound fact.
Again, think about
classical mathematics.
Can you think of a function
which you can give as its input
a description of other functions
and it will carry out any function
you give it?
That sounds absurd.
In order to carry out a function,
you need some higher order thing,
like a mathematician,
or a calculator.
Functions don't carry out
other functions.
And there's certainly no
universal function
which can carry out
any function at all.
And yet,
in the world of Turing machines,
you have exactly that.
Turing's original universal machine
was quite large,
with a lot of symbols,
and a lot of states.
But in fact clever people
have come up with very small
universal Turing machines,
with as few as four tape symbols
and six states,
for instance.
So, this phenomenon of
universal computation
is pretty ubiquitous,
you don't even need
that big a machine
to be capable of universality.