Thanks to my supporters Yuri, vinetor, Ali (UA-cam) and Bruno, Timmy, Micah (Patreon) for making this video possible! If you want to contribute, links are in the video description.
Because we need a machine which language is regular only if M accepts w, and we take advantage of the fact that the star operation on an alphabet is regular (so if we accept all words, then it is regular) (even if this word could be recognized but a non-regular machine)
My exam is tomorrow and this is a proof me and my buddies were scratching our heads on! As always you explained it very intuitivelty! Would you prove that the complement of Regular TM is undecidable in a similar way?
Thanks - you could (or even use Rice's theorem for extra fun), but there's an easier way. Since decidable languages are closed under complement, then if the complement of REG_TM were decidable, then the original would be, but it isn't.
If M' only accepts {0^n 1^n}, then {0^n 1^n} is L(M'). That's the definition of a language of a TM. It doesn't matter if your input x is in the form or not. If it's not, then it's not in L(M'). But it doesn't change the language of M'.
Why does M' accept the input x when it is not a regular language? I think for me with these proofs, using input x vs is slightly confusing... :( Could you please explain why we bring in the input x?
Input x can be anything, it does not have to be of the form "M,w" or just "w". We only use it in M', which is a TM that is created when launching the algorithm to solve Atm on an pair (M,w). This algorithm is a TM, I will call it S but @EasyTheory doesn't give it a name in his video, he just shows it can't exist, which is why a decider for REGULARtm can't exist. The point of creating that TM M' is so we can use our decider R for REGULARtm to build a decider S for Atm. To be able to use the decider R, we need to give it a TM (here, M') as input, which can have either a regular or a non-regular language L(M') so that R either accepts or rejects M'. To get those 2 possible languages for M', we first need to know of a potential non-regular language that could be L(M'). A famous example is 0^n 1^n. We observe that any input x is either of the form 0^n 1^n or isn't. If it is (step 2(a) inthe video), then we add it to the language M'. This doesn't mean that L(M') will eventually be the non-regular language 0^n 1^n. If it isn't, we check if M accepts w. But if M accepts w, hell, we already know that M' will accept all x's so L(M') can just be defined as Σ*. If it isn't and M does not accept w, we can conclude that M' will never accept any x that is not of the form 0^n 1^n since the statement "M does not accept w" is not going to change. In the end, we find ourselves with one of two different languages, and the decisive factor is only that M either accepts or rejects w. If M accepts w, L(M') = Σ*. If M rejects w, L(M') = {0^n 1^n | n >= 0} because those are the only inputs that were accepted (step 2(a) in the video) Now, we can use our assumed decider R on M', which will accept if L(M') is regular, so Σ*, and reject if L(M') is non-regular, so here: {0^n 1^n | n >= 0}. If R accepts, it means M accepted w. If R rejects, it means M rejected w. This whole operation gives us a decider for Atm, since we can repeat it for every (M,w) pair. I think this is not a very helpful comment at first but I believe it can be understood if you just read it slowly :D. Overall, I just repeat what the video is saying.
Not quite. Regardless of what happens, L(M') *contains* the strings of the form 0^n 1^n, so unless something else happens, L(M') = {0^n 1^n : n at least 0}. Now, if the *original* TM M accepts w, then M' will accept *all other* strings in addition, which means L(M') = Sigma*.
@@EasyTheory There is this thing that keeps buzzing me what if x is not in the form of 0n1n and M' does not accept w meaning it rejects or loops? Shouldn't its language be the empty set then?
@@rookiecookie8258 this "x not in the form of 0n1n" would only be one input to the TM M'. The supposed decider will call M' with all possible x's, which includes those of the form 0n1n. In the end, if M does not accept w, the language of M' will be composed of all the words (= inputs = all x's) of the form 0n1n.
The machine will loop forever. And the language recognized by M' is 0^n1^n which is non-regular (remember that L(M') is not regular means that the set of strings accepted by M' is not regular, strings that are rejected or cause an infinite loop do not matter). This is enough for the proof.
Thanks to my supporters Yuri, vinetor, Ali (UA-cam) and Bruno, Timmy, Micah (Patreon) for making this video possible! If you want to contribute, links are in the video description.
You are truly a blessing for us CS students.
Thank you for your video! However, i am still confused about the first step to build M': why do we need to use a non-regular language 0^n1^n at first?
Because we need a machine which language is regular only if M accepts w, and we take advantage of the fact that the star operation on an alphabet is regular (so if we accept all words, then it is regular) (even if this word could be recognized but a non-regular machine)
My exam is tomorrow and this is a proof me and my buddies were scratching our heads on! As always you explained it very intuitivelty!
Would you prove that the complement of Regular TM is undecidable in a similar way?
Thanks - you could (or even use Rice's theorem for extra fun), but there's an easier way. Since decidable languages are closed under complement, then if the complement of REG_TM were decidable, then the original would be, but it isn't.
What if x isn't of the form 0^n 1^n and M on w does not accept - Won't the language accepted by M' be the empty set?
If M' only accepts {0^n 1^n}, then {0^n 1^n} is L(M'). That's the definition of a language of a TM. It doesn't matter if your input x is in the form or not. If it's not, then it's not in L(M'). But it doesn't change the language of M'.
Why does M' accept the input x when it is not a regular language? I think for me with these proofs, using input x vs is slightly confusing... :( Could you please explain why we bring in the input x?
Input x can be anything, it does not have to be of the form "M,w" or just "w". We only use it in M', which is a TM that is created when launching the algorithm to solve Atm on an pair (M,w). This algorithm is a TM, I will call it S but @EasyTheory doesn't give it a name in his video, he just shows it can't exist, which is why a decider for REGULARtm can't exist.
The point of creating that TM M' is so we can use our decider R for REGULARtm to build a decider S for Atm. To be able to use the decider R, we need to give it a TM (here, M') as input, which can have either a regular or a non-regular language L(M') so that R either accepts or rejects M'.
To get those 2 possible languages for M', we first need to know of a potential non-regular language that could be L(M'). A famous example is 0^n 1^n.
We observe that any input x is either of the form 0^n 1^n or isn't.
If it is (step 2(a) inthe video), then we add it to the language M'. This doesn't mean that L(M') will eventually be the non-regular language 0^n 1^n.
If it isn't, we check if M accepts w. But if M accepts w, hell, we already know that M' will accept all x's so L(M') can just be defined as Σ*.
If it isn't and M does not accept w, we can conclude that M' will never accept any x that is not of the form 0^n 1^n since the statement "M does not accept w" is not going to change.
In the end, we find ourselves with one of two different languages, and the decisive factor is only that M either accepts or rejects w.
If M accepts w, L(M') = Σ*.
If M rejects w, L(M') = {0^n 1^n | n >= 0} because those are the only inputs that were accepted (step 2(a) in the video)
Now, we can use our assumed decider R on M', which will accept if L(M') is regular, so Σ*, and reject if L(M') is non-regular, so here: {0^n 1^n | n >= 0}.
If R accepts, it means M accepted w. If R rejects, it means M rejected w.
This whole operation gives us a decider for Atm, since we can repeat it for every (M,w) pair.
I think this is not a very helpful comment at first but I believe it can be understood if you just read it slowly :D. Overall, I just repeat what the video is saying.
Basically, we want to build M' such that when M does not accept w, the only x's that M' accepts form a non-regular language.
@@hisao1291this explaination was so good, thankyou
@@hisao1291 i guess my confusion is why do we accept in M' 0^n1^n form? Why isn't that rejected and R reject
Run M on W and if accept accept x but what if M does not stop??
I wish you were teaching the course that I am currently taken.
why if x is in the form 0^n 1^n we accept?
it wouldn't happen because 0^n1^n is nonregular, no TM can recognize nonregular languages.
@@serendipityx737 There are definitely TMs that can recognize non-regular languages.
Thanks from India 🇮🇳
Thanks, mate!
You are brilliant!!!!!!! thank you so much!!!!!
Underrated God
What if w=x=0^n 1^n m' will accept x which is like accepting w but then L(m')={0^n 1^n} even if m' accept w!?
Not quite. Regardless of what happens, L(M') *contains* the strings of the form 0^n 1^n, so unless something else happens, L(M') = {0^n 1^n : n at least 0}. Now, if the *original* TM M accepts w, then M' will accept *all other* strings in addition, which means L(M') = Sigma*.
@@EasyTheory Thanks for replying to the comments. This comment helped me to fully understand it.
@@EasyTheory Thank you so much.. I was seriously struggling on understand this part and now I finally understand!
What if M runs forever on w? Then M' will never take on either form?
Absolutely can - IF we ran M' ourselves, but we never do that. We feed it to the supposed decider.
@@EasyTheory There is this thing that keeps buzzing me what if x is not in the form of 0n1n and M' does not accept w meaning it rejects or loops? Shouldn't its language be the empty set then?
@@rookiecookie8258 this "x not in the form of 0n1n" would only be one input to the TM M'. The supposed decider will call M' with all possible x's, which includes those of the form 0n1n. In the end, if M does not accept w, the language of M' will be composed of all the words (= inputs = all x's) of the form 0n1n.
wait what if M does not accept w in M' ?
The machine will loop forever. And the language recognized by M' is 0^n1^n which is non-regular (remember that L(M') is not regular means that the set of strings accepted by M' is not regular, strings that are rejected or cause an infinite loop do not matter). This is enough for the proof.
I thought regular languages were decidable..
Yes they are. Buy A turing machine to decide whether a language is regular or not is undecidable.