We're going to begin by extending the abstract machines that we talked about in the last lecture. They're very simple machines to try to get to a point where we can have a model that help us understand computation the most basic possible way. So, here's a starting point, really the way Turing thought about it. So, our goal is to develop a model of computation that encompasses everything we know about computation, every process that we use to compute things. And we want to make that model as simple as possible. So, think about the mechanical process of adding two numbers. So, this is a very familiar computational process. We take the two numbers and compute the sum and then perhaps, there's a carry. In this case, the carry zero. Now, we compute those and we get a 2 and we have to carry the 1. Now, we add the three 1s and we get a 3, and then that's going to carry of a 0, and then 3 and 7 gives a 10, which we have a carry of 1. And eventually, bring down that 1, and we have the result, the addition of the two numbers. Now, it's a simple process. Let's think about its basic characteristics. It's discrete, we do one thing at a time. Maybe we have a small part of amount of memory to carry the few digits that we're adding together in the carry and so forth. It's local, we move from one place to another that's pretty nearby. We're not jumping to a place a mile away ever in this process. And it's got states. We're always doing something. It's kind of a well-defined that we're in a certain state with a certain amount of data, and then that's going to tell us what to do next. Those are the basic characteristics that Turing wanted to have in his machine. Now, in the previous lecture, we talked about discrete Deterministic Finite Automata. And that's an abstract machine that solves a pattern matching problem. So, just to review how there's a string on an input tape, no input on it, no limit on its length, the machine reads each character once moving left to right, lights up "Yes" if it recognizes a string, and "No" otherwise. And each DFA defines a set of strings. That's all the strings that it's recognized as that's the purpose of the machine. And we did an example of a machine to show how they're built. They have a finite number of states. Each one's labelled Y or N. We have transitions between the states, each labeled with a symbol. One of the states is identified as the start state. We begin there, read a symbol, that symbol tells us which state to move to next, we move to the indicated state, and we repeat until the last input's been read, turn on "Yes" or "No." And we did a simulation of this particular machine which recognizes all strings whose number of Bs is a multiple of 3. In this case, it winds up in the "Yes" state and lights up the "Yes" light. So, that's a very simple machine that has all the characteristics that we thought about in the example where we're just adding numbers. And we saw at the end of the last lecture that there are some things that we can't do with this machine that we'd like to do. So, what we're going to talk about now is the equivalent to the model that Turing came up with called a Turing machine. It's like the DFA but it's got a few more things that it can do. It's an abstract model of computation again. We have a string specified on a tape, no limit on the length of the string. The Turing machine now can read but it can also write characters on the tape. And it can move left or right. It's not constrained to just move in one direction. And again, it's going to light "Yes" if it recognizes a string and "No" otherwise. But it also might halt and leave some result of the computation on the tape. So here, the differences with DFAs, it can write. It can move left or right, and it might halt and leave a result on the tape. Very simple abstract machine with just those extra capabilities over what we saw with DFAs. That's a Turing machine. Now, Turing machine, to find his machine's mathematically in terms of tuples that define the states and relationships among tuples, but this graphical model is just as formal and accurate description. So, we're going to look at the details of a couple of Turing Machines. They're quite similar to the DFAs. So, again, we have a finite number of states, each labeled Y or N but also H, L, or R, for halt, move left, move right. And we have transitions between the states the same as before. But now, on each transition, there's a pair of symbols. One of them is the input symbol and then the transition tells what state to go to if you see that input symbol. Then there's a call-in and then an output symbol which says write that indicated output over the one that you read. The other thing is if the state that you're going into is labelled L, then move left. Otherwise, move right. And keep going until you get to a state labelled "Yes" or "No" or "Halt" and turn on the associated light. So, we'll look at an example in a second but let's talk again about the similarities and differences between DFAs and Turing machines. They're simple models of computation. They have input on the tape that's a finite string, but there's no limit on the size of the tape, finite number of states. The state transitions are determined by the current state and the input symbol. The differences are with the DFA, you can read input symbols from the tape, with the Turing machine, you can read or write, read from the tape or write onto the tape. DFA, you can only move to the right. And every time you read a symbol, you move to the right. With the Turing machine, you can move in either direction. DFAs, the tape itself is finite. It's a string. In the Turing machine, there's no limit on where you can go on the tape in either direction. In DFAs, we go one step per input symbol, few of N characters on your string,then you can only do N state transitions. With the Turing machine, there's no limit on the number of state transitions that you can do. That's a big difference. And again, DFAs, all you can do is turn on "Yes" or "No", but with the Turing machine, you can also leave output on the tape which gives a great deal more power to that machine. But the basics are very, very similar. So, let's look at an example. So, this is a Turing Machine, a three-state Turing machine that can decrement a number given on the tape. So, in our notation sharp sign is just an empty symbol on the state tape and we can assume that wherever we go, there's going to be a sharp sign on the left or right. And then our input is going to be a binary number on the tape. And we start in the state labelled R at the left of the arrow from nowhere coming in indicates that's the starting point. And we're starting with the tape head on the leftmost symbol that's not blank in this case, the 1. So, what this machine does is going to move to the right as we come into the start state. One thing to note just to keep the notation down is that if we see zero and write zero and stay in the same state, we don't bother drawing those. So, in this case, there's an implicit, I saw a 0, I saw 1, I write a 1, and I stay in the same state. So, omitting those makes the machines much simpler where there's lots less state transitions. So, if you see a symbol, write that same symbol and stay in the same state, we don't put that in that transition there. So, if you're on a symbol and you're in a state and you don't see an arrow with that symbol, you can assume that you stay in that same state, and don't write over the symbol. So now, we're still in that state and we see a zero, it's going to write a zero and move right. So really, what this particular state means is scanned to the right until you find a blank. And so that's what we'll do. In every case, see it, rewrite it and go back into the state. When you go back into the state, you move right. So, now in this case now, we see a blank and then we write a blank but we move to the middle state. And that states is an L, so we move left. Now, what we do is we're in that state in the middle that says if you see a zero write a one and stay in the same state. So, you write a one and then going back to the same state, move left. So, what this one is doing is writing ones as long as you see a zero. Now, at this point we see a one, that point we write a zero and then go to the halt state. So, our input was 1 0 1 0 1 0 0 0 0 and our output is what's left on the tape is if that's a binary positive binary integer. What we've done is computed the result of subtracting one from that integer. That's a binary decrementer. So, just one point about this. What happens if we try to decrement zero? So, if we happen to have the number zero on our tape, that's fine. We find the blank. But now we're going to go left looking for a one, and we're not going to find one, and this Turing machine doesn't halt. It'll keep scanning over the blanks looking for a one. Remember the tape is infinite in either direction so it'll never halt. So, this is a bug. A Turing machine can have bugs just like a Java program. So, in order to fix that bug in this case think about what we need to do. What we need to do is at least if we see a blank, go transition to the halt state and then maybe decrementing zero, we have an overflow. You want to do something different, you could as well. The main thing this fix does is avoid the infinite loop. Okay, so, that's an example of a complete Turing machine that does a useful computation. Here's another one. This one is supposed to increment a binary number. Now, the input is 1 0 1 0 0 1 1 1. When we increment that we do kind of opposite computation. We want to change all the ones to zeros and then the rightmost zero to a one. So here's the Turing machine that gets that done. Again, we scan to the right until we find a blank. And at that point we know we're at the rightmost endpoint of the number. See the blank, so we go into the state at the middle. State at the middle if we see a one we write a zero, and we keep doing that as long as we see ones until we see the first zero, the rightmost zero in the input. If we see that we write a one and halt. That's then the output when we halt, and so we take that input to that output which is adding one to that binary number. So, already we're doing familiar computational tasks with this quite simple machine, and with a little bit more work, we can develop machines to do more complicated tasks. Just by the way, this one actually does keep incrementing, making the number bigger. If you have all ones, it'll make them all zeros and then it'll change the blank just to the left of the number to one. So, it'll actually grow the length of the number by one. So, this will just keep counting and incrementing without stopping, increment any number. Now, we can put these two together actually to make an adder, a machine that can add two numbers. That was kind of one of our original goals. So, what we're going to do is here's the plan to compute x plus y. Now remember, when we're looking at this that we're not going to talk about efficiency today. We're just talking about whether we can do it or not. Next lecture, we'll talk more about efficiency. Right now we're just interested in is this, is machine powerful enough to do the computations we want to do? Is there some way to do it? And then we can worry about doing it faster and better later on. So, here's how we're going to compute x plus y. So, we can say we have two binary numbers with a plus sign in between. That's our problem, and what we want to do is replace that problem by the sum in binary. So, the plan is move right until we find a blank and that'll put us at the right end of y and then we decrement y. Every time we decrement y, we'll go left to the left of the plus sign and will be right at the right end of x. We just decremented y and now we're going to increment x. Then, we'll just continue doing that until we decremented y equals zero. So that means, we started with y, we decremented by one down until we got to zero and that's when we can tell that if we come to the plus sign when we're looking for a way to stop our decrementing the case that we did when we're trying to decrement zero. Then, in that case we know we get to y equals zero. Every time we decremented y, we incremented x. So, that's going to give the same result as adding y to x. So, then we just clean up by erasing the plus in all those leftover ones and what we're left with is the sum of x and y on the tape. So, that's a strategy for computing x plus y and it's an example of a Turing machine that can add two numbers. Again, quite simple formal abstract machine, but it can start to do more complicated tasks. You can start to see as well if you can do that, then you can maybe multiply in the same way and so forth, and sure enough you can. So, anyway here's what the binary adder looks like. It's a combination of our decrement machine and our increment machine and then in the middle one that cleans up. So, we start at the bottom left and then find the right end and then move up to decrement y. So after having done that, then we go on we increment x. And you can follow through the details of this offline. I just want to show the basic plan. So then increment x and then just now we keep going and doing the same thing, decrement y and increment x until we get to the point where we tried to decrement zero and we got all ones and ended at the plus. So then we go into the middle to clean up and eventually come to the halt, having computed the sum of x and y. So, with just six states in the combining the two machines that we've talked about, we have a Turing machine that can add to binary numbers. Not too bad. That's a basic computation that we want to be able to perform and we're able to perform it. So, that's an introduction to what a Turing machine is. Now, what we're going to want to do is the same thing that we did with the DFA. We're going to want to write Java programs that can simulate Turing machines. They're quite simple abstract devices and we should be able to do that. The main task that we have to accomplish is simulate this idea of simulating an infinite tape. So, that's what the machine has. The DFA didn't have that. It just had a finite tape. So, what we're going to do is use two stacks to simulate a tape that's infinite on both ends. We know what the stack abstraction is, so now, we can write Java programs that take care of that. And that's taking advantage of the idea that when we build a stack, we don't have any limit on the size of the stack. And that same idea is going to give us infinity in each direction. So here's what it looks like. So, we're going to have a left stack and a right stack. So, that's everything to the left of the tape head and everything to the right of the tape head, and we're going to assume that the current character being read is at the top of the right stack. So, you can see those two stacks, which the one on the left is everything to the left of the tape head. But we don't keep the infinite blanks. We just keep one blank representing infinite number of blanks to the left or to the right. And as we keep pushing, then we are adding to the size of the stack but we still always carry implicitly the idea of unlimited amount of tape. So, what do we do to read a character? Well, if the right stack is empty, that means there's nothing under the tape head except a blank. We assume that it's a blank. So we return a blank if the right stack is empty. Otherwise, we pop the element from the right stack. That's what we're going to return as what was under the tape head. And then now, the next thing that we do is going to be right and whatever character that we're going to write in our Turing machine, we always read and then write. Every time that we read a character, we write some other character. So, we're going to call right exactly once after each call on read and that's implicit in this implementation. So then, whatever character is supposed to be written gets put back on the right stack, and the tape head then we'll be on top of the right stack, and it'll contain that new character that was just written. So, what about moving to the right? That's the other things that we have to be able to do with our tape. We have to be able to move the tape head to the right or move it to the left. Well, again, if it's empty, then moving to the right is putting a blank on the top of the left stack. Otherwise, what we put on there is what we get from popping the thing on the right stack. But most of the time, move to the right means just pop the right stack and push it on the left stack, then the next character on the right stack is the one the tape head is under. If it's empty, then we have to put a blank, and moving to the left does the opposite. If the left stack's empty, we push a blank. Otherwise, we pop from the left and push that on the right. So with two stacks, we have a very simple implementation of the basic operations that we have to perform for Turing machine. Given the basic facility that we just talked about using push down stacks to simulate the operation of a two-way infinite tape, then it's easy to write Java code to simulate the operation of a Touring machine just extending what we did for DFAs. So, again, we have an instance variable, which is our current state and at start state, and then we have an array of characters which tells us for each state what action we're supposed to perform before we wind up in that state. And then we have an array of symbol tables, which tells us for each state which state we should go to for each possible character, and then we have another array of symbol tables which tells us for each state what character we're supposed to write out for each given input character. So, for example, if we're in state one and we see a 1, then we should write out a 0 as indicated in the diagram and as indicated by the center element in the center row in the rightmost array. So those things that provide all the information that we need to go ahead and simulate the operation of a Turing machine. So, our constructor is just going to fill in the data structures, and then to simulate the operation of the Turing machine, we go ahead and start in our start state, and then we take our input from standard input and just push it all on the on the stack. And then now, our right stack has our input and then we can simply move through the machine as indicated by the state transitions in the rugs. As long as their action is not the "halt", then we read a character and then that character, depending on what state we're in, we go to the symbol table associated with that state and we get the character that we're supposed to write, and then we go to the other symbol table and we get the integer associated with that character, which tells us what state to go to next. And then, depending on whether that state is an R or an L, we might move right or move left. And that's the whole thing. We just keep going until we find a "halt". And if we do get out of there, we return the action associated with the state that we're in. And then our mean is going to be similar to the mean in DFA, which just reads a string from standard input and runs the machine on that. So, in here, we're using TM as abbreviation for Turing machine and a couple of different places. So if we read, this is the Turing machine for our decrementer. So if we give it the strings 0 0 0 1 1 1, then it decrements anything that we might want to put we can decrement. So very simple Java program that we can use to simulate the operation of any Turing machine. All we have to do is, then if we get all 0s or we get all 1s and so forth, all we have to do is provide a full representation of everything about the machine. We need the number of states, we need the alphabet, the number of specific different characters that might be on the tape and, we need to start state. And then, for every state, we need its type or its action. The transition is that for every character tells us what state to go to next and then the alpha characters which tells us for every character what character to write. That's a complete description of the Turing machine. And given that, this Java program can simulate the operation of that machine on any input. That's what we use to study the behavior of Turing machines. Is this program and all the examples we give are the result of running this program? But it turns out that the ability to do this is actually quite profound, and that's what we're going to look at next.
