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, <i>f</i>,

and then halts,

and another Turing machine

which computes another function, <i>g</i>,

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 <i>third</i> 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 <i>U</i>,

And what <i>U</i> does

is it takes a pair of things as input,

<i>P</i>, which you can think of

as a program

or the description for

another Turing machine,

and the input <i>x</i>

and <i>U</i> given the pair,

<i>P comma x</i>

produces

<i>P of x</i>:

what <i>P</i> would do

given input <i>x</i>.

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.