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.