L8: Introduction to Turing Machines and Computations

Turing here stands for Alan turn how many people have heard of him okay yeah quite a bit and might say a little bit more about him during the during the quarter as we learn more about Turing machines and other things that Turing did and this is actually we're coming up to his hundredth endureth birthday sometime in June and all right so I'm gonna introduce Turing machines first sort of intuitively with a couple of examples in a couple of pictures and then we'll as we've done in the past look at formal definitions of muttering machine consists of and what a computation in Turing machine is and then we'll look at some more examples of programming Turing machines so first of all Turing machine has a control which is sort of like what we've been used to it has States and transitions etc so this is almost like a DFA in there but the main difference it's a huge difference is that there's a tape and this tape it's it has an end on the left side but it's infinite on the right side and it's the tape where initially the input is written so ABCD whatever that's the input input but the Turing machine can also write onto the tape so it's a read/write tape read and also right tape and this is called the read head so the turing machine has a read head which is over some particular character on the input tape or on the on the tape the read right tape and in a single move can read a symbol can choose to write or not and can move left or right okay so turning machine moves on the tape but now it's bi-directional when we were talking about finite state machines you were only progressing through the string you could never back up and if I say machines other than PDAs you couldn't you couldn't write anything okay but now we have the ability to write on on this tape and unlike a PDA the writing is unrestricted we don't have to just use a stack okay so it's a lot more freedom and we'll see that that freedom has a lot of consequence in terms of the kinds of languages that a Turing machine can recognize okay but inside here it's sort of intuitive although we will have to really specify and it's it's it's sort of in sense that's it's similar to what we've been playing with so far but we still have to specify exactly what goes on in here and then there are some other differences that it see it first seems small but anyway anyway we have to specify them and one is that in a Turing machine as soon as you get to an accept state you accept so you don't have to have exhausted the input okay and this also is is reflects the fact that you can be writing things on the tape and so on and so you want the ability to accept even if the tape still has things on it or we have a process to everything to the end of course for most languages that you want to for many languages that your in recognizing you need to have seen all the input so that has to be built into the control for how the Turing machine actually works but formally you are allowed to to accept or reject as soon as you get into well you do accept you reject as soon as you get into an accept state you accept and as soon as you get into a reject state you reject so there's there's one specified accept state and one specified reject state okay so let me give you a little bit of example so we'll look at a Turing machine even without having fully defined what a Turing machine is I'm going to show you an example and then we'll define it more more precisely this is a Turing machine for the language B equals W hash W where W is a string now they should be Wrigley's the but it's a binary string okay so W is a binary string and we have a hash and then we have another copy of it all right we know this isn't a regular language right although it is a language that we could accept we could recognize by a PDA everybody I think seen that so let's see what a Turing machine does on this okay okay it's so it's going to make multiple passes over the over the input so here we have written on the input let's say let's say this that we have some input which is actually in the language we have input which is not in the language in which case the Turing machine should reject let's do an example first or think about first what happens with input that actually is in the language and by the way after the input you have a space and we recommend a with that silly empty half empty or fully empty cup or whatever you want to call it anyway that's that represents the space and we have spaces all the way down all the way out okay so this is what the input tape initially looks like the reed hat is initially at the left end looking at the first character and so what what would you want to remember we can move left and right and we can mark we can right onto the tape as replace symbols and inside here we have something that's kind of like a finite state machine it has it has very precise has States and transition rules the transition rules say that when you're looking when you're in a particular state and you're looking at a particular character on the tape you can choose what state you next moved into you can choose whether you're going to write overwrite that symbol with something else or not and whether you're going to move right or left so these are these are the kinds of decisions that the Turing machine can make at every step so what's anybody have any general idea of how you should have a Turing machine should go about checking whether this string is in this language see now we're closer a lot closer to thinking like an algorithm or a program okay admittedly this is a pretty constrained computer but you can think sort of at a high level first and then translate that into the states and the transition rules okay unlike let's say when we were thinking about finite state machines it was hard to think algorithmically at the top level because what you had to altima li translate that into was so low level but here we can think of a kind of a high level idea what's lets anybody have a suggestion for a high level idea yeah we don't know the length of W but we do know that there's a symbol that separates the two copies well okay but at the high level so you're still thinking a little too mechanistically at the high level you want to see the first character here and then somehow remember it run over to see a hash which you can do by these left transit right transition rules and the hash separates the two copies of the two things you hope or copies and then you check whether these two characters are equal okay now we don't have this is not a high level language so we don't have an equality test okay so that all has to be encoded somehow in finite state in the finite state control but if these are two are the same then well we're gonna mark this one off and mark that one off we'll put it we'll we'll change them to symbols that are not in the in the read alphabet in the input alphabet and then we go back here till we hit that till we hit that symbol that was the that show that something was marked off we read what the next symbol is we run back over here till we hit the the last marked off symbol and we read the next symbol and see whether that was equal okay so hopefully everybody gets the high-level idea you haven't seen quite yet how we're going to translate that into the actual Turing machine so this is what the this is the way it's put in the in the block the high-level idea is zigzag across the tape well zigzag means it's going to go forward and backwards and forwards and backwards repeatedly this is eggs a gang to corresponding positions and the two strings that are separated by the hash okay and and check if they're the same okay well this one by the way you really want to think about that you you have in here a finite control you don't have a language which can take two variables and see if there have equal value something like that we're not at the level of a programming language so how is it that that the Turing machine is going to be able to check if they're the same anybody have an idea well one thing I didn't tell you or is that the the alphabet for the input tape this is the input alphabet well actually here we know it's what you know what it is but anyway the imprint alphabet is finite and that's that's a crucial thing here it's just the size - okay so the input the input alphabet only has two different possible characters so when we see a character over here we can move into a state a particular state which is by the virtue of what state it is it's remembering it's recording it's it's reflecting the fact that that what you saw here was a zero or in a different state reflecting the fact that what you saw here is a one okay and then when you go over here depending on what you actually read and based on which say state you are you can do the appropriate thing of saying yes they're equal or recognize that they're not equal and then reject okay so you can encode the fact that what symbol you see by what state you're in and that's that's possible because the alphabet is always finite okay in this case we're working on this particular example the alphabet is just sighs - okay so we'll see that in more detail but that's something we have to do and then we're gonna cross off corresponding cymbals if they are the same well what does cross off mean cross off means we're gonna overwrite those symbols with a a symbol that's not in the in phonetic alphabet okay so we have a tape alphabet which is actually different than the input alphabet that's the tape alphabet [Music] so let's just have a little example here let's say this is 0 1 0 1 - 0 1 0 1 and maybe the tape alphabet has an X in it ok it's it's a symbol it's not in the input alphabet so when when the 0 is read here we're going to replace it with an X which is a good way of crossing it off and we're gonna move into a state here which is a state remembering a 0 the 0 was read and then we're going to be moving right until we see the hash and then move right until we see something that's not an X which in this case is just that 0 so we read a 0 and since we're in the state that's remembering there was that was a 0 then that 1 is crossed off and we're good so far and then that'll move back to the left until we hit the X and then move one place right and we see now oh that's a 1 so now we're in a state that's remembering it were a 1 okay cross it off move to the left here's the hash here's there's an X we run until we see something that's not an X that's a 1 we're in the state that said 1 well that's good okay then we moved back somebody getting the idea and at the end how do you know whether you're whether you're finally finished or not [Applause] when all symbols to the left of the hash are X tau and how do we how do we to determine that so when we're going back left okay we pass the hash and we we make if we see just an X there then we know that all the symbols on this side have been xed out if my provided that my rule was always to go well it the way I said it was you go all the way till you see an X and then you move right one step and see whether there's a a symbol there other than the hash to 2x out so here if we if we hit the hash and we move one place left and we see an X then we go one place back to the right and we see a hash that's it that's something we can route we can identify in the finite control then we know these guys are all crossed off okay when all the symbols to the left are next out check if any symbol yeah on the right of the hash is left if it's right it's left left this way okay it's still there okay and if there is something that's still there then the two sides weren't equal and then you reject if so reject else accept okay now how do you how do you tell whether you've whether all the symbols on the right have been xed out okay so we're Xing out the first one here and the first one here in the second one here in the second one here and so on so when you run to the right you're seeing X's okay and if they haven't all been xed out then what happens you see something that's not an X okay but if they have all the next out then you end up at the right end of of the input of what's been written and you see an empty and empty square okay so so we'll have to take take account of the ability to to know when we're in the right end of the tape okay so this is sort of the you know the high-level logic but it's got to be translated into the actual rules for a Turing machine just the way you translate a high-level algorithm into a program in C or into assembly language or X so most people said you program in assembly language how many people have programmed in machine language you know the distinction between an assembly language and a machine language nobody oh you have okay yeah how many people have programmed by sitting on an old nineteen no I actually did this where I was sitting on the front of some big machine with toggle switches that was how you were programming nobody knows what I'm talking about forget it anyway there are more and more primitive ways of programming that are more and more tedious and programmed Turing machines is more tedious than programming assembly language and even machine language so it's time to start giving you a formal definition of a Turing machine formal definition first of all we have States that's the usual thing and we have a tape alphabet okay and the tape alphabet is actually I guess I should have let sort of come earlier this is the input alphabet so the input is written over some alphabet and the tape alphabet is not necessarily the same but it of course has to contain the infidel foe because the input is on the tape okay so the other the tape alphabet can be richer it can have symbols that are not in the input alphabet and we've seen that okay we've seen that here that we were going to X out some of some of the characters so we need a symbol X which is not part of the input and we need to be able to write a space or in empty space that's that's part of the know that's not the right way would say it yeah the empty space is part of the is part of the tape alphabet that's not part of the input alphabet okay so the strings that you write as input don't contain empty spaces all right then the transitions well it gets it's going to be a function Delta the transition is going to be a function of the states and what you're seeing on the tape and what you're seeing on the tape might be from the input but it also might be from what you've written onto the tape so this has got to be well the tape alphabet and then it's a function from that to what well I've mentioned before what the Turing machine can do it can move into a state I mean it can change its state so definitely we have to put Q there okay it can change its state it can also write on the tape right where the lead head is so that means this next component has got to be what it what from the tape it yes the tape alphabet right good so it decides what it's going to write it's writing from the tape alphabet question it's what you think this should be the infidel and put it know the left side this should be this needs to be the tape alphabet because the the the Turing machine can move back and we saw over here to read again something this it's written okay so if we just if we just had this as the input alphabet then we wouldn't have the ability to reread a Cell on the tape and be reading something that was written there in the tape alphabet but not in the input alphabet okay that makes sense well the input alphabet is contained there because the tape alphabet always contains the input alphabet right okay so definitely the Turing machine decides what state to go into what to write but then I also said it decides whether to move left or right okay so left or right we use L and R to indicate left or right and that's what this is the form of every transition rule okay now there's one thing that's that's sort of implicit in this that we made a big distinction we were talking about finite state machines there were two flavors of finite state machines what were they yeah deterministic or non-deterministic all right so I haven't said I even use those words in describing a Turing machine but if you look at this which word should you use actually that's that's right that's not right but it's close I mean what you're saying it makes sense but it's not right this is sort of a hybrid yes the empty space kind of reminds you of an epsilon but it isn't really it's just another it's just another character and the tape alphabet yeah tape alphabet so no that's not the critical thing that I was thinking of anybody else well this is deterministic because this is from a particular state and a particular symbol on the tape you're making one possible decision every one possible action here that's a particular state that you're moving to a particular symbol that you're writing and then this is going to be a particular left or right okay so the transition rules are deterministic later we will get to non-deterministic Turing machines but right now the definition of Turing machine is that it's deterministic and I think the convention the book is if they just say Turing machine then they mean deterministic otherwise they'll call it non-deterministic Turing machine and then later when it will see it doesn't matter because they're equivalent but right now we want to make that distinction and point that out okay so then what's left we have q0 is the start state and we have Q except is a state in Q that's the accept state and I also mentioned that in the computation of a Turing machine as soon as against gets into the accept state it accepts it isn't required as in in a finite state machine that we've exhausted the input although for particular languages that will often be required in order for the Turing machine to properly accept to reject a string in that language okay so but we allow that that possibility that we haven't seen the whole input I mean maybe maybe we're thinking of the language that of all strings that contain at least one one okay so as soon as you see a one you accept you don't have to see the rest of it but there are many of the languages where you have to look at everything but formally Turing machine accepts as soon as it gets into an accept state and similarly it has a reject state okay as soon as it goes into the reject state it rejects so this is unlike a this is unlike the case of a finite state machine where it had accept States but anything else that wasn't an accept state was automatically a reject state here we just have a specified accept and a specified reject and the other states are not are not or not either and and then of course we also have this formal requirement that the accept state and the reject state are not the same state okay those are different states all right so this is what it means to describe or define define a particular Turing machine and you should be able with enough patience and and playing around you should be able to take this high-level logic and implement it in terms of these kind of transition rules specifying what the states are what the input alphabet what the tape alphabet is and so on and the transition rules so that when the Turing machine starts in the start state and yet has an input on the input tape and then it follows the transition rules that are specified it ends up either as an accept or reject and it ends up in the accept if and only if what was written on the input tape really came from this language B and it rejects no this is equivalent it rejects if and only if this is not from be the input is not from B okay so we'll see some examples of that we're gonna do some Turing machine programming not this example though this one it might be in the book and if it's not in the book then maybe you can do it on your homework your next homework okay so this is a Turing machine and Turing machines do computation so we want to talk about computation of a Turing machine well I said a minute ago that you start in the start state of course and your we know where the read head is at that moment the read head is on the left end of the input of the input and it's therefore we have a state that we're in we have what's being read on the tape and therefore there's a transition roller if you programmed it appropriately there's a transition rule which says what state you go into next what you write on the tape if you read anything over writing where the the symbol is that the read head is looking at and then whether you go left or right okay and then you just keep doing that following the appropriate rule until you're in a accept state or reject state okay so as we're as we're progressing we represent the status of the machine as in a configuration so represent the status I don't want to say state of the machine because how do you spell status status mm-hmm it's a yes no that stays us good thank no that doesn't look right how do you spell status oh okay okay there we go just like a spelled okay all right English just did terrible spelling in English no system makes no sense to me at all I've never figured it out okay so we want to represent the status of the Turing machine of the computation of the Turing machine at any given moment or given step and it's done this way we know that there's something on the on the tape okay so here's the tape and their various things that are written on the tape and we know that the read head is somewhere looking at some symbol okay and so we're going to represent this and this is really the and we're in some particular state okay so we're gonna represent all that by writing down this portion of the tape followed by the state we're in followed by the rest of the tape and what's on the rest of the tape and so that that tells you the whole tape where you are where the read head is and what state the machine is in so this specific one might look like this 1 0 1 1 Q 7 0 1 1 1 okay so this represents this represents the status of the Machine of the Machine M where m is in state Q seven okay because that's written there the read had is right there it's it's the symbol just to the right of where you've written the state and the tape what the tape has on it is 1 0 1 1 0 1 1 1 1 and then an empty space okay so we can we can write down the the status or the configuration of the machine and at each step and therefore follow along what the what the computation was ok so this is just a convention so that you can understand what's in the what's in the book ok and then there's a single step and the single step of the computation the configuration changes ok the configuration if this is the configuration at one at the one given moment of time alright then the next configuration can you say something about what it's going to look like I mean how radically different will the next configuration be from this one can these symbols change and the symbols change you say yes well yeah this is the only symbol that can change ok because in a single step we're going from what state we're in and what symbol were reading to an eye a state which may be the same or maybe different and then we write something but we right it right where the Red Hat is looking so this is the only symbol that might change okay and this might change so these two might be different and then where where is the read head well it could be here that's possible if we do a right move or it could be here if we do a left move okay so we're going to be changing you know changing the configuration and a fairly small part of of the whole configuration all right okay then the book also discusses what happens to the configuration when you're on the extreme left and when you're on the extreme right and it's fairly intuitive okay so if you is the part of the tape before the last symbol which is an a and then you're in Qi so this is this is the situation where the lead head is on the extreme right of the tape right and this is equivalent to you a Qi and then a symbol that represents the space okay so the the change in configuration isn't really that different because you're reading the space the read head is right there and can choose to write there putting something there or not and then the tape can go right or left from here so we can deal with this conceptually in the same way we dealt with the others just by thinking of this as a as an actual symbol which it is in the tape alphabet okay so that's really not not so critical all right the state to start configurations well that's obviously that's obviously we're in q0 that's the start state and then the first symbol on the tape and then the rest of the the rest of the symbols so we're there and then a rejecting or or accepting configuration that's any configuration where we're in the reject state or accept state so a computation of the Turing machine is really a succession of configurations where each one corresponds to a transition rule where each change corresponds to a transition rule so a computation is a series of configurations start in in the start configuration and ending and and accept or reject configuration and each successive configuration whether each successive configuration is obtained and the prior one by use of inappropriate or the appropriate transition rule why this is tedious okay this says what you think it should say I mean we start in the start configuration and then the computation of a Turing machine means it's moving through successive configurations or its we represent its computation by successive configurations but whenever you look at two successive configurations the second one has got to be related to the first one by the application to the application of an appropriate transition rule okay and then ultimately we end up if we if the computation terminates we end up in a reject state or an accept state now I just I just said something that never came up when we were talking about finite state machines and I haven't said yet did anybody hear it the slight of mind I said if it terminates okay so finite state machine always terminated because you read one character at each step and the input was not infinite it was some bounded length okay but Turing machine computations don't necessarily have to terminate we terminate if you end up in a reject state or an accept state but you could certainly have Turing machines that is it specified by exactly what we talked about over there and particularly where the Turing machine just keeps going I mean what you could you should be able to design one like that without without too much thought at this point okay so we need some language to talk about that possibility to distinguish those machines that those computations that terminate in those computations that don't okay so yeah well okay so this you really this is a string and this is a single character yeah I didn't really make that explicit we've used something like that before well maybe we haven't in my other class that I'm teaching when he was this a lot where letters from the lower end of the alphabet refer to individual characters and letters from the upper end of the alphabet refer to whole strings okay so this is a string and then this was the single character and because that's that's what the read head is looking at or anyway might move past then we've we've pulled that out as an individual character okay yeah and here are the same thing we've got a individual character and this is where the where the read hat is and then we have some unspecified string no this is just this is what what it looks like if the read has all the way at the right end of the what's written on the tape not necessarily the input because we may be in a place where the machine has changed the input extended and deleted some it whatever but if it's at the right end then that's equivalent to this kind of configuration and so this looks more normal in the sense that there's something here to the right of where the state is and that's what all I was pointing out okay yeah thanks all right let's take this out okay so the collection of strings that detering machine m accepts okay is called the language recognized by M okay well we use this word before recognized so the we have a Turing machine and given various input strings it does its computation and does one of three things on each on each possible string it's given it runs to ultimately to an accept state in which case that string is accepted or on that string it runs to a reject state in which case that string is rejected or what's the third thing it spins its wheels and doesn't get to either of those states ever it just goes forever okay but the collection of strings that M accepts that forms a language it's a set of strings language we've defined it early on is just a set of strings that's the set of strings that's recognized by M even if M has this property that on some input it it just goes forever that's still defined okay now the book computation computations that don't terminate our said to loop okay I don't like that term maybe I'm anyway I wouldn't have used the word loop here because we've seen computations that can go around a loop as in the finite state machine but that's okay there's nothing wrong with that that's because in the finite state machine we're making progress through the string okay and even though the computation is going back to the same state it was and previously we're still making progress towards ultimately terminating because we're moving through the string okay so loops are not necessarily a bad thing and in fact they're necessary in order to have interesting computations otherwise on any finite state machine the the the amount of computation you could do is just bounded by the number of states you have so you could never accept you can never recognize the infinite language but we know that we we do plenty right they call it they say loops but I would say it's computation that doesn't terminate that's my ramp okay a Turing machine that always halts that is on every on any input always terminates that is it runs ultimately either to an acceptor reject state this is called is called a decider okay so that's a special word we use to represent a Turing machine which its inputs always ends up rejecting or accepting it never terminates or it never has this behavior that it doesn't it doesn't terminate and then a language that is recognized by a decider a language that is recognized by a decider it is called Turing decidable it is very decidable language or just a decidable language okay this lecture has got too many words see some pictures too many too many definitions but these will be your your critical definitions as we go through our cutting our conversation about Turing machines whether the language is merely recognized by some Turing machine is recognizable by a Turing machine Turing recognizable or whether the language is Turing decidable that is it can be recognized by a Turing machine as a decider that can that that Turing machine will always say rejecter except no matter what input it's given as opposed to only having Turing machines which will accept when it ought to accept but when it ought to reject when it wouldn't give an input that's not in the language that machine may say reject and up in the reject state or it may just go forever so that's a major distinction between the two types of types of Turing machines that are available for particular languages which one would you rather have which is the good guy which is the bad guy if you have a particularly want it to be would you rather it be turned decidable or just recognizable by some Turing machine decidable decidable is definitely a good property okay and if you don't have a Turing machine that's a decider for that language and you have a particular input and that Turing machine is just keep just keeps running you don't know whether it's running and will eventually reject or even eventually accept or whether it's in some kind of loop and it's never going to terminate okay so that's that's a critical distinction I mean if you have that and you're in a program that you're running and you're sitting there and you're waiting for it to terminate and it's taking a lot longer than you expect you often say well you know it's just I'll give it another maybe you don't ever have this experience but I do and some of the things that I do you say well maybe if I give it another hour maybe if I give it another day you know yeah I mean whatever you know whatever I can tolerate maybe it will terminate eventually or maybe is this going to go forever and I better kill it so these are important distinctions and the critical distinctions we'll get into all right let's just let's program okay so here's the language a equals 0 to the N 0 to the 2 to the n such that n is greater than equal to 0 first of all what is this saying what's the input alphabet here just zero okay it's it's a unary alphabet I don't think we've seen any those before and the two to the N says it's it's a repeat of 0 to the N times for some n so the number of zeros is a power of 2 okay so this is a unary string we're unary string this well of lengths let me just say unary string so W is contained in a if and only if W is a unary string of length it is a power of two okay so for example what about the empty string is that in this language good I don't think it is yeah I don't think the empty string isn't here because we you the only possibility would be when N is equal to zero but two of the zero is equal to one right so this is that would be a single zero so it doesn't look like the empty string isn't there a single one we just said it was in there because you could take N equals N equals zero so two of the zero is 1 and that's just one zero what about zero zero yeah that's in there because N equals one how about three zeroes that's not a power if 3 is not a power of two so that's not in there and that is in there and so on okay all right is this a regular language a good exam question I'm speaking of an exam by the way I hope everybody remembers that the midterm is not this Thursday but the Thursday after so midterm on that I think it's the 27th of the of October and that was on the syllabus so we'll have I'll say more about the midterm as we get closer to it but it's it's coming up next week all right is this a regular language what would you do - well obviously what you do if you want to prove that it isn't regular languages you have to come up with a DFA for it or an NFA whichever is easiest or a regular expression whichever way is convenient for you but how would you prove that it was not a regular language yeah [Music] yeah I think that would work I think you could you could play that out and make make all that work yeah you could use the pumping lemma to prove that this was not a regular language and so that sounds like a good homework exercise or a good exam question for the midterm okay but now we have Turing machines so you might also think about whether you could do this with a PDA I don't know but now we have Turing machines we've got a lot more power so how do we but still we don't have numbers Turing machine doesn't have well I shouldn't say it doesn't have numbers it can write things on tapes and so on a tape and so you might be able to think about how a Turing machine can actually deal with numbers but we're not going to actually need to have numbers so most of the logic you have to think about in terms of you only have a finite state control in there what are you going to do to recognize whether something is the number of zeros is a power of two or not any idea well let's do a little example not not to turn machine itself yet but just a very primitive way of determining whether some list of zeros if the number of them is a power of two so what is this one two three four five six seven eight power of two okay so one algorithm high-level algorithm that should sound like you could translate it into a Turing machine the computation of a Turing machine is to make multiple sweeps here and cross out every other zero that you encounter okay so the first time we sweep left to right we're going to cross out one let's cross that that one cross out that one cross out that one okay and then go back to the beginning and again we're gonna cross out every other zero we encounter but now we also are going to be encountering exes right so you encounter ex you don't do anything about that cat or a zero okay then you encounter an ex don't do anything about that then you encounter a zero well that's not if I said I said we're gonna cross out every other zero we encounter okay so is this the ever your the Emmy every or the other it's the one we shouldn't cross out right we crossed out that one so we're not going to cross out that one okay that one we crossed out okay and then we don't cross out that we hit the and we recognize we're at the end and we go all the way back here and we sweep again X X X ah here's a zero okay so we cross that out xxx here's another zero but that's the one we don't cross out okay hit this one go back and then go back here and cross it out so yeah and then we have all the x's and if you think about the logic of what I was doing every sweep is is crossing out half there's roughly half of the zeros that are there every other one so if we end up crossing them all out then that was a power of two if if we don't then it wasn't somehow that I believe that's right but it doesn't feel right at the moment we don't think about it okay okay so here's how we're going to encode that and the Turing machine I could write down all the actual transitions but that's tedious so again we're gonna have a diagram which shows you what the turret the logic of the Turing machine is and that diagram has shorthand in it so let me write it down and then explain it to you q1 is the start state I pointed this out before the book has an inconsistency it doesn't really matter as long as you keep your wits about you in the definition of the start state of a Turing machine it was accuse ero but a lot of times when they're actually actual start states in diagrams that's q1 doesn't matter here we have the year that goes into it that's okay there's only a little piece of the Turing machine of the diagram but let me explain what these what these are saying this is saying that if you see an X if your now let me make sure I know what this means hold on a second okay yeah let me just give another piece up here so I can explain that one too - okay so that means that yeah so if we're in state Q 1 and we see a 0 then we're going to write a blank and we're going to move to the right okay so this is encoding the transition rule and move to Q 2 so this is encoding the transition rule that says state Q 1 this is what you see and then this is what you're going to write and this is where you're going to move on the tape and this is what state you move into so all the components of a transition are represented by this piece here but here we have something that looks a little bit different that's what I had to check to see exactly what this meant and this means that if we see a blank then we're going to move right and we're not going to write anything there's nothing that's written and here if we see an X we're going to move right and nothing is written and we move from state q1 to the reject state now you're not going to see the logic of the whole thing here till I put in much more but I wanted to write this just to start showing you what this shorthand means this is what you're looking with the what the read head is looking at this is a state you're in the state you move to what's written and whether you're moving right or whether the read head is moving right or left okay so okay let's just look at this thing so here we're looking we're seeing exes that's the symbol we're using for marking off characters we're marking out the zeros we're seeing exes and we're not writing anything we're just moving right okay so this is this is a part of the computation that I was talking about earlier where you're just zipping through whatever X's you see all right and then here this is you're seeing the right end right the right end of the of the tape because you've hit the fifty blank okay so you're if you're zipping through the X's you're seeing X's and then you finally hit a blank you're gonna go right and except now we have to see the rest of the machine to know this is the right thing to do but as I'm writing this out I want you to think about the basic computation I was showing you earlier where we're going to make multiple passes Xing out every other zero and then finally if we end up through everything and everything is is xed out and we hit a blank then we accept and that's this is part of that implementation zipping through X's moving right each time not writing anything on the tape and then finally we hit the blank at the end we go right and we accept okay well what happens if we see a zero if you see a zero what this is saying we we want some part of the Turing machine and it's if this is sort of like a finite state machine at this point we want to build some states and some transition rules that say X out every other zero that you see okay so if you think about the initial computation or computation from here you're saying here's a zero you're turning it into a blank that that's that's so we can detect when we're on the left end by the way we don't use an X in that case we just use a blank and then either you go right now you're just seeing X's now you're seeing you're an O and you want to X out every other one so you X that went out you go in right and you move into q3 and now you might see a lot of X's again so you're zipping through those not doing anything with them just in here and here you see another oh but you don't want to you don't want to you don't want to exit out here we X I don't know so the next oh you see or next zero you see you should not X out and that's what's done here but then the next one you see you should X out 0 goes X R okay so you can see what this is doing is every other this whole piece in here every other zero is being X down and in between those every other zero might be many X's that's okay you just zip through them you zip through them but every other zero that you see is X doubt so this 0 is read but you just move right without writing anything and then here you'd change that zero to an X and you keep doing that okay what else do we need need something up here Q five empty string goes empty string goes left okay so what's happening here here you're you're Xing out every other zero and you finally hit the right end of the tape you see the blank it's the right end of the tape and so what should you be doing now you need to go left back to the left end of the tape right so here's your first move to the left and then we'll have here zero you go left X you go left so this is just this is just the part of the control that's going back it was at the right end at zipping all the way back to the left end how does it know that it got to the left end how does it know when it gets to the left end well remember here in the first zero that you saw you turn it into a blank okay so when this all of this zipping around finally hits a blank then you know you come back to the to the first guy so really this first one shouldn't have an X data should have been made of blank in terms of this logic the basic logic of evaluate that that should be made of a blank according to to this logic and according to the ability to in order to have the ability to recognize when you're at the left end of the tape so here we go we're seeing a blank and what so the tale of the tape move now we read head move now so when we see a blank at the left end where does the read head go it goes right okay so that's that part and then we have this one empty goes reject so what's happening here is that we're seeing an odd number of of zeros and an odd number is never a power of two now if she was never an odd number except for one no that was that was somewhere here somewhere and so there you if you hit the right end you want to reject okay I think I've written it all up and I think you're going to have to look at this yourself to convince yourself that this really works and convince yourself of what the high level logic is that really works so if you this is in the book I'm in this class I'm trying to stay very close to the books oh by the way I meant to pass around your homeworks homework too so see how far that gets so this is on page 144 so take a look at that and trying this out with some examples we're with number of zeros there's a power of two and when the number of zeros is not a power of two and and just convince yourself of how this is working what these notations mean and that the logic the general approach is working okay what I have next is another example but we're kind of running out of time and so I'll do the next one next time but well it'll be an example of how a Turing machine can actually do some arithmetic so let me just show you well those pages are going around what's the next language is that we're going to look at the C is equal to a raised repeated I times B repeated J times C repeating K times where I times J equals K and I J and K are greater than equal to 1 so we're going to see that the Turing machine can do multiplication it can it can check whether basically I times J is equal to K but it's doing it in a very tedious way whether the number of A's times the number of B is is equal to the number of C's but again multiplication is something if you try to do that with a finite state machine I think you'd immediately you'd get stuck and have a good intuitive appreciation for why something like that is very difficult on a on a finite state machine and but when we're programming Turing machines then you'll see that that's possible I'm showing this week okay we've got a couple of minutes left but this is a natural place to stop and

Channel: UC Davis

Views: 53,012

Keywords: Turing, Machines, decidable, languages, recognizable

Id: eq2bvb8xE78

Length: 74min 56sec (4496 seconds)

Published: Thu Dec 13 2012