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.