Turing Machine Example
Resources
Video Script
Hello everyone in this video we’re going to take a look at a detailed example on how a Turing machine may actually perform a common operation that we would do with a regular program. Remember that our Turing machine has eight simple instructions that it can execute using the control arm or the the reader that the machine or the program is actually loaded on. But it can simply move left or right one, it can write ones and zeros and it can also read and also jump around in the program as well. So these eight simple steps remember represent a truly universal computer given enough time, and given enough memory, it can perform any operation any other real world computer could actually do. So here’s an example of a basic program on our Turing machine. So our reader or the Turing machine itself would be preloaded with this program. In this situation, we’re going to assume that we start with two elements or two items or two pieces of data on our tape. And these items, remember, all we’re dealing with here are ones and zeros, nothing else.
So we’ll start with two binary digits on our tape. And then the program has just a finite number of steps here, so steps one through 11. And you can see here we jump around a little bit. For example, in step one, if we read a one on the tape, then we’re going to jump to step number five in our program. So the go to number five isn’t a step to number five in our tape, it is go to number five in our actual programs, line five in our program. For this example we’re actually going to do here is we’re going to step through our program overall and try to figure out what kind of operation it’s actually trying to perform is just looking at this straight up. It’s kind of hard to tell what we’re actually trying to accomplish or what the Turing machine is actually trying to accomplish.
So let’s work out this example here. So since we only start with two binary digits on our tape, that really means we only have four possible combinations in total, right, we only have two binary digits to the power of two is four. So this is the number of combinations of those two digits that we might actually have. So let’s go ahead and write to these different combinations out here. We have 0 0. We have 0 1, 1 0, and finally, 1 1. So I’m going to go ahead and label these different cases here. So we can kind of keep track of them a little bit better. So this is case A, B, C, and let’s call this one over here. D Now this is a little bit different than how we would normally actually read things. In this case for my Turing machine, I’m going to read my inputs or start my inputs from left to right. So if we start out our program here at step number one, I’m going to go ahead and just work on example A here first or this data A here first, to our head, our reader, our Turing machine, starts looking at the first square out. Step number one, and our program says if one, go to Step Five. Now, the data that we have here is actually just a zero, so we’re not going to jump to step five. So we’ll actually just continue on and go to step number two.
Now notice that my head over here, or where my Turing machine is actually reading from does not actually move until I tell it to. Now step two does tell us to move left. And so you can either imagine this as the head moving left, or the tape moving in the opposite direction. And so what that actually causes us to do is we’re going to no longer be in that spot are going to move on to this square. So then let’s continue on to our next step here. So we already move left and so we’ll keep on executing our program sequentially. So at step number three, we have if 0, go to step nine. So if 0 is true. So we were reading a 0 here, I’m going to jump from step three, all the way down to step nine. Step nine, says move left. So we’re going to move our tape over here to this empty square. And then we’re going to go down to the next step, step 10. Step 10 says write a 0. So my, machine is going to write a zero here. And then we’ll continue on to our next step of our program, and our Turing machine stops. So our output here, this is our output, what our machine actually wrote out as a result of running our program, given the starting data.
Let’s continue on. Let’s go and look at another example here. So if we look at our second data set here, we are going to again, start at our first position here. And start out at number one on our slides over here or on our on our list over here. So if one, go to Step five, and so this indeed is a one. So that is that is good. And so we’re going to skip steps two, three and four, and go down to step five. Step five tells us to move left. So I’m going to move left here. And that’s step five. And then step six says move left again, though, we’re going to stop that, move our Turing machine, head over one. Step seven, tells us to write a one. And then we go down to step eight, and that says, Stop. So this was the result of doing our data B over here. This particular example. So our first one, we read two zeros and output at zero. In this case, we read a one. And then we, we moved over to zero, but we didn’t actually read this one, right? Remember, we didn’t actually read the second data piece, we only read our first piece of information, and then we skipped over zero and then wrote a one in our empty spot. So let’s do more examples.
You still have C, and D to go. So again, we’re going to start out over here at our first piece of information. Step one, right, step one, go to Step five, so that’s not true. So we’re going to jump down here to step number two. Step number two says move left. So we’re going to move left one Then continue on to Step three. That three says if zero go to nine, well, that’s not true because we’re at a, our, our current carrying machine tape square has a one on it, it will go down to step four, which says if one go to Step six, which is true, though, that is true. So we’re going to go to step number six, then that tells us to move left, go on to Step seven. Step seven, tells us to write a one and then the top. So very similar case as what we had for be here where we read a one, skip to zero, wrote one. Here, we wrote as we read a zero, move left, write a one and then output it. And then finally, just to kind of put this last the this dataset to rest here, let’s check out D. This will be the final indicator for what kind of operation that we’re actually trying to showcase here.
So just like what we’ve done before, we’re going to start out at our first square on our Turing machine tape. And then of course, start out at our first step in our program. So if one go to step number five, so our square that we’re at is indeed a one. So we’re going to skip all the way down here to step number five. Step number five, says, move left though, I’m going to move the machine over one. Step six says move left. I’m going to move over one again. Then, step seven says write a one. Oh, well, let’s try to one here and that square and then Stop. So that’s pretty much it for our particular Turing machine example, for this particular program, we’ve covered all of the different combinations of data that we possibly could have on our tape for this particular program.
Now, what kind of operation Could you imagine would actually be represented here? Oh, really, the hint is how the program or what the program outputted when we actually read our ones and zeros out, the only time that we actually out voted a, we wrote out a zero was when both of our inputs here were heroes. Right? So when we had two zeros, so remember, zero meaning false and one meaning true in binary, so, zero and zero is zero. So starting to look like a Boolean operator. So if we come down and look at B. So we have for a we had zero whatever the operator is zero, and that equals zero. So for B, we had, we had one , zero, which is one, for C, we had zero, one. And that was a one. And then for D, we had one, one, which is one. Now, what is the binary or not that sorry, not the binary, the Boolean operator that unifies all of these statements. Well, it’s not AND right, because if and was the operator here, this would output false ,right, so one and zero would be zero not one, or true and false is false. So it’s not that and it’s not the exclusive OR either because exclusive OR would have made D equal false. So one XOR one would be to write because XOR is one or the other, but not both. So really the only to the left, the only Boolean operator that takes two operands right, left hand and right hand side, the only one that we have left is OR so if we put OR here, zero or zero is 0, 1, OR zero is one, zero OR one is one, and one OR one is one. So this Turing machine is simply OR Or you can, if you remember from the Boolean algebra, right, it’s For our examples that we’re going to be doing in class other examples that we’ll be doing in class will have you try your shot at trying to analyze a Turing machine program to figure out what kind of Boolean operator it may be, or even making your own Boolean operator program as as a Turing machine.