Turing's contribution was not just developing such a simple model of computation, but also showing that it was powerful enough to do any computation that we might imagine. That concept is called universality. So a Turing machine is nothing more than a finite sequence of symbols. We have our decrementer Turing machine that we drew out graphically, but we had a text file representation of it that's just a bunch of symbols. So, in particular, what we can do is we can put a Turing machine and its input on a Turning machine tape. Just lay out this table with spaces in between with different symbols on the tape. So, there is input we might want to run on the left and then this complete description of the Turing machine. Turing machine and its input are all described with a finite sequence of symbols. And what that means is that we can then develop another Turing machine that can take that as input and simulate its operation. Since any Turing machine can be described with final set of symbols in this way, this Turing machine uses this as input is going to be able to simulate the operation of any other Turing machine just like our Java program did. That's the idea of a universal Turing machine, a Turing machine that takes as input any Turing machine, an input for that Turing machine on a tape. So, that's a particular machine called universal Turing machine, and that's our example where we had our increment input to our decrementer Turing machine, and then a decrementer Turing machine, you could put any Turing machine there. And then what the universal Turing machine does is leave on the tape precisely what the Turing machine that's on the tape would leave on the tape if it were run on that input or if that machine loops the universal Turing machine would loop or ends in "Yes", "No", "All", it would do exactly what the Turing machine that's on the tape would do. In this case, it would wind up decrementing the number input by one and blanking out the rest of the tape. Turing figured this out that simply, simulating a Turing machine is a simple computational task. You can do it with the basic operations that we have laid out for Turing machine. So, since it's a simple computational task, there's a Turing machine to do it. That's a universal Turing machine. Maybe an easier way to think about it is look at everything that a Java simulator does, and each piece of it, think about building a piece of a Turing machine that could do that. Really, often, all we're doing is going and looking up in a table what state should I go to next and so forth. It's quite a simple computational task. Our simulator gives a roadmap for it. We don't have to build the constructor because everything's already on the tape. But simulating the infinite tape, we don't have to worry about that part of it because the Turing machine already has an infinite tape. Most of it is updating the state as I indicated. So, if you want to see the details or build your own Turing machine for any computational task, this is something that there's lots of resources for. In fact, we have a whole Turing machine development environment on the book side, and one of the things that's there is a 24-state universal Turing machine that you can go ahead and study and run on our decrementer or any other Turing machine that you want. Simulates the operation of any Turing machine if you put the input and that Turing machine on the tape. If you think that 24 is a small number, actually, people have developed universal Turing machines that have only four states with six different symbols. Just a warning, if you get into working with Turing machines and you like working with discrete processes and programming, it can be addictive and you'll find lots of examples on the book side of Turing machines that people have developed for all sorts of computational tasks. But the idea of universality is really profound. Universal Turing machine is a very simple model of computation that's universal actually and of precise technical sense. We're going to call a task computable if a Turing machine exists that can compute it. And what Turing proved is that it's possible to invent a single machine that can be used to do any computable task. So that's a proof is the existence of universal Turing machine. That's Turing's one of his main theorems. And so, one thing is that if you can simulate a Turing machine, you could actually simulate a universal Turing machine. So, if any machine that you make, if it can simulate the operation of a Turing machine, then it can simulate, it can do any computable task because in particular, it can do a universal Turing machine which can do any computable task. And that means that in terms of what you can compute, any one machine is universal. We don't have to build separate computers for each task that we might encounter like solving scientific problems or doing email or playing music. It means that all the computers that we can invent are equivalent. They are universal in that they can do anything that a Turing machine can do, which means they can do any computable task, and that's a very profound result that has lots of practical implications as well. Here's just an example. Maybe you've seen this example. It's called the Game of Life. It's different, simple, formal model of computation called a cellular automaton. So, we think of an infinite square grid with cells that can live and die under specific rules. It's discrete, time proceeds in discrete steps, and there's a couple of rules that determine whether cells live or die. So, it depends on the values of its neighbors. If a cell has too few neighbors alive, either zero or one, it dies of loneliness. If the number of living neighbors is just right, two or three, then it's going to live to the next generation. And if there's too many alive, more than three, it dies of overcrowding. And then the other rule is that a cell is born if it has exactly three living neighbors. Now, these are simple rules and you see how they work in just a second. So, suppose we have this configuration at a particular time T. Then what we can do is for every cell, you can count the number of its direct neighbors and these are the counts for this and you can figure out what's going to happen to each cell based on those counts. The one at the fringes are zero. There's a couple that have exactly three. And there's a couple that die of loneliness and one that dies of overcrowding. And you can check that in time T + 1, we get a different configuration. So question is what's the story with this discrete model of computation? It really is a model of computation as you'll see. So, the idea of Conway's Game of Life is that even very simple rules like that even simpler than Turing machine, can lead to pretty complicated behavior. And very early on, one of the things that people realize is, there's a thing called a glider, and after one two three four steps, the thing has the same form but it moves down through the grid. And again it's infinite in all directions, so if you get that configuration, it'll move. Now, you can write a Java program to implement the game of life to see what happens. And I wrote one that's how we get some of the demos that we've done here. It's a very simple program that maybe could have been an assignment when we discussed erase. But the input to that program can lead to interesting and complicated behavior. One thing that's quite amazing is a thing called a glider gun. If you start out like this, then here's what happens. Looks pretty complicated but after a while what you can realize is that this glider gun it bounces around at the top there but it spins off gliders. And when you think about it, that's actually pretty profound that we can get that kind of behavior from such simple rules. Those gliders out there that's transmitting information. If we can transmit information maybe there's more that we can do. And there's another level, there's a glider gun breeder that generates the glider guns that all generate gliders, extremely complex behavior. So, one thing that someone has figured out is what happens if you have that starting configuration. Pretty complicated starting configuration, but if you study it just for a minute and you can, while you have to study it quite a bit, but you can understand when I say that actually what that thing is is a universal Turing machine. You can kind of see the tape going off along the diagonal and then the state diagram as a little array down in the bottom left. So with the game of life, we can build a universal Turing machine, that mean anything that we can compute and that's the Turing machine's definition of what we can compute, we can compute with the game of life. It's quite surprising. It's a very profound connection to the real world. And what Church and Turing articulated and this was because many people are working on different models of computation, and they were trying to see if one would be more powerful than another, like we saw with our one stack and two stack machines at the end of the last lecture. By the way, a two stack machine as you saw them and we simulated a tape with two stacks, you can make that like a Turing machine. So, two stack machines are equivalent to Turing machines and therefore they can computing Turing Machines can and their equivalent. And what Church and Turing articulated is that anything that we can do in this universe is going to be equivalent. That a universal Turing machine, you can simulate a universal Turing machine, universal Turing machine can simulate it. So, they're all equivalent, all compute the same thing. Now, this is something that can't be proved because it relates to the universe, physical properties of the universe. It could be falsified but we can never prove that it's true. So the thing is, ever since this thesis was articulated, if someone wants to study a new model of computation or a new discrete physical process, we can use simulation to prove that it's equivalent to some known physical process or grant model of computation that we already know to be equivalent to Turing machines. So, we'll see later on in the course of a small machine that we define, that we can simulate in Java and vice versa. And when you have the Java compiler, what that does is take a Java program and make it run on a simple machine, so those machines are equivalent. And with the Java simulator, we showed equivalence one way with Turing machines and you could show equivalence the other way with a couple of steps. In general, it's not difficult to use simulation to prove computational models equivalent. And what that means is that if you believe that, then there's no need to look for a machine that can compute more once you've got past the two state machine. It's all about convenience and efficiency but not about the kinds of problems that can be solved. And that is very important because it enables us to have a rigorous study of what computation is in this universe if we believe the Church-Turing thesis. And there's a lot of evidence in favor of this because many, many, many models of computation have been shown to be equivalent and this is just a short list some of which came from mathematicians trying to come up with a more powerful models of computation and others that just arise practically as people develop different ways to compute things. In fact, over eight decades, people have developed lots and lots of different models of computation and still going in. They all turn out to be equivalent in terms of problems that can be solved with a computational device, all starting with the Turing machine, this simple machine articulated by Turing as a definition of what we can compute. These universal models sometimes bear a striking resemblance to nature. This is a model called a Lindenmayer system, which is a formal model, not much more complicated than Turing machine but then can be linked to graphical models that makes makes us think well is there computer ability actually to be found in nature? These kinds of questions are profound and important.
