Overview of Decidability and Undecidability

Okay, so I'm actually going to record this at the same time, so I'll be able to upload it later in case the stream quality sucks. So these three problems were decidable, and what we saw was that the acceptance problem for CFGs was decidable as well as for emptiness. And so the main ones that we did not answer are these four right here. We didn't, we don't know whether or not, we can test whether two CFGs have the same language or not. Yeah, so I'm getting quite a lot of dropped frames now, which is kind of crummy. So what we're going to do today is we're going to answer these four and more. So what we're going to do is we're going to tackle this one. then emptiness for Turing machines, and then equality for Turing machines, and then equality for CFGs. It seems weird that we do it in that order, but there's actually a very good reason for doing that, because some technology that we need to use for this problem will need after we do these three. So the first one I want to do is to talk about the ATM problem, which is very similar to the ADFA and ACFG problems, where instead we have a Turing machine as being the first parameter of the input pair. And of course, W is in the language of M. So this is exactly the same thing as ADFA, except now we have a Turing machine instead of a DFA. And what I claim... that this problem is undecidable. So there is no algorithm to to decide this. But we know we can actually show that this is recognizable. And how do I show that it's recognizable? Well that means that if we have a pair M's and W's If it really is in ATM, then I need to accept. That's what it means to be a recognizer. You accept on the strings in the language and you don't care about the other ones. So to get a recognizer, what we do is we say on input MW, where M is a Turing machine and W a string. and I don't care about what the encoding is as long as it's some encoding that we can understand. So the first step is just to run that Turing machine on the input string. Now this step might take forever, but that's okay in this case because we're only making a recognizer. And then we will accept if m accepts w. So if the machine said, yeah, I accept that thing, then we're just going to say yes. So effectively, we're just doing what the original machine would have done. It's okay here that this step might run forever because Turing machines could run forever because we're only concerned about making a recognizer. If the machine runs for forever, then it's never going to accept anyway. And so that's not a big deal. The problem for showing decidability is... if the machine happened to run forever, we need to say reject. We need to actually say reject ourselves. Okay. So how do I actually show undecidability here? So how do I show undecidability? We're actually going to use a proof by contradiction, and this is the standard proof. And the contradiction proof basically goes, if it was decidable, then we can get some kind of contradiction as a result. So what we're going to do first is we're going to suppose that ATM, which will show to be undecidable, was decidable. Suppose it was decidable. God, I can't write decidable. And let's let... uh, each decided. Okay, so H is just some machine we're supposing exists, and it solves the ATM problem. And what we'll basically show is that either H has a contradiction or it can't exist, or both. So what it does is, if we give H some input MW, it either says accept or it says reject. Because... It's a decider. It must always halt because that's what it means to be a decider. So it says except if M accepts W and rejects otherwise, which means that it either outright rejects W or it runs forever. One of those two. And it doesn't matter which. So H must say reject regardless of whether it runs forever. or it outright rejects the thing. Okay, so what do we actually, how do we actually use that? Well, what I'm going to do is I'm going to, the step I'm going to do here is I'm going to build a contradictory, contradictory machine that only exists. if H does. So the only way that this machine that I'm going to make next can exist is if this H exists. And H is the decider for ATM. So this machine that I have to build has to be contradictory in some way. And it can only exist if that machine H does. And if... because this machine is contradictory it therefore can't exist and then therefore H can't exist and so therefore ATM is undecidable. So how do we actually use that here? So here's the machine I'm going to build. I'm going to call it D for no reason. So D is going to take some input M which is all that it's going to take is where M here a Turing machine. So it has no input string, it's just the machine itself, nothing else. And the first step it's going to do is going to run that decider H on this. So I provided a Turing machine to H, but H also needs the input string after it. So then what's the input string? Well I'm going to feed the string the encoded string of the machine. So this thing is the input string to m. So that's just the input string. And the second step is output the opposite of what h does. So whatever h says here. it must say accept or reject whichever one of the two it is, we do the exact opposite. Okay, so this machine seems totally logical in what it actually does because it just runs a machine and it outputs something. And we've we've outputted the opposite before so that's not inherently an issue. So what we can actually see here based on these two steps right here is that d is a decider too, okay? Because all of its steps run in a finite amount of time. Clearly, the first one does because H is a decider by assumption. And the second one, clearly, it runs in a finite amount of time. So D is a decider for whatever language it is. So therefore, it must say accept or reject correct. on all strings that it gets. So no matter what Turing machine this thing gets, it's going to say the right answer. It is going to say accept or it's going to say reject. So like we did with the H machine, let's actually understand D's behavior. So it's going to get a single machine M and because it's a decider, it must say accept or it must say reject, one of the two. it'll say except if So the behavior of this machine is if, I'm sorry, not m. So if that Turing machine that it got rejects, or actually I should say, yeah, I should say does not accept its own encoded string. Because the d machine. says output the opposite. So if D said accept in this step then that means that H said reject in the first step because it does the opposite. So that means that M does not accept its own string as input which is fine that's possible and it says reject if M accepts its own encoded string. Because again, the D machine does the exact opposite of what the H machine said. So D is kind of doing the opposite of what the H one said. So this seems totally logical because M may or may not accept its own string, right? And so therefore, we just do the opposite. There seems to be no contradiction here. So the key to understand this is that the D machine must say the right answer on every Turing machine. every single one, including itself. So what happens if we feed D's own string as input to itself? So D on its own input string, well, it's kind of like this one up here, except I'm going to substitute D for the M up here. So it says, except if D... because there was an m here, I'm going to put d here. If d does not accept d, wait a second, so it says d accepts its own input string. If d does not accept its own input string, that seems kind of contradictory. Well, let's try the other one. Well, it says reject if d accepts. its own description. Wait, so wait, it said D rejects its own input string, its own string, if D accepts its own input string. Wait, so that means that D on this input cannot have said the right answer, because it's a contradiction no matter which is the case. Ah, so therefore, D is contradictory, is not a decider. So D not decider and actually can't exist because it doesn't report any answer here and and so therefore it cannot possibly exist which means that the H machine up here could not exist because the only way we were able to build the D machine is if we made the H machine and that since we can't make the D machine that means we can't make the H machine and so therefore ATM is undecidable. All right, so this implies that ATM is undecidable. All right, so that's a little bit complicated. I completely understand. So if that was complicated to you, watch the stream again. Maybe I'll upload this because I'm recording it now. Hopefully the recording works. Hopefully, let's see if it's working. Yeah, it looks like it's working. Yeah, this proof is using diagonalization, exactly. It's a diagonalization type proof. Good. All right, so let's see what's the next one. All right, so one other thing I want to prove which is kind of related and we'll kind of use it here. that I'm gonna have a theorem here which is that L is decidable if and only if L is recognizable and L bar is complement is also recognizable which seems kind of shocking because recognizability You only have to accept the strings in your language, whereas decidability you have to halt on every single string, whereas if you just had a recognizer, you don't have to halt on the strings, not in the language. So it seems kind of shocking that if you have a recognizer for a language and its complement, you can get a decider out of it. So it turns out that the forward direction is easy, because if the language is recognizable, it already is recon... Sorry, if it's decidable, it automatically is recognizable because of the definition. and decidable languages are closed under complement. So if L is decidable, then its complement is 2. And so if L bar is decidable, then L bar is recognizable too. And so that's pretty straightforward. So for the other direction, so let's suppose that A recognizes L and B recognizes is a machine for L bar. So A is for the first for L and B recognizes the other one. Though these two machines do not have to halt on the strings not in their language. They're not required to. They just have to halt on the strings that are in their language. Okay the key is to note that yeah I'll actually write it down here. So the key to note here is that every string is either in L or as complement. Every single string. And so that means that one of the two machines must stop on every single, for any string that you pick, one of the two machines must stop, or both, but at least one of the two must stop. So I'm just going to give a sketch here. it's actually not more than this, but I want you to actually think about how this works, which is to simulate A and B, the two machines, for one step each and then check, actually I should say it this way just to be a little simpler, so if A accepts at this point, So if A accepts, then we are going to accept. The reason for that is if A says yes, it's in my language, the string that you gave me, then it's in L, which is the language I'm trying to decide at this point. And so we should say accept it is in there. Otherwise, if B accepts at this point, then we're actually going to reject. And the reason for that is if... the string that we gave us had b said yes it is in my language then it must be in l bar and we're trying to decide the original language l. So if it's in the complement of l it is not in l and so therefore we need to say no we're not in l at this point. And we know that yeah so one of these two will always be encountered by definition, by the supposition that A recognizes this language and B recognizes the complement of it. And so therefore, one of these two steps must occur because we're always simulating for one step each. I can't just simulate on A and then simulate on B because A might run forever. And so by doing this one lock step each, You could do for two steps. There's nothing special about one step, but it's just that it's a finite amount of work for each of the two machines at each point. And so there's no possibility of one machine running forever before you try to do the other one. So this is how you would actually solve this. Alright, so this machine, because each one of these two steps must have encountered at some point, then that means that we will, therefore we will accept or reject in a finite amount of time, and so therefore we have a decider because that's all it needs to be. And we are accepting the right strings and rejecting the right strings because of how a and b were created earlier. A was for l, b was for l bar. All right, so the consequence of this is that atm Bar. not recognizable and the reason for this is if it was then ATM ATM would be decidable because we saw before that ATM was recognizable and so if ATM bar was also recognizable then ATM would be decidable by the result we just did. And so therefore it's not recognizable. All right, so the picture that we have right now is actually a little bit more interesting. So we had regular down here, then CFLs, then we had decidable out here, then we saw that in fact recognizable languages are a bigger bubble. And then we have some languages that are outside the recognizable bubble. So like ATM bar was out here. Recognizable but not decidable is in here. So normal ATM is in there. And then we have all of the usual ones down here. All right. So that's all I wanted to show for ATM. Let's move on to the ETM. In fact, let's update our little table up here. So we now know that ATM is undecidable, so it's not decidable here. Let's figure out ETM, the emptiness problem. So ETM, which is just like all of the emptiness problems before, so M is a Turing machine, except now we have Turing machines obviously, and the language of M is empty. And I want to show you that this is not, I should actually say undecidable, is undecidable. Alright so how do we actually show this? Well the good thing that we're going to do here is we're going to use another proof by contradiction but not nearly as complicated as the ATM one. So we're going to suppose that ETM were decidable. Then what are we going to do here? We're going to, we will show then that ATM is in fact decidable based on entirely on that supposition. So based on this supposition alone, we're going to show that ATM is decidable. And we know that this thing is false, and so therefore this can't be true, and so therefore ATM is undecidable. So how do we actually do this? So we're actually going to try to decide ATM at this point. So the ATM problem had M and W where M is a Turing machine, and W is a string. So let's say that ETM were, I should actually write it as, were decided by, let's call the machine E. So let's say that E here is the hypothetical machine that solves the ETM problem. Then how do we use it here? Well, I can't just feed this M into that Turing machine E right here, because if E says its language is empty, then I immediately know it doesn't accept the input string W here, which is fine. But what if E says no, its language is not empty here? So if E says no, M's language is not empty, that doesn't tell me anything about whether M accepts. this string w. I know it accepts some string. I don't know if it's this one. So what we are going to actually need to do is to make a machine that has the right behavior. So how do we actually do that? So we're going to construct a Turing machine. I'm going to call it m prime. And the way it's going to work. is I'm going to have it take some input, different input x. So this case, x can be any string at all. It does not matter what it is. Okay so let's see. So the behavior I'm gonna have this be is I'm gonna have it have M prime be the empty language if and only if M accepts W. And so how am I going to do that? So step A in here. I'm going to say if X right here the input string to M prime not W, so if it's not the the input string way above here, then I'm going to reject immediately. So the reject in here is for the M prime machine, not the outside machine here. So then here if X really is W, then run the original Turing machine upstairs. the original input w and accept if m does. Okay and that's it. So the behavior of this machine is it's either so the only possible string it could ever accept is when it's equal to w. That's the only possibility and so The language of M'is either the empty set if it does not accept W, if it doesn't accept at this point down here, or it's just the single string W and nothing else. It's not important that it's a single string here for this language as long as it's empty in one case and not empty in the other case. And what we're going to do then is we're going to run the decider for ETM on this M prime thing that we got. So M prime. Okay. So let's see. So now let's figure out what we need to do here. So if E accepts. So then if E accepts. then that means that M prime's language is empty by definition. So that means if it accepts, we will look at what happened here. So that means that it was empty. How did M prime's language be empty? The only possibility is that M did not accept W because if it did, then M prime's language would not be empty. So this statement right here implies that M that m did not accept w before. And so because we're trying to solve the acceptance problem, we need to reject here. Basically do the opposite because we set it up so that the language would be empty exactly when m does not accept w and non-empty if m does accept w. And so otherwise we're going to accept. Okay so we'll accept there because in the otherwise case it M prime's language is not empty which means that M had to accept a W here. And it's clear that this runs in a finite amount of time or maybe not so obvious. So the important thing is that this step right here is purely construction. of a machine. So I'm not actually running M prime. I'm just making the machine and that takes a finite amount of time because I just have to embed the transitions of M into this this M prime machine. And that's pretty easy to do. So this takes a finite amount of time. E takes a finite amount of time by supposition. And clearly the last step runs in a finite amount of time too. And so therefore, this whole machine runs in a finite amount of time and solves the ATM problem, which we know to be undecidable. And so this is a contradiction. So this is a contradiction since ATM is undecidable. And we can finally conclude that ATM. is undecidable. Because if it were decidable, then ATM would be decidable, and we know it isn't. All right, so that's pretty good. So we can finally go check off that, or cross out that one area right here for E sub tm. What about the equivalence problem? You're going to probably guess it's very similar, and in fact we'll show that to be the case. So let's do eqtm, which is all pairs of machines. So m1, m2 are Turing machines. And L of m1 equals L of m2. And you wouldn't be surprised to say that this is undecidable. Okay, so how am I going to actually use this here? So many frames dropped. So what are we going to do here? What we're going to do is we're going to do another proof by contradiction. So this is a proof by contradiction. So let's suppose that again E decides EQTM. And what we're going to do is we're now going to solve the ETM problem. There is a way to do it with the ATM problem. It doesn't have to be with ETM, but it turns out that solving ETM in this case is way easier. So we're going to try to solve the ETM problem. So remember the ETM problem has a single Turing machine as input, where M is a Turing machine. So we don't have, so EQTM, so this machine E right here expects two Turing machines, whereas the ETM problem, we're only given one. So if I'm going to use this supposed decider right here, I need to manufacture or... new Turing machine. So what I'm gonna do here is I'm going to make a Turing machine, I'm gonna call it M sub-empty, which has empty language. Okay, so it accepts absolutely nothing and that's very easy to do. And what I'm gonna do I'm going to run that supposed decider E again on the two Turing machines I have, M and M sub empty. So M is the machine I was given, M sub empty is the one I manufactured, and what we're going to do is I claim that we just need to figure out whether to accept or reject here. So if E accepts because it's a supposed decider, then that means that these two machines have the exact same language by definition, because that's what E says. E tells us whether or not the two languages are the same. So if it says yes, then these two are the same, which means that M had empty language, which means that to solve the ETM problem, we need to say except here. So we need to say except. and then otherwise we will actually reject. And the reason for that is if these two are not the same language then M cannot possibly have empty language. And so therefore solving the ETM problem, if it has not empty language then we need to reject. And clearly all three of these steps run in a finite amount of time because the first one you just make the machine. and it's a small machine, so it's no big deal. The second one takes a finite amount of time by assumption, and so the third one takes a finite amount of time, and so this is therefore a contradiction since the ETM problem is undecidable. And so therefore, we can conclude that EQTM is undecidable. So in some sense, EQTM is harder to solve than the ETM problem. Because if you happen to solve a particular choice of two machines, so this one always has empty language, then we can solve all of the ETM problem. So EQTM in some sense is actually pretty hard. And one thing that you could prove is that EQTM is formally harder of a problem. problem to solve than the ETM problem. So if you do this kind of proof by contradiction thing, for the thing that you're trying to solve, then the thing you're trying to solve is actually going to be quote-unquote a harder problem than the one that you're that you supposedly solve like ETM here or ATM that we did before. Alright so that's that. All right, so I'm going to take a break for a bit because the next one is going to actually take quite a, it's quite a doozy. So I'm going to take a short break and then we will be back with more of undecidability stuff. So I'll see you then. I actually forgot to hit the transition button. All right. So what I'm going to do here is I'm going to prove a whole bunch of things to be undecidable. So what I'm going to be proving here is something called Rice's Theorem. And it's a general tool. to show languages undecidable really easily. Much easier than doing the proof by contradiction stuff that we did before. Alright, so how is this going to work? So the setup is, we're going to talk about non... trivial properties of Turing machine languages. And it's actually pretty simple. So this part right here, ignore non-trivial for a sec. So this is a language which has Turing machine descriptions and nothing else in it. So M is a Turing machine. blah blah blah so something like that so what do we actually have here so in this language right here either oh sorry I didn't say that right so if we have two machines M1 and M2 exist such that the language of M1 is equal to the language of M2, then both or neither of them are in this language. I know that's quite a bit of a mouthful, but the basic idea here is that the only criterion to be in this language right here is what your language is. So if we had two machines that had the exact same language, then the only criterion supposedly for this blue one right here is your language, which means that it's not possible for say M1 to be inside here and M2 to not be inside here. Okay. So it's either they're both in there or both not in there. Okay. So if I had a... thing in here that said if the machine has at least seven states, then this condition down here is not satisfying necessarily. But if it was like say ETM for example, then the only criterion to be in there is if you have empty language. If you have this exact same language, then either you're both empty or both not empty. Okay. And so therefore that would be a property of Turing machine languages. Alright, and then what about the non-trivial thing over here? So this says that the language that thing has, I should say it this way, includes at least one Turing machine. and excludes at least one Turing machine. Okay. I could say that more formally, but that's the basic idea. It has something in there. So there is a Turing machine in there. And it excludes some Turing machine. So it's not the case that every single machine is in here. So if I just said M is a Turing machine and that's it, that is not. non-trivial. And in fact, if you don't have non-trivial here, then you have a decidable language because either you have every Turing machine in there or no Turing machines in there. And you can show that that's decidable. But what Rice's theorem says is this. It says that every non-trivial property... of Turing machine languages is undecidable. Every single one. So for free, we get that ETM is undecidable. We get that testing whether a Turing machine has regular language or not, that's undecidable. Testing if it accepts sigma star, that's undecidable. All of them are undecidable, 100%. So how do you actually try to prove this? So it's actually... very very similar to what we did before but just more general. So let's see, so how do we actually show this? Yes I do. I'm pretty sure I'm, oh okay I did have it, it just was hidden. All right so the thing is that The only thing that we know here is if we have some non-trivial property. I don't know anything about it. About what Turing machines it has, which ones it excludes, I do not know. So let's just let p be a non-trivial property. No, not no trivial property, non-trivial. Need to learn to spell. Property. All right, so what do we actually know here? Well, the way that we're going to work with this is we're going to, without loss of generality, assume Turing machines with language being the empty set are not in P. Okay. And why can we assume this without loss of generality? The reason is, if not, if that's not the case, interchange P with its complement. Because if you have a undecidable language, which is what P we will show to be, those are closed in a complement. So I can just switch it with. the complement and that's also a non-trivial property you can also show. In some sense, not entirely accurate, but it's close. All right, so let's just assume that p were decidable. So again, we're going to do a proof by contradiction. So suppose p were decidable. And let's say that, and let, I'm going to call it T be its decider. Let it be the machine that answers the right answers. Answers the right answers. All right. T says I'm going to be given a Turing machine and I'm going to say whether or not is in this P set right here. And we will show that T cannot possibly exist. How? By showing that if T is a decider, then I can make a decider for ATM. And we know that that's not possible. So to solve ATM, so remember the ATM problem gets... a machine and input. So I'm going to write where m is a Turing machine and w a string. So what are we going to do here? So just like before, we're going to make a totally brand new machine that has some behavior. So we're going to construct a Turing machine I'm going to call m prime, which is going to be input X just like before. No difference there. So what I'm gonna do here, which is kind of weird, which is simulate M on W. So this, I'll draw some arrows, so this M is the one right here, and the W is this one right here. So these are not the T machine for the property. These are the original machines, which is kind of weird in that... you're doing it inside this other machine, but the thing is I can construct this. I'm not running the M prime machine and so I don't have the issue of this being this could run forever. So what I'm going to do here is kind of weird, which is if M just outright rejects W, then we in the M prime machine are going to reject here. But otherwise, we're going to do some other stuff. We're going to run T on X. So from what we've done before, the T machine is for the property P, and the X is the input to the M prime machine. I know there's a lot of machines here. But I'll get you through it. So run T on X and accept if T does. And that's it. So what is the behavior of this thing? So let's actually go through it. So if M accepts W, then that implies that... we will skip the B step right here and we'll proceed immediately to the C step, which means that we will run T on X where X is some arbitrary input. So the behavior of what M prime does is identical to what T does. So that means that the language of M prime is in fact going to be the language of T, which is the property P right here. Is that right? Yeah, I think that's right. Oh, no, no, no, sorry, sorry, not P. It's the language of T. So M prime is going to have the exact same language as the T one. That's what I meant to say. And then if M does not accept W. then that means that we're going to be stuck in this b step right here no matter what. And so we're going to outright reject the x string no matter what. And so the M prime machine then is going to have empty language because we're going to get stuck in this b step and never accept anything. And so because we reject everything its language is empty. So the language of M prime is Empty. Oh, I screwed it. I screwed something up Not let T be its decider. That's not what I meant to say. I meant to say that T Be in the property. That's what I meant to say is using the non-trivial thing Yeah, so because I assume that the language though The Turing machines with empty language are not in the property. I have that there must be some machine with the property that's in the set P. And I'm just letting T be one of those things. And so the behavior here is that M prime is going to be either a machine that has the property or one that doesn't by definition. And so. the differentiator of that is whether m accepts w. So all that we need to do now is run the decider for property p on that m prime machine that we just made and output the same answer. And you can check that this is the right thing to do. Okay. And that's it. So This shows that P is undecidable, this property. And it was just some arbitrary non-trivial property, and then therefore the language is undecidable. Because this is, in fact, a decider for ATM, and we know that one cannot possibly exist. So an example of this. Let's do a quick example. one that I've used on the channel before. It's one of my older videos. So here 3TM is all the Turing machines with exactly three strings in its language. Okay, so it's all the machines that accept exactly three strings. And I claim that this thing is undecidable. All right, so how do you actually do that? Well, what we're going to use is Rice's theorem. So, we're going to use Rice's theorem. So the proof of Rice's theorem is actually quite complicated, but using Rice's theorem is significantly easier. Oh, I haven't paid any attention to chat, sorry. I'm not going to talk about p versus np. I will when I start. Complexity Theory next semester, or I hope to start it next semester. Murphy says love your streams. Aw, thanks I don't know. Why would anyone do so much just for five people regularly? Yeah Although some videos on my channel get quite a ton of views like the academic integrity one I just did it got like 20 times the number of views I normally get so maybe I just have to Put things in my title like don't be stupid or something I'm not gonna actually do that, but it's it's just funny. But yeah, I'm happy for all your support, by the way. All right, so let's use Rice's theorem here. So Rice's theorem says, well, we need to show that this is a non-trivial property of Turing machine languages. So the first step is to show it's a property Ignore non-trivial for a sec. So it's a property of Turing machine languages All right, so how do we actually show this? Well, we need to have two Turing machines. So let's let M1, M2 be Turing machines with identical language. So M1, language of M2, they're the same. So what do we actually do with this? Well, notice that the only criteria to be in the language here is whether you are... whether or not you have exactly three strings. If you have two machines that have the exact same language, then either of them, then they either both have three strings or both don't. And so therefore we get this. So either both languages here have equal to three strings or both don't. which is all that you actually need here, because they're the exact same language, which is key. And then the second one is to show non-trivial. So then I just need to give an example of a machine that has exactly three strings in it, and one that has a different number than three strings. So we could just have a example of a machine A. with the language trying to again getting notifications. So let's let the language of a for example be 0 1 2 and that has exactly three strings. That's easy to make because you can make a dfa for it and so therefore you can make a Turing machine for it and so this implies that a is in 3tm and let's let a machine B have its language being the empty set. You can pick anything else other than that. It doesn't have to be empty set here, but it's just a quick and dirty example. So we have that B is not in 3TM. And therefore, we have an example of a machine that is in there and one that isn't in there. And that shows that it's non-trivial. So by Rice's theorem, 3TM is undecidable. Okay, pretty cool. So that was using Rice's theorem and... showing that a whole lot of languages are undecidable. So it doesn't work all the time. So you can't use this for every single problem. So like EQTM, this will not work because it's not a property of Turing machine languages because it has pairs of Turing machines, not a single Turing machine. But anything that involves just a single Turing machine and something to do with this language, then those are undecidable. So like another example would be regular TM, which is the language of all Turing machines. So M is a Turing machine. And its language is regular. So this is purely application-based. Like if I wanted to know whether my computer program can be just easily done on a DFA, that is impossible to do, to do algorithmically for all possible Turing machines. That's impossible to do. If you substitute this for context-free, it's the same story. Checking even if it's sigma star, that's already undecidable. So... quite a lot here that you can do. You can't prove everything undecidable this way. So you can't prove like emptiness of some other model for example because it has to be Turing machine and you can't have anything other than single Turing machine descriptions or encodings with anything other than their language being the important part. So if you rely on the number of states for example of the machine or something like that, then that is, you can't apply Rice's theorem for those things. Okay, so let's move on to another type of model. So it's something that I'm going to call, yeah, I'm going to call it a linear bounded automaton. as an LBA here, is exactly a normal terrain machine except, oops, I can't spell for anything, except, except all, oops, sorry, except only the cells where the input uh is or was can be accessed so you can't access anything other than where the input originally was so in some sense uh what we have is a finite length tape now so instead of a one-way infinite where you can just acquire more cells if you wanted to we have the input being presented here like this, and there are no other cells available. So to aid us a little bit, although it's not really that important, we're going to adorn this with a marker at the beginning and the end to signify where the input begins and ends, because I can't like shift the input over one position or anything because I'm fixed to where the input is. The key is that the size of the tape that's allowed is bigger when the input is bigger. Okay so the tape is adjustable to the input size whatever that is. So it's unbounded in the sense that the input size can be unbounded but I can't acquire more cells later on. Rice's theorem for non recursively innumerable languages. So that's called the strong rice's theorem. I made a video about it I'm not going to cover it here. Yeah, most feared concept after pumping lemma. Yeah, it's it is for most people So if it's a simulation of a PDA Using Turing machine and finding out whether a string it accepts or not even that's undecidable. No So if you're simulating another machine like a PDA, you can always simulate a PDA. In fact, we showed that A sub CFG was decidable. And so A sub PDA is also decidable. So it's taking a Turing machine as input and deciding or not whether or not it has a context-free language. That's a different question. Here, if you're trying to simulate a fixed PDA, so if you know the PDA in advance and you're trying to simulate it, that is decidable. So here is really a question of whether the input is fixed or whether it... is an arbitrary input and there's a different answer for both. Yeah I see my stream is freezing. I am recording this so I will upload this at some later point. All right so what I want to show is that the a sub LBA problem so like a sub Turing machine but now for LBAs. MW. So M is an LBA and W is in the language of that machine. I want to show, I did this on the channel way back, but I want to do it again. This is decidable. So this thing actually is decidable. So this actually immediately tells us that LBAs are different. than Turing machines because if they were the same then the ATM problem would be the same answer as what the ALBA problem is but they're different. It's because this one's decidable and I'm not going to do the whole proof here. Watch the video on my channel if you want to see the full proof but the basic idea here is that if the input has a length n for example, then the number of possible tape configs configurations is finite because the tape length is fixed here. And the reason for that is, let's actually draw it out. So if I have my tape And let's say that this thing has n cells. And let's say, for example, there are, I don't know what's going on. So let's say that in each cell there are g possible symbols. I should say tape symbols. And could be, let's just say in the state that we're in, one. the set of q states and let's call that little q here. So let's say that there are little q states, there are g possible things I can put into each cell, and there are n cells. So the tape head could be at any one of those n cells. I should write this here. So the total number of possible configs. is going to be equal to the number of tape positions there are, so n, times the total number of possible tape contents, which is g to the n, because I can have g in any one of the n cells. I can have any number of them. And I can be in any one of the q states independently of all that. So that's the total number of possible um configurations. So the idea here is to simulate the LBA for that many plus one transitions. The plus one actually is important here because if you simulate the LBA for that long then that means that you must have repeated a configuration at some point. So if you repeat a configuration at some point, because the machine is deterministic, you're going to repeat it again. You don't know which one is going to be repeated, but you know that one actually is repeated. So the machine that actually simulates this thing just calculates this number plus one and will simulate the LBA for that many transitions. And that's it. If the LBA accepts before then, you accept. If it rejects outright, you reject outright. But if it has not stopped by this point right here, then that means the LBA will never stop because it's not required to stop. And so we can just outright reject because we know the LBA is going to run forever anyway. And so here we can actually guarantee that we will. we can check whether or not the LBA will run forever as a result. And therefore, it's decidable because this number is a finite number of transitions. And so therefore, we can easily do that. All right. So, but in contrast, what I want to do is I want to do the emptiness problem for LBAs. So just to refresh your memory, we have a single LBA here, or a single one given as input, I should say. M is an LBA, and its language is empty. And what I want to show here, that this is undecidable. So it's more than context-free languages. because there we got the A and the E problem both being Decidable and it's not quite to Turing machines because the A problem is Decidable for LBAs. So it's somewhere in between and It turns out that LBAs are equal to the context free language context sensitive language I'm not going to actually prove that here and I'm not going to go into context sensitive grammars and whatnot. But if you happen to know what those are, then they're equivalent to that. All right. So how do we actually show that this is the case? It's actually kind of complicated, but once you see it, it's actually pretty, it's like, ah, that makes sense. So what I'm going to call a computation. history is a string pound sign c0 pound sign c1 pound sign dot dot dot pound sign cm where we have that c0 is the starting config and we have I'll do it this way We have that each one is going to yield the next one in the in the chain Okay, so each one is going to yield the next one and remember that yield just means apply a transition All right. So how do we actually do this? So What we're gonna do is Again a proof by contradiction. I can't use Rice's theorem here because this is not Turing machines This is an LBA. So I got to do something different So again, we're going to suppose it were decidable. And what we'll do is we'll try to solve ATM, just like before, just like the other ones. And if we do, in fact, solve ATM, then this shows that E sub LBA is undecidable. So the question here. I'm not going to write the whole thing, but remember what a supposed solver for ATM says. It says on input M and W blah blah blah. Then what we want to do is in here can an LBA figure out if any computation history that has the last one being accepting exists. So can we have an LBA figure out whether or not this is even possible? So if the LBA is given some potential example strength. like this, can it actually check whether or not this really is an accepting computation history? So it turns out that yes, the answer is yes to this. And so what do we actually need to do? The things that it needs to do are check if C0 is the starting one. We need to check that Cm is what is accepting, and 3, that Ci yields Ci plus 1 for all i. And it turns out that that's possible because if you think about it, I'm not going to do all the details, but the basic idea is to check that C0 is the starting one, you just need to see that, you need to look in this little block. right here. You don't need to acquire more cells or anything. To check if CM is the accepting one, you just need to look for an accept state over here and to check for whether each one yields the next one, you just will need to look and see if the transition was applied correctly and that's pretty easy. Sorry for interrupting, just to inform that the audio video is out of sync. Yeah. I am recording it, so hopefully it's not a big deal. Maybe we'll take a break. So let's take a break and then come back to this problem. So I'll see you all in a bit. Okay, hopefully things are in sync. Doesn't look like it. Yeah, maybe I won't do the post correspondence problem because I don't want this to be entirely out of sync. I'm just going to do a little bit. All right, so I'm just going to do the E sub LBA problem here. And And then do the... the EQCFG problem because that's the only one that's left. All right, so, yeah, so in fact an LBA can figure this out whether or not given a computation history like this whether or not it's a valid one. So the thing is what we have here is that Because M is a Turing machine, this thing that was given to us, it can only have one possible computation history that is accepting. It could have zero if M does not accept W, but it might have, it's either zero or one. So the language of this LBA that we make here is either going to be it has one string in it if m accepts w and it's going to be empty otherwise. All right and so therefore if we build this LBA given the machine m and w, the Turing machine m and the input w, then this LBA will have empty language if and only if m does not accept w. And so therefore that has a direct relation to the ATM problem. And so therefore we can actually show that if we can decide whether or not an LBA has empty language, then we can decide the ATM problem, which is not possible. All right. So now I want to do two more problems. which is one of them is going to be called the all-CFG problem, which we haven't seen, but it's actually kind of useful for showing the EQ problem for CFGs to be undecidable. So here we have that C is a CFG and the language of G is everything. So it's sigma star. And you may think, well that's kind of like the E CFG problem, but it's just now all strings instead of no strings. And unfortunately it's not quite the same, because this thing is undecidable. It's actually kind of shocking because the E's, the emptiness problem was decidable, whereas this one I claim is undecidable. So The reason is that we can use this computation history idea yet again. So the basic idea here is to check or sorry, I should say it this way, build a CFG that accepts. all strings that are not computation histories with CM accepting, like before. So if we have a CFG that accepts all strings that are not computation histories. So that means that there's ever only zero or one computation history given a Turing machine and input w that are accepting. So there's only either zero or one. So all strings that are not them is either this grammar is going to have either sigma star as its language or everything but one string. So it's kind of like the opposite idea that the ELBA is going to have a string that's proof had. It's just now we're working with all strings that are not them and not. But this idea as stated will not work. because if you think about it, what does a computation history look like? So let's draw a few configurations here. If you think about it, if we apply a transition from C0 to C1, then there's only a very small portion of it that's going to change. So this green part in the computations is the same in both of them, right? And because it's the same in both, then this is essentially the same or similar to the language W pound sign W, where W is in something. It doesn't matter what the strings are. And actually, I should say, I should say, let's say sigma star. And this guy is not a context-free language. And I'll let you actually prove that. So we can't actually use this because it's essentially the same thing. There's some things to fix here because it's not exactly identical. But it's very close to it. And so therefore, this would not... be possible to do all of these, let alone even a pair of them like this. What happened to the 2n-1 constraint of c and f from your previous string? Can we not check up to that and decide for all cfg? No, that's actually a really good question. I haven't even thought of that. So The reason why the 2n minus 1 trick won't work is, let's say that, so let's say that this is the 2n minus 1 mark right here, length. And let's say, for example, that all of these are accepted. So all are accepted. Then this implies. that we can pump these strings that are above the pumping length. Well I don't know where the pumping length is. So if the pumping length is less than this number right here, then then yeah it would work. But the problem is that what if the pumping length is over here? Then it might be possible for these strings to not be accepted. So possibly not accepted. And we don't know an advanced word that pumping length is going to be. So that's one issue. The other issue is even if you discard that entirely, then if you think about what pumping really does is you are only knowing that there is some decomposition where you can always stay in the language. So it might be the case that if we have a decomposition which allows us to stay in the language. then the things that when we pump more into the string, the length might jump considerably. So it might be that even if we discard all of this, then it might be that the next string that we can get is way longer than, say, 2n. It might be way longer than that. And then maybe some string will generate this one and then this one over here. And so we're not necessarily guaranteed, so we're not guaranteed here to be on to for the, when we pump the strings. We're not guaranteed to have an on to function here, which means that we hit all possible strings after this point. Yet, It is true that if you track all strings up to here, then you can certainly do that. It's just you're not guaranteed to do the ones afterward. You're guaranteed to, if you check strings of length 2 and minus 1, you'll check to, you'll know that that's the number of rules to apply, but it's not necessarily about which strings after this point are going to be accepted. It's a good question though. I might do a video on that. I never thought of it that way. That's good. Uh So I have my final on Wednesday. This channel is G-E-M. I thought that was short for something. Thank you for the hard work. Back to studying. Study hard. Watch all my videos. All right. So what do we do here? Well, what are we going to do? We're actually going to do something called, let me do this in pink. So we're going to use something called a reversed. computation history, which is quite a mouthful. But the idea here is that instead of doing this, we're actually going to reverse every other one here. Let's say the last one's reversed. So here it's more now like W pound sign W reverse and that is a context tree language because uh this is kind of like a palindrome with a pound sign in the middle. Actually it is a palindrome. So and from C1 to C2 it these two configurations are essentially the same but one of them is the reverse of the other one. There's a small difference but it's roughly the same. So the basic idea is we build a CFG that checks one that checks one of the following. So if any one of these conditions is true, then it's not a computation history. So if c0 is not the starting config, if it's not the starting one, then it's clearly not a computation history. And I can actually show that that's regular. I'll let you actually think about that. Similarly, if c sub m is not accepting, and it turns out that that one is also regular too, and then the third one is for some i, we have that if we look at c sub i, let's say it's forward and c i reverse. then more after. And then ci does not yield. Oh this would be plus one, sorry. ci plus one. So it doesn't yield it there. Alright so how do we actually do this? Well it's essentially W pound sign W reverse. So if there is some i that's like this, then it must be of the form gamma star then c i pound sign c i plus one reverse and then gamma star afterward. So I don't care what happens afterward. As long as this one does not yield this one, then we're all good. So how do we do this? Well, if we actually look at these two configurations side by side, let's say that C i starts with a b c then the pound signs in the middle then that means that C i plus one ends with C b a like this. So then what we know what we can figure out then is that wherever the stuff that changes is in a little window on both sides. So what we can say is that for the first part let's call it W then the second the part at the very end is going to be W reversed for sure. Not the part that is different, just the part that's outside of the little window. And actually the part in between, let's call it X, on the other side is going to be X reversed. And we know how to do this. So we know how to check for each of these individual segments because it's essentially W, W reverse and we know how to do that easily. It's just these parts right here that are that you have to check for but I claim that this part is easy to do because there are only finitely many transitions for Yeah, there are only finitely many transitions of the Turing machine So we're trying to solve the ATM problem again. So we're given a Turing machine. So these ones are for Turing machines, although it's not really that important. The important part is that we can actually check for all possible combinations that can appear here. And what we can do, what we want to have is that we want not that these two segments are the same, but they're different. So either one... the outside segments are different, the insides are different, or three, the transition was not applied correctly. And we just need to look at the transition function of the Turing machine, and there are only finitely many transitions that can occur. And so we just encode all of them into the context-free grammar. And since there's only finitely many, we can put finitely many things into a context-free grammar, and that's no issue whatsoever. And since it's OR for all of these, then as long as at least one of these occurs, then the grammar should accept that string. So therefore the only string that is not accepted is any accepting computation history. So the only possible string the CFG generates is some accepting computation history. And so, therefore, if I can check whether a grammar has every single string in its language or not, then I can check whether or not it accepts some computation history. So, if the language of the grammar really is sigma star, then you can... then M does not accept W because it can't possibly have an accepting computation because if it did, then this grammar would not accept it. And so therefore, because this language is sigma star. And then otherwise, if the language of the grammar is not sigma star, then M accepts W because the only possible string that it... this grammar does not make is some accepting computation history. And that's it. Pretty cool. And I know that this is a context-free grammar because we had unions of regular languages and context-free languages, only a finite number of them. And so therefore the entire thing really is a context-free grammar and that's in fact it. So This actually concludes everything I wanted to do, but let's do a final summary table of decidable and undecidable stuff. So we have DFA and NFA and regular expression being one row. We have CFGs and PDAs being another one. You can do deterministic context-free and that's actually a really interesting question, but I'm not going to do it here because it's actually very complicated. We had the LBA question and we have the Turing machine question. Let's see if all this fits. All right, so let's have some columns here. So we had the A acceptance problem. we had the emptiness problem, we had the equivalence problem, and the all problem. Actually I didn't do the equivalence problem for CFGs, but I can do this really quick. EQCFG is undecidable, and the reason for this is that I'm just going to sketch it right here really quick. Where we build a CFG that has sigma star, its language and then feed the input CFG and that one. to the decider for eq and that's all you need to do because if if then we can solve the all problem because if if the if the equivalence one says yeah they're the same then the original one had language being sigma star and if it said that they were different therefore the original one did not have sigma stars as language And so therefore we could solve the all problem, but we know the all problem is not possible. And so therefore the EQ problem is not possible either. All right. So what do we have here? So DFAs are checks on everything. I didn't do all DFA, but you can actually work with the EDFA one and you can show all DFA is decidable too. In fact. Virtually any problem that you come up with for DFAs is going to be decidable. CFGs and PDAs, we had checks on the first two and frowny faces on the last two. For LBAs, we had yes on the acceptance problem, but we have frowny faces on the emptiness problem. For the same reason... for Turing machines, we have EQ also being undecidable because we can just make a Turing an LBA that has empty language and feed the input one and the constructed one to the EQ machine. And so that therefore that would solve the emptiness question, but we know that's undecidable. So this one's also not possible. The all one is also not possible. for very similar reasons that the emptiness one is. And then for turning machines, it's frowny faces everywhere. So frowny face for you, frowny face for you, frowny face for you, frowny face for you. All right, so the interesting question, and this is like the subject of research level stuff, is what about deterministic context-free languages? So if it happened to be like all checks on both of them, on CFGs and PDAs and DFAs, then the DPDA1 would be all checks here. So is it that they're all checks for DPDAs? Because we show that they're not the same thing as PDAs, not equivalent in power. So maybe we do recover the equivalence in the all problem. We definitely get the acceptance and the... emptiness one for DPDAs. That's pretty clear because it's checks for both, but it's just for these last two. It actually gets quite interesting. So that's all I wanted to do for today. So congrats, you made it to the end. That was the entire theory course in four videos. Thank you all for sticking around and supporting the channel. I am gonna go lie down pretty soon. No. It was fun doing this. It was a lot of work and the stream is... I need to fix the stream. I know it's a terrible quality sometimes. I need to fix that but hopefully you learned something. Make sure to subscribe to the channel if you haven't yet. There are many other links in the video description if you want to support the channel further. I'm currently doing one-on-one tutoring sessions. If you want to take part in that my email is in the video description. And as always, thank you for watching and I'll see you next time.

We didn't, we don't know whether or not, we can test whether two CFGs have the same language or not. Yeah, so I'm getting quite a lot of dropped frames now, which is kind of crummy. So what we're going to do today is we're going to answer these four and more.

So what we're going to do is we're going to tackle this one. then emptiness for Turing machines, and then equality for Turing machines, and then equality for CFGs. It seems weird that we do it in that order, but there's actually a very good reason for doing that, because some technology that we need to use for this problem will need after we do these three. So the first one I want to do is to talk about the ATM problem, which is very similar to the ADFA and ACFG problems, where instead we have a Turing machine as being the first parameter of the input pair.

And of course, W is in the language of M. So this is exactly the same thing as ADFA, except now we have a Turing machine instead of a DFA. And what I claim... that this problem is undecidable. So there is no algorithm to to decide this.

But we know we can actually show that this is recognizable. And how do I show that it's recognizable? Well that means that if we have a pair M's and W's If it really is in ATM, then I need to accept. That's what it means to be a recognizer.

You accept on the strings in the language and you don't care about the other ones. So to get a recognizer, what we do is we say on input MW, where M is a Turing machine and W a string. and I don't care about what the encoding is as long as it's some encoding that we can understand.

So the first step is just to run that Turing machine on the input string. Now this step might take forever, but that's okay in this case because we're only making a recognizer. And then we will accept if m accepts w.

So if the machine said, yeah, I accept that thing, then we're just going to say yes. So effectively, we're just doing what the original machine would have done. It's okay here that this step might run forever because Turing machines could run forever because we're only concerned about making a recognizer. If the machine runs for forever, then it's never going to accept anyway. And so that's not a big deal.

The problem for showing decidability is... if the machine happened to run forever, we need to say reject. We need to actually say reject ourselves.

Okay. So how do I actually show undecidability here? So how do I show undecidability? We're actually going to use a proof by contradiction, and this is the standard proof.

And the contradiction proof basically goes, if it was decidable, then we can get some kind of contradiction as a result. So what we're going to do first is we're going to suppose that ATM, which will show to be undecidable, was decidable. Suppose it was decidable.

God, I can't write decidable. And let's let... uh, each decided. Okay, so H is just some machine we're supposing exists, and it solves the ATM problem. And what we'll basically show is that either H has a contradiction or it can't exist, or both.

So what it does is, if we give H some input MW, it either says accept or it says reject. Because... It's a decider. It must always halt because that's what it means to be a decider.

So it says except if M accepts W and rejects otherwise, which means that it either outright rejects W or it runs forever. One of those two. And it doesn't matter which.

So H must say reject regardless of whether it runs forever. or it outright rejects the thing. Okay, so what do we actually, how do we actually use that?

Well, what I'm going to do is I'm going to, the step I'm going to do here is I'm going to build a contradictory, contradictory machine that only exists. if H does. So the only way that this machine that I'm going to make next can exist is if this H exists.

And H is the decider for ATM. So this machine that I have to build has to be contradictory in some way. And it can only exist if that machine H does.

And if... because this machine is contradictory it therefore can't exist and then therefore H can't exist and so therefore ATM is undecidable. So how do we actually use that here? So here's the machine I'm going to build.

I'm going to call it D for no reason. So D is going to take some input M which is all that it's going to take is where M here a Turing machine. So it has no input string, it's just the machine itself, nothing else.

And the first step it's going to do is going to run that decider H on this. So I provided a Turing machine to H, but H also needs the input string after it. So then what's the input string? Well I'm going to feed the string the encoded string of the machine.

So this thing is the input string to m. So that's just the input string. And the second step is output the opposite of what h does. So whatever h says here.

it must say accept or reject whichever one of the two it is, we do the exact opposite. Okay, so this machine seems totally logical in what it actually does because it just runs a machine and it outputs something. And we've we've outputted the opposite before so that's not inherently an issue. So what we can actually see here based on these two steps right here is that d is a decider too, okay? Because all of its steps run in a finite amount of time.

Clearly, the first one does because H is a decider by assumption. And the second one, clearly, it runs in a finite amount of time. So D is a decider for whatever language it is.

So therefore, it must say accept or reject correct. on all strings that it gets. So no matter what Turing machine this thing gets, it's going to say the right answer. It is going to say accept or it's going to say reject. So like we did with the H machine, let's actually understand D's behavior.

So it's going to get a single machine M and because it's a decider, it must say accept or it must say reject, one of the two. it'll say except if So the behavior of this machine is if, I'm sorry, not m. So if that Turing machine that it got rejects, or actually I should say, yeah, I should say does not accept its own encoded string.

Because the d machine. says output the opposite. So if D said accept in this step then that means that H said reject in the first step because it does the opposite. So that means that M does not accept its own string as input which is fine that's possible and it says reject if M accepts its own encoded string. Because again, the D machine does the exact opposite of what the H machine said.

So D is kind of doing the opposite of what the H one said. So this seems totally logical because M may or may not accept its own string, right? And so therefore, we just do the opposite.

There seems to be no contradiction here. So the key to understand this is that the D machine must say the right answer on every Turing machine. every single one, including itself. So what happens if we feed D's own string as input to itself? So D on its own input string, well, it's kind of like this one up here, except I'm going to substitute D for the M up here.

So it says, except if D... because there was an m here, I'm going to put d here. If d does not accept d, wait a second, so it says d accepts its own input string.

If d does not accept its own input string, that seems kind of contradictory. Well, let's try the other one. Well, it says reject if d accepts. its own description. Wait, so wait, it said D rejects its own input string, its own string, if D accepts its own input string.

Wait, so that means that D on this input cannot have said the right answer, because it's a contradiction no matter which is the case. Ah, so therefore, D is contradictory, is not a decider. So D not decider and actually can't exist because it doesn't report any answer here and and so therefore it cannot possibly exist which means that the H machine up here could not exist because the only way we were able to build the D machine is if we made the H machine and that since we can't make the D machine that means we can't make the H machine and so therefore ATM is undecidable. All right, so this implies that ATM is undecidable. All right, so that's a little bit complicated.

I completely understand. So if that was complicated to you, watch the stream again. Maybe I'll upload this because I'm recording it now.

Hopefully the recording works. Hopefully, let's see if it's working. Yeah, it looks like it's working. Yeah, this proof is using diagonalization, exactly. It's a diagonalization type proof.

Good. All right, so let's see what's the next one. All right, so one other thing I want to prove which is kind of related and we'll kind of use it here. that I'm gonna have a theorem here which is that L is decidable if and only if L is recognizable and L bar is complement is also recognizable which seems kind of shocking because recognizability You only have to accept the strings in your language, whereas decidability you have to halt on every single string, whereas if you just had a recognizer, you don't have to halt on the strings, not in the language.

So it seems kind of shocking that if you have a recognizer for a language and its complement, you can get a decider out of it. So it turns out that the forward direction is easy, because if the language is recognizable, it already is recon... Sorry, if it's decidable, it automatically is recognizable because of the definition.

and decidable languages are closed under complement. So if L is decidable, then its complement is 2. And so if L bar is decidable, then L bar is recognizable too. And so that's pretty straightforward. So for the other direction, so let's suppose that A recognizes L and B recognizes is a machine for L bar. So A is for the first for L and B recognizes the other one.

Though these two machines do not have to halt on the strings not in their language. They're not required to. They just have to halt on the strings that are in their language.

Okay the key is to note that yeah I'll actually write it down here. So the key to note here is that every string is either in L or as complement. Every single string.

And so that means that one of the two machines must stop on every single, for any string that you pick, one of the two machines must stop, or both, but at least one of the two must stop. So I'm just going to give a sketch here. it's actually not more than this, but I want you to actually think about how this works, which is to simulate A and B, the two machines, for one step each and then check, actually I should say it this way just to be a little simpler, so if A accepts at this point, So if A accepts, then we are going to accept. The reason for that is if A says yes, it's in my language, the string that you gave me, then it's in L, which is the language I'm trying to decide at this point. And so we should say accept it is in there.

Otherwise, if B accepts at this point, then we're actually going to reject. And the reason for that is if... the string that we gave us had b said yes it is in my language then it must be in l bar and we're trying to decide the original language l. So if it's in the complement of l it is not in l and so therefore we need to say no we're not in l at this point. And we know that yeah so one of these two will always be encountered by definition, by the supposition that A recognizes this language and B recognizes the complement of it.

And so therefore, one of these two steps must occur because we're always simulating for one step each. I can't just simulate on A and then simulate on B because A might run forever. And so by doing this one lock step each, You could do for two steps.

There's nothing special about one step, but it's just that it's a finite amount of work for each of the two machines at each point. And so there's no possibility of one machine running forever before you try to do the other one. So this is how you would actually solve this. Alright, so this machine, because each one of these two steps must have encountered at some point, then that means that we will, therefore we will accept or reject in a finite amount of time, and so therefore we have a decider because that's all it needs to be. And we are accepting the right strings and rejecting the right strings because of how a and b were created earlier.

A was for l, b was for l bar. All right, so the consequence of this is that atm Bar. not recognizable and the reason for this is if it was then ATM ATM would be decidable because we saw before that ATM was recognizable and so if ATM bar was also recognizable then ATM would be decidable by the result we just did.

And so therefore it's not recognizable. All right, so the picture that we have right now is actually a little bit more interesting. So we had regular down here, then CFLs, then we had decidable out here, then we saw that in fact recognizable languages are a bigger bubble. And then we have some languages that are outside the recognizable bubble. So like ATM bar was out here.

Recognizable but not decidable is in here. So normal ATM is in there. And then we have all of the usual ones down here.

All right. So that's all I wanted to show for ATM. Let's move on to the ETM. In fact, let's update our little table up here. So we now know that ATM is undecidable, so it's not decidable here.

Let's figure out ETM, the emptiness problem. So ETM, which is just like all of the emptiness problems before, so M is a Turing machine, except now we have Turing machines obviously, and the language of M is empty. And I want to show you that this is not, I should actually say undecidable, is undecidable.

Alright so how do we actually show this? Well the good thing that we're going to do here is we're going to use another proof by contradiction but not nearly as complicated as the ATM one. So we're going to suppose that ETM were decidable.

Then what are we going to do here? We're going to, we will show then that ATM is in fact decidable based on entirely on that supposition. So based on this supposition alone, we're going to show that ATM is decidable.

And we know that this thing is false, and so therefore this can't be true, and so therefore ATM is undecidable. So how do we actually do this? So we're actually going to try to decide ATM at this point. So the ATM problem had M and W where M is a Turing machine, and W is a string. So let's say that ETM were, I should actually write it as, were decided by, let's call the machine E.

So let's say that E here is the hypothetical machine that solves the ETM problem. Then how do we use it here? Well, I can't just feed this M into that Turing machine E right here, because if E says its language is empty, then I immediately know it doesn't accept the input string W here, which is fine.

But what if E says no, its language is not empty here? So if E says no, M's language is not empty, that doesn't tell me anything about whether M accepts. this string w.

I know it accepts some string. I don't know if it's this one. So what we are going to actually need to do is to make a machine that has the right behavior.

So how do we actually do that? So we're going to construct a Turing machine. I'm going to call it m prime. And the way it's going to work. is I'm going to have it take some input, different input x.

So this case, x can be any string at all. It does not matter what it is. Okay so let's see. So the behavior I'm gonna have this be is I'm gonna have it have M prime be the empty language if and only if M accepts W.

And so how am I going to do that? So step A in here. I'm going to say if X right here the input string to M prime not W, so if it's not the the input string way above here, then I'm going to reject immediately.

So the reject in here is for the M prime machine, not the outside machine here. So then here if X really is W, then run the original Turing machine upstairs. the original input w and accept if m does.

Okay and that's it. So the behavior of this machine is it's either so the only possible string it could ever accept is when it's equal to w. That's the only possibility and so The language of M'is either the empty set if it does not accept W, if it doesn't accept at this point down here, or it's just the single string W and nothing else.

It's not important that it's a single string here for this language as long as it's empty in one case and not empty in the other case. And what we're going to do then is we're going to run the decider for ETM on this M prime thing that we got. So M prime.

Okay. So let's see. So now let's figure out what we need to do here.

So if E accepts. So then if E accepts. then that means that M prime's language is empty by definition.

So that means if it accepts, we will look at what happened here. So that means that it was empty. How did M prime's language be empty? The only possibility is that M did not accept W because if it did, then M prime's language would not be empty.

So this statement right here implies that M that m did not accept w before. And so because we're trying to solve the acceptance problem, we need to reject here. Basically do the opposite because we set it up so that the language would be empty exactly when m does not accept w and non-empty if m does accept w. And so otherwise we're going to accept.

Okay so we'll accept there because in the otherwise case it M prime's language is not empty which means that M had to accept a W here. And it's clear that this runs in a finite amount of time or maybe not so obvious. So the important thing is that this step right here is purely construction. of a machine.

So I'm not actually running M prime. I'm just making the machine and that takes a finite amount of time because I just have to embed the transitions of M into this this M prime machine. And that's pretty easy to do.

So this takes a finite amount of time. E takes a finite amount of time by supposition. And clearly the last step runs in a finite amount of time too. And so therefore, this whole machine runs in a finite amount of time and solves the ATM problem, which we know to be undecidable.

And so this is a contradiction. So this is a contradiction since ATM is undecidable. And we can finally conclude that ATM.

is undecidable. Because if it were decidable, then ATM would be decidable, and we know it isn't. All right, so that's pretty good.

So we can finally go check off that, or cross out that one area right here for E sub tm. What about the equivalence problem? You're going to probably guess it's very similar, and in fact we'll show that to be the case. So let's do eqtm, which is all pairs of machines.

So m1, m2 are Turing machines. And L of m1 equals L of m2. And you wouldn't be surprised to say that this is undecidable. Okay, so how am I going to actually use this here?

So many frames dropped. So what are we going to do here? What we're going to do is we're going to do another proof by contradiction. So this is a proof by contradiction.

So let's suppose that again E decides EQTM. And what we're going to do is we're now going to solve the ETM problem. There is a way to do it with the ATM problem. It doesn't have to be with ETM, but it turns out that solving ETM in this case is way easier.

So we're going to try to solve the ETM problem. So remember the ETM problem has a single Turing machine as input, where M is a Turing machine. So we don't have, so EQTM, so this machine E right here expects two Turing machines, whereas the ETM problem, we're only given one. So if I'm going to use this supposed decider right here, I need to manufacture or...

new Turing machine. So what I'm gonna do here is I'm going to make a Turing machine, I'm gonna call it M sub-empty, which has empty language. Okay, so it accepts absolutely nothing and that's very easy to do.

And what I'm gonna do I'm going to run that supposed decider E again on the two Turing machines I have, M and M sub empty. So M is the machine I was given, M sub empty is the one I manufactured, and what we're going to do is I claim that we just need to figure out whether to accept or reject here. So if E accepts because it's a supposed decider, then that means that these two machines have the exact same language by definition, because that's what E says. E tells us whether or not the two languages are the same. So if it says yes, then these two are the same, which means that M had empty language, which means that to solve the ETM problem, we need to say except here.

So we need to say except. and then otherwise we will actually reject. And the reason for that is if these two are not the same language then M cannot possibly have empty language. And so therefore solving the ETM problem, if it has not empty language then we need to reject. And clearly all three of these steps run in a finite amount of time because the first one you just make the machine.

and it's a small machine, so it's no big deal. The second one takes a finite amount of time by assumption, and so the third one takes a finite amount of time, and so this is therefore a contradiction since the ETM problem is undecidable. And so therefore, we can conclude that EQTM is undecidable. So in some sense, EQTM is harder to solve than the ETM problem. Because if you happen to solve a particular choice of two machines, so this one always has empty language, then we can solve all of the ETM problem.

So EQTM in some sense is actually pretty hard. And one thing that you could prove is that EQTM is formally harder of a problem. problem to solve than the ETM problem.

So if you do this kind of proof by contradiction thing, for the thing that you're trying to solve, then the thing you're trying to solve is actually going to be quote-unquote a harder problem than the one that you're that you supposedly solve like ETM here or ATM that we did before. Alright so that's that. All right, so I'm going to take a break for a bit because the next one is going to actually take quite a, it's quite a doozy.

So I'm going to take a short break and then we will be back with more of undecidability stuff. So I'll see you then. I actually forgot to hit the transition button. All right. So what I'm going to do here is I'm going to prove a whole bunch of things to be undecidable.

So what I'm going to be proving here is something called Rice's Theorem. And it's a general tool. to show languages undecidable really easily. Much easier than doing the proof by contradiction stuff that we did before. Alright, so how is this going to work?

So the setup is, we're going to talk about non... trivial properties of Turing machine languages. And it's actually pretty simple.

So this part right here, ignore non-trivial for a sec. So this is a language which has Turing machine descriptions and nothing else in it. So M is a Turing machine.

blah blah blah so something like that so what do we actually have here so in this language right here either oh sorry I didn't say that right so if we have two machines M1 and M2 exist such that the language of M1 is equal to the language of M2, then both or neither of them are in this language. I know that's quite a bit of a mouthful, but the basic idea here is that the only criterion to be in this language right here is what your language is. So if we had two machines that had the exact same language, then the only criterion supposedly for this blue one right here is your language, which means that it's not possible for say M1 to be inside here and M2 to not be inside here.

Okay. So it's either they're both in there or both not in there. Okay. So if I had a... thing in here that said if the machine has at least seven states, then this condition down here is not satisfying necessarily.

But if it was like say ETM for example, then the only criterion to be in there is if you have empty language. If you have this exact same language, then either you're both empty or both not empty. Okay.

And so therefore that would be a property of Turing machine languages. Alright, and then what about the non-trivial thing over here? So this says that the language that thing has, I should say it this way, includes at least one Turing machine.

and excludes at least one Turing machine. Okay. I could say that more formally, but that's the basic idea. It has something in there.

So there is a Turing machine in there. And it excludes some Turing machine. So it's not the case that every single machine is in here. So if I just said M is a Turing machine and that's it, that is not.

non-trivial. And in fact, if you don't have non-trivial here, then you have a decidable language because either you have every Turing machine in there or no Turing machines in there. And you can show that that's decidable. But what Rice's theorem says is this. It says that every non-trivial property...

of Turing machine languages is undecidable. Every single one. So for free, we get that ETM is undecidable. We get that testing whether a Turing machine has regular language or not, that's undecidable. Testing if it accepts sigma star, that's undecidable.

All of them are undecidable, 100%. So how do you actually try to prove this? So it's actually... very very similar to what we did before but just more general.

So let's see, so how do we actually show this? Yes I do. I'm pretty sure I'm, oh okay I did have it, it just was hidden. All right so the thing is that The only thing that we know here is if we have some non-trivial property.

I don't know anything about it. About what Turing machines it has, which ones it excludes, I do not know. So let's just let p be a non-trivial property.

No, not no trivial property, non-trivial. Need to learn to spell. Property.

All right, so what do we actually know here? Well, the way that we're going to work with this is we're going to, without loss of generality, assume Turing machines with language being the empty set are not in P. Okay.

And why can we assume this without loss of generality? The reason is, if not, if that's not the case, interchange P with its complement. Because if you have a undecidable language, which is what P we will show to be, those are closed in a complement. So I can just switch it with. the complement and that's also a non-trivial property you can also show.

In some sense, not entirely accurate, but it's close. All right, so let's just assume that p were decidable. So again, we're going to do a proof by contradiction.

So suppose p were decidable. And let's say that, and let, I'm going to call it T be its decider. Let it be the machine that answers the right answers. Answers the right answers.

All right. T says I'm going to be given a Turing machine and I'm going to say whether or not is in this P set right here. And we will show that T cannot possibly exist. How? By showing that if T is a decider, then I can make a decider for ATM.

And we know that that's not possible. So to solve ATM, so remember the ATM problem gets... a machine and input.

So I'm going to write where m is a Turing machine and w a string. So what are we going to do here? So just like before, we're going to make a totally brand new machine that has some behavior.

So we're going to construct a Turing machine I'm going to call m prime, which is going to be input X just like before. No difference there. So what I'm gonna do here, which is kind of weird, which is simulate M on W.

So this, I'll draw some arrows, so this M is the one right here, and the W is this one right here. So these are not the T machine for the property. These are the original machines, which is kind of weird in that...

you're doing it inside this other machine, but the thing is I can construct this. I'm not running the M prime machine and so I don't have the issue of this being this could run forever. So what I'm going to do here is kind of weird, which is if M just outright rejects W, then we in the M prime machine are going to reject here. But otherwise, we're going to do some other stuff.

We're going to run T on X. So from what we've done before, the T machine is for the property P, and the X is the input to the M prime machine. I know there's a lot of machines here. But I'll get you through it.

So run T on X and accept if T does. And that's it. So what is the behavior of this thing? So let's actually go through it.

So if M accepts W, then that implies that... we will skip the B step right here and we'll proceed immediately to the C step, which means that we will run T on X where X is some arbitrary input. So the behavior of what M prime does is identical to what T does. So that means that the language of M prime is in fact going to be the language of T, which is the property P right here. Is that right?

Yeah, I think that's right. Oh, no, no, no, sorry, sorry, not P. It's the language of T. So M prime is going to have the exact same language as the T one. That's what I meant to say.

And then if M does not accept W. then that means that we're going to be stuck in this b step right here no matter what. And so we're going to outright reject the x string no matter what.

And so the M prime machine then is going to have empty language because we're going to get stuck in this b step and never accept anything. And so because we reject everything its language is empty. So the language of M prime is Empty. Oh, I screwed it.

I screwed something up Not let T be its decider. That's not what I meant to say. I meant to say that T Be in the property.

That's what I meant to say is using the non-trivial thing Yeah, so because I assume that the language though The Turing machines with empty language are not in the property. I have that there must be some machine with the property that's in the set P. And I'm just letting T be one of those things. And so the behavior here is that M prime is going to be either a machine that has the property or one that doesn't by definition. And so.

the differentiator of that is whether m accepts w. So all that we need to do now is run the decider for property p on that m prime machine that we just made and output the same answer. And you can check that this is the right thing to do. Okay.

And that's it. So This shows that P is undecidable, this property. And it was just some arbitrary non-trivial property, and then therefore the language is undecidable. Because this is, in fact, a decider for ATM, and we know that one cannot possibly exist. So an example of this.

Let's do a quick example. one that I've used on the channel before. It's one of my older videos. So here 3TM is all the Turing machines with exactly three strings in its language.

Okay, so it's all the machines that accept exactly three strings. And I claim that this thing is undecidable. All right, so how do you actually do that? Well, what we're going to use is Rice's theorem. So, we're going to use Rice's theorem.

So the proof of Rice's theorem is actually quite complicated, but using Rice's theorem is significantly easier. Oh, I haven't paid any attention to chat, sorry. I'm not going to talk about p versus np.

I will when I start. Complexity Theory next semester, or I hope to start it next semester. Murphy says love your streams.

Aw, thanks I don't know. Why would anyone do so much just for five people regularly? Yeah Although some videos on my channel get quite a ton of views like the academic integrity one I just did it got like 20 times the number of views I normally get so maybe I just have to Put things in my title like don't be stupid or something I'm not gonna actually do that, but it's it's just funny. But yeah, I'm happy for all your support, by the way.

All right, so let's use Rice's theorem here. So Rice's theorem says, well, we need to show that this is a non-trivial property of Turing machine languages. So the first step is to show it's a property Ignore non-trivial for a sec. So it's a property of Turing machine languages All right, so how do we actually show this?

Well, we need to have two Turing machines. So let's let M1, M2 be Turing machines with identical language. So M1, language of M2, they're the same. So what do we actually do with this?

Well, notice that the only criteria to be in the language here is whether you are... whether or not you have exactly three strings. If you have two machines that have the exact same language, then either of them, then they either both have three strings or both don't.

And so therefore we get this. So either both languages here have equal to three strings or both don't. which is all that you actually need here, because they're the exact same language, which is key.

And then the second one is to show non-trivial. So then I just need to give an example of a machine that has exactly three strings in it, and one that has a different number than three strings. So we could just have a example of a machine A. with the language trying to again getting notifications. So let's let the language of a for example be 0 1 2 and that has exactly three strings.

That's easy to make because you can make a dfa for it and so therefore you can make a Turing machine for it and so this implies that a is in 3tm and let's let a machine B have its language being the empty set. You can pick anything else other than that. It doesn't have to be empty set here, but it's just a quick and dirty example. So we have that B is not in 3TM. And therefore, we have an example of a machine that is in there and one that isn't in there.

And that shows that it's non-trivial. So by Rice's theorem, 3TM is undecidable. Okay, pretty cool.

So that was using Rice's theorem and... showing that a whole lot of languages are undecidable. So it doesn't work all the time.

So you can't use this for every single problem. So like EQTM, this will not work because it's not a property of Turing machine languages because it has pairs of Turing machines, not a single Turing machine. But anything that involves just a single Turing machine and something to do with this language, then those are undecidable.

So like another example would be regular TM, which is the language of all Turing machines. So M is a Turing machine. And its language is regular.

So this is purely application-based. Like if I wanted to know whether my computer program can be just easily done on a DFA, that is impossible to do, to do algorithmically for all possible Turing machines. That's impossible to do.

If you substitute this for context-free, it's the same story. Checking even if it's sigma star, that's already undecidable. So... quite a lot here that you can do. You can't prove everything undecidable this way.

So you can't prove like emptiness of some other model for example because it has to be Turing machine and you can't have anything other than single Turing machine descriptions or encodings with anything other than their language being the important part. So if you rely on the number of states for example of the machine or something like that, then that is, you can't apply Rice's theorem for those things. Okay, so let's move on to another type of model. So it's something that I'm going to call, yeah, I'm going to call it a linear bounded automaton. as an LBA here, is exactly a normal terrain machine except, oops, I can't spell for anything, except, except all, oops, sorry, except only the cells where the input uh is or was can be accessed so you can't access anything other than where the input originally was so in some sense uh what we have is a finite length tape now so instead of a one-way infinite where you can just acquire more cells if you wanted to we have the input being presented here like this, and there are no other cells available.

So to aid us a little bit, although it's not really that important, we're going to adorn this with a marker at the beginning and the end to signify where the input begins and ends, because I can't like shift the input over one position or anything because I'm fixed to where the input is. The key is that the size of the tape that's allowed is bigger when the input is bigger. Okay so the tape is adjustable to the input size whatever that is. So it's unbounded in the sense that the input size can be unbounded but I can't acquire more cells later on.

Rice's theorem for non recursively innumerable languages. So that's called the strong rice's theorem. I made a video about it I'm not going to cover it here. Yeah, most feared concept after pumping lemma. Yeah, it's it is for most people So if it's a simulation of a PDA Using Turing machine and finding out whether a string it accepts or not even that's undecidable.

No So if you're simulating another machine like a PDA, you can always simulate a PDA. In fact, we showed that A sub CFG was decidable. And so A sub PDA is also decidable.

So it's taking a Turing machine as input and deciding or not whether or not it has a context-free language. That's a different question. Here, if you're trying to simulate a fixed PDA, so if you know the PDA in advance and you're trying to simulate it, that is decidable.

So here is really a question of whether the input is fixed or whether it... is an arbitrary input and there's a different answer for both. Yeah I see my stream is freezing. I am recording this so I will upload this at some later point. All right so what I want to show is that the a sub LBA problem so like a sub Turing machine but now for LBAs.

MW. So M is an LBA and W is in the language of that machine. I want to show, I did this on the channel way back, but I want to do it again.

This is decidable. So this thing actually is decidable. So this actually immediately tells us that LBAs are different.

than Turing machines because if they were the same then the ATM problem would be the same answer as what the ALBA problem is but they're different. It's because this one's decidable and I'm not going to do the whole proof here. Watch the video on my channel if you want to see the full proof but the basic idea here is that if the input has a length n for example, then the number of possible tape configs configurations is finite because the tape length is fixed here.

And the reason for that is, let's actually draw it out. So if I have my tape And let's say that this thing has n cells. And let's say, for example, there are, I don't know what's going on. So let's say that in each cell there are g possible symbols. I should say tape symbols.

And could be, let's just say in the state that we're in, one. the set of q states and let's call that little q here. So let's say that there are little q states, there are g possible things I can put into each cell, and there are n cells.

So the tape head could be at any one of those n cells. I should write this here. So the total number of possible configs. is going to be equal to the number of tape positions there are, so n, times the total number of possible tape contents, which is g to the n, because I can have g in any one of the n cells.

I can have any number of them. And I can be in any one of the q states independently of all that. So that's the total number of possible um configurations.

So the idea here is to simulate the LBA for that many plus one transitions. The plus one actually is important here because if you simulate the LBA for that long then that means that you must have repeated a configuration at some point. So if you repeat a configuration at some point, because the machine is deterministic, you're going to repeat it again.

You don't know which one is going to be repeated, but you know that one actually is repeated. So the machine that actually simulates this thing just calculates this number plus one and will simulate the LBA for that many transitions. And that's it.

If the LBA accepts before then, you accept. If it rejects outright, you reject outright. But if it has not stopped by this point right here, then that means the LBA will never stop because it's not required to stop. And so we can just outright reject because we know the LBA is going to run forever anyway. And so here we can actually guarantee that we will.

we can check whether or not the LBA will run forever as a result. And therefore, it's decidable because this number is a finite number of transitions. And so therefore, we can easily do that. All right. So, but in contrast, what I want to do is I want to do the emptiness problem for LBAs.

So just to refresh your memory, we have a single LBA here, or a single one given as input, I should say. M is an LBA, and its language is empty. And what I want to show here, that this is undecidable. So it's more than context-free languages. because there we got the A and the E problem both being Decidable and it's not quite to Turing machines because the A problem is Decidable for LBAs.

So it's somewhere in between and It turns out that LBAs are equal to the context free language context sensitive language I'm not going to actually prove that here and I'm not going to go into context sensitive grammars and whatnot. But if you happen to know what those are, then they're equivalent to that. All right.

So how do we actually show that this is the case? It's actually kind of complicated, but once you see it, it's actually pretty, it's like, ah, that makes sense. So what I'm going to call a computation.

history is a string pound sign c0 pound sign c1 pound sign dot dot dot pound sign cm where we have that c0 is the starting config and we have I'll do it this way We have that each one is going to yield the next one in the in the chain Okay, so each one is going to yield the next one and remember that yield just means apply a transition All right. So how do we actually do this? So What we're gonna do is Again a proof by contradiction. I can't use Rice's theorem here because this is not Turing machines This is an LBA.

So I got to do something different So again, we're going to suppose it were decidable. And what we'll do is we'll try to solve ATM, just like before, just like the other ones. And if we do, in fact, solve ATM, then this shows that E sub LBA is undecidable. So the question here.

I'm not going to write the whole thing, but remember what a supposed solver for ATM says. It says on input M and W blah blah blah. Then what we want to do is in here can an LBA figure out if any computation history that has the last one being accepting exists.

So can we have an LBA figure out whether or not this is even possible? So if the LBA is given some potential example strength. like this, can it actually check whether or not this really is an accepting computation history? So it turns out that yes, the answer is yes to this.

And so what do we actually need to do? The things that it needs to do are check if C0 is the starting one. We need to check that Cm is what is accepting, and 3, that Ci yields Ci plus 1 for all i. And it turns out that that's possible because if you think about it, I'm not going to do all the details, but the basic idea is to check that C0 is the starting one, you just need to see that, you need to look in this little block.

right here. You don't need to acquire more cells or anything. To check if CM is the accepting one, you just need to look for an accept state over here and to check for whether each one yields the next one, you just will need to look and see if the transition was applied correctly and that's pretty easy.

Sorry for interrupting, just to inform that the audio video is out of sync. Yeah. I am recording it, so hopefully it's not a big deal. Maybe we'll take a break. So let's take a break and then come back to this problem.

So I'll see you all in a bit. Okay, hopefully things are in sync. Doesn't look like it.

Yeah, maybe I won't do the post correspondence problem because I don't want this to be entirely out of sync. I'm just going to do a little bit. All right, so I'm just going to do the E sub LBA problem here.

And And then do the... the EQCFG problem because that's the only one that's left. All right, so, yeah, so in fact an LBA can figure this out whether or not given a computation history like this whether or not it's a valid one. So the thing is what we have here is that Because M is a Turing machine, this thing that was given to us, it can only have one possible computation history that is accepting. It could have zero if M does not accept W, but it might have, it's either zero or one.

So the language of this LBA that we make here is either going to be it has one string in it if m accepts w and it's going to be empty otherwise. All right and so therefore if we build this LBA given the machine m and w, the Turing machine m and the input w, then this LBA will have empty language if and only if m does not accept w. And so therefore that has a direct relation to the ATM problem.

And so therefore we can actually show that if we can decide whether or not an LBA has empty language, then we can decide the ATM problem, which is not possible. All right. So now I want to do two more problems.

which is one of them is going to be called the all-CFG problem, which we haven't seen, but it's actually kind of useful for showing the EQ problem for CFGs to be undecidable. So here we have that C is a CFG and the language of G is everything. So it's sigma star.

And you may think, well that's kind of like the E CFG problem, but it's just now all strings instead of no strings. And unfortunately it's not quite the same, because this thing is undecidable. It's actually kind of shocking because the E's, the emptiness problem was decidable, whereas this one I claim is undecidable.

So The reason is that we can use this computation history idea yet again. So the basic idea here is to check or sorry, I should say it this way, build a CFG that accepts. all strings that are not computation histories with CM accepting, like before.

So if we have a CFG that accepts all strings that are not computation histories. So that means that there's ever only zero or one computation history given a Turing machine and input w that are accepting. So there's only either zero or one.

So all strings that are not them is either this grammar is going to have either sigma star as its language or everything but one string. So it's kind of like the opposite idea that the ELBA is going to have a string that's proof had. It's just now we're working with all strings that are not them and not. But this idea as stated will not work.

because if you think about it, what does a computation history look like? So let's draw a few configurations here. If you think about it, if we apply a transition from C0 to C1, then there's only a very small portion of it that's going to change.

So this green part in the computations is the same in both of them, right? And because it's the same in both, then this is essentially the same or similar to the language W pound sign W, where W is in something. It doesn't matter what the strings are.

And actually, I should say, I should say, let's say sigma star. And this guy is not a context-free language. And I'll let you actually prove that.

So we can't actually use this because it's essentially the same thing. There's some things to fix here because it's not exactly identical. But it's very close to it. And so therefore, this would not... be possible to do all of these, let alone even a pair of them like this.

What happened to the 2n-1 constraint of c and f from your previous string? Can we not check up to that and decide for all cfg? No, that's actually a really good question.

I haven't even thought of that. So The reason why the 2n minus 1 trick won't work is, let's say that, so let's say that this is the 2n minus 1 mark right here, length. And let's say, for example, that all of these are accepted. So all are accepted.

Then this implies. that we can pump these strings that are above the pumping length. Well I don't know where the pumping length is. So if the pumping length is less than this number right here, then then yeah it would work. But the problem is that what if the pumping length is over here?

Then it might be possible for these strings to not be accepted. So possibly not accepted. And we don't know an advanced word that pumping length is going to be.

So that's one issue. The other issue is even if you discard that entirely, then if you think about what pumping really does is you are only knowing that there is some decomposition where you can always stay in the language. So it might be the case that if we have a decomposition which allows us to stay in the language. then the things that when we pump more into the string, the length might jump considerably.

So it might be that even if we discard all of this, then it might be that the next string that we can get is way longer than, say, 2n. It might be way longer than that. And then maybe some string will generate this one and then this one over here.

And so we're not necessarily guaranteed, so we're not guaranteed here to be on to for the, when we pump the strings. We're not guaranteed to have an on to function here, which means that we hit all possible strings after this point. Yet, It is true that if you track all strings up to here, then you can certainly do that.

It's just you're not guaranteed to do the ones afterward. You're guaranteed to, if you check strings of length 2 and minus 1, you'll check to, you'll know that that's the number of rules to apply, but it's not necessarily about which strings after this point are going to be accepted. It's a good question though.

I might do a video on that. I never thought of it that way. That's good.

Uh So I have my final on Wednesday. This channel is G-E-M. I thought that was short for something. Thank you for the hard work. Back to studying.

Study hard. Watch all my videos. All right.

So what do we do here? Well, what are we going to do? We're actually going to do something called, let me do this in pink.

So we're going to use something called a reversed. computation history, which is quite a mouthful. But the idea here is that instead of doing this, we're actually going to reverse every other one here.

Let's say the last one's reversed. So here it's more now like W pound sign W reverse and that is a context tree language because uh this is kind of like a palindrome with a pound sign in the middle. Actually it is a palindrome. So and from C1 to C2 it these two configurations are essentially the same but one of them is the reverse of the other one.

There's a small difference but it's roughly the same. So the basic idea is we build a CFG that checks one that checks one of the following. So if any one of these conditions is true, then it's not a computation history. So if c0 is not the starting config, if it's not the starting one, then it's clearly not a computation history. And I can actually show that that's regular.

I'll let you actually think about that. Similarly, if c sub m is not accepting, and it turns out that that one is also regular too, and then the third one is for some i, we have that if we look at c sub i, let's say it's forward and c i reverse. then more after. And then ci does not yield. Oh this would be plus one, sorry.

ci plus one. So it doesn't yield it there. Alright so how do we actually do this? Well it's essentially W pound sign W reverse. So if there is some i that's like this, then it must be of the form gamma star then c i pound sign c i plus one reverse and then gamma star afterward.

So I don't care what happens afterward. As long as this one does not yield this one, then we're all good. So how do we do this?

Well, if we actually look at these two configurations side by side, let's say that C i starts with a b c then the pound signs in the middle then that means that C i plus one ends with C b a like this. So then what we know what we can figure out then is that wherever the stuff that changes is in a little window on both sides. So what we can say is that for the first part let's call it W then the second the part at the very end is going to be W reversed for sure.

Not the part that is different, just the part that's outside of the little window. And actually the part in between, let's call it X, on the other side is going to be X reversed. And we know how to do this.

So we know how to check for each of these individual segments because it's essentially W, W reverse and we know how to do that easily. It's just these parts right here that are that you have to check for but I claim that this part is easy to do because there are only finitely many transitions for Yeah, there are only finitely many transitions of the Turing machine So we're trying to solve the ATM problem again. So we're given a Turing machine. So these ones are for Turing machines, although it's not really that important. The important part is that we can actually check for all possible combinations that can appear here.

And what we can do, what we want to have is that we want not that these two segments are the same, but they're different. So either one... the outside segments are different, the insides are different, or three, the transition was not applied correctly. And we just need to look at the transition function of the Turing machine, and there are only finitely many transitions that can occur.

And so we just encode all of them into the context-free grammar. And since there's only finitely many, we can put finitely many things into a context-free grammar, and that's no issue whatsoever. And since it's OR for all of these, then as long as at least one of these occurs, then the grammar should accept that string. So therefore the only string that is not accepted is any accepting computation history.

So the only possible string the CFG generates is some accepting computation history. And so, therefore, if I can check whether a grammar has every single string in its language or not, then I can check whether or not it accepts some computation history. So, if the language of the grammar really is sigma star, then you can... then M does not accept W because it can't possibly have an accepting computation because if it did, then this grammar would not accept it.

And so therefore, because this language is sigma star. And then otherwise, if the language of the grammar is not sigma star, then M accepts W because the only possible string that it... this grammar does not make is some accepting computation history.

And that's it. Pretty cool. And I know that this is a context-free grammar because we had unions of regular languages and context-free languages, only a finite number of them. And so therefore the entire thing really is a context-free grammar and that's in fact it.

So This actually concludes everything I wanted to do, but let's do a final summary table of decidable and undecidable stuff. So we have DFA and NFA and regular expression being one row. We have CFGs and PDAs being another one. You can do deterministic context-free and that's actually a really interesting question, but I'm not going to do it here because it's actually very complicated. We had the LBA question and we have the Turing machine question.

Let's see if all this fits. All right, so let's have some columns here. So we had the A acceptance problem.

we had the emptiness problem, we had the equivalence problem, and the all problem. Actually I didn't do the equivalence problem for CFGs, but I can do this really quick. EQCFG is undecidable, and the reason for this is that I'm just going to sketch it right here really quick. Where we build a CFG that has sigma star, its language and then feed the input CFG and that one. to the decider for eq and that's all you need to do because if if then we can solve the all problem because if if the if the equivalence one says yeah they're the same then the original one had language being sigma star and if it said that they were different therefore the original one did not have sigma stars as language And so therefore we could solve the all problem, but we know the all problem is not possible.

And so therefore the EQ problem is not possible either. All right. So what do we have here? So DFAs are checks on everything.

I didn't do all DFA, but you can actually work with the EDFA one and you can show all DFA is decidable too. In fact. Virtually any problem that you come up with for DFAs is going to be decidable. CFGs and PDAs, we had checks on the first two and frowny faces on the last two.

For LBAs, we had yes on the acceptance problem, but we have frowny faces on the emptiness problem. For the same reason... for Turing machines, we have EQ also being undecidable because we can just make a Turing an LBA that has empty language and feed the input one and the constructed one to the EQ machine. And so that therefore that would solve the emptiness question, but we know that's undecidable. So this one's also not possible.

The all one is also not possible. for very similar reasons that the emptiness one is. And then for turning machines, it's frowny faces everywhere.

So frowny face for you, frowny face for you, frowny face for you, frowny face for you. All right, so the interesting question, and this is like the subject of research level stuff, is what about deterministic context-free languages? So if it happened to be like all checks on both of them, on CFGs and PDAs and DFAs, then the DPDA1 would be all checks here.

So is it that they're all checks for DPDAs? Because we show that they're not the same thing as PDAs, not equivalent in power. So maybe we do recover the equivalence in the all problem.

We definitely get the acceptance and the... emptiness one for DPDAs. That's pretty clear because it's checks for both, but it's just for these last two. It actually gets quite interesting. So that's all I wanted to do for today.

So congrats, you made it to the end. That was the entire theory course in four videos. Thank you all for sticking around and supporting the channel.

I am gonna go lie down pretty soon. No. It was fun doing this.

It was a lot of work and the stream is... I need to fix the stream. I know it's a terrible quality sometimes. I need to fix that but hopefully you learned something. Make sure to subscribe to the channel if you haven't yet.

There are many other links in the video description if you want to support the channel further. I'm currently doing one-on-one tutoring sessions. If you want to take part in that my email is in the video description. And as always, thank you for watching and I'll see you next time.

Transcript for:Overview of Decidability and Undecidability

Transcript for:
Overview of Decidability and Undecidability