L17: Using Reductions to Prove Language Undecidable

[@baharehshakiba2957]

Best Professor for Theory of Computation . I would truly appreciate you for your good teaching.

[@nimeshkrishnani]

Untangling the whole explanation of getting a universal turing machine in the given A'circ We essentially are making the R(magical decider for our A'circ) equivalent to a more selective UTM 1.consider a machine(decidable) that compares to our previously magically found out w'(or predefined as an example consider a language that takes 2 a's and 5b's so our w could be aabbbbb or this w' might be any string) 1.1we take the input M and w compare w to our w' if it doesn't match one right rotated w' or w(we reject it) this is the part where our UTM is more selective 1.2 if its a single right rotation of w' accept it 1.3 if w=w' we simulate M on w 2. consider (1.3) this simulation musn't always come through since, you know UTM is recognizable but our magical R does it it gives us if w is accepted in M it accepts all its rotations, if not it rejects 3. the last part of the 2'nd point can't happen, but adjoining all we get a simulation of ATM which is proven undecidable. and voila!

[@andrewlanham3507]

Really good explanation! For visual learners, the drawings make this more easily digestible

[@adiesha_]

This is a good explanation. It will take some time to understand this but it is worth it!

[@arashjamshidi3249]

Just to be clear for those who didn't understand the proof: Mw accepts "any" rotation of W. We give W to ATM and we give Mw to R (in parallel) any of them accepts/reject first, we go to accept/reject state. But this is impossible, because suppose M (ATM) can not decide W (it runs forever), but with this method we can decide for any W (with the help of R) which is a contradiction (because ATM is not decidable)

[@hajijohn1]

21:50 : actually this is a turing-reduction (not a mapping-reduction), but proving problems undecidable, we can use it.

[@buttegowda]

At 43:40, why Mw just accept if w`=w ? Why should it simulate for that ?

[@Mike-ci5io]

+buttegowda because you want H to accept iff R accepts Mw and M accepts w (and you have to simulate M on w to see if it accepts you can't just declare it accepts)

[@buttegowda]

+Intelli Vester,Thanks a lot.

[@pcheo]

Thank god I found this. I cannot understand my India professor's lectures

[@anjamisimovic9214]

just beautiful. thank you man

[@mikevar5487]

Thank you so much, I finally understand!

[@itsnow385]

Whenever I have had bad professors, Professor Gusfield has always rescued me

[@nascarsayan]

Love this lecture

[@MahiTanMazy]

Very good professor I wish my India teacher Graham was good like you - Muhibear

[@AKAFlaze]

What is the significance of simulating M on input w in the Mw machine?

[@MrGillamkid]

Let's see if I get this Outside the proof (meaning the real world with no false assumptions), if you are given a _string_ (any string at all) you can build a machine M0 so that it's language is { w' | w' is in the language iff w'-circ is in the language} . What you can't do (but we temporarily pretend we can in the video proof) is create a Machine R where given a _Turing_ _Machine_ (any Turing Machine at all) you decide whether that Turing Machine's language is a circular language. In the video, he called his machine M-subscript-w. I'm calling the same machine M1 The language of M1 is { w' | w' is in the language iff w'-circ is in the language} *iff* M accepts w. Running M on input w could be undecidable (which is why A[TM] is undecidable). Therefore M1 could be undecidable, but that's okay, no one said it had to be, we just have to know what M1's language is. If M accepts w, M1 accepts and it's language is circular. If M1 loops, we could nondeteministically say it _would_ reject and its language wouldn't be circular. Because we know what it _would_ do, we know what its language is, even if M1 is undecidable. M1's language is w-circ iff M accepts w. Because of that, running R on input M1 and deciding whether M1 defines a circular language is the same as deciding if M accepted or rejected w.

[@asitisj]

the sign of m accepts, m :> , I have seen it in Haskell

[@VAbhijayArora]

What's the text book's name?

[@laveenabachani]

Abhijay Vuyyuuru michell Spenser

[@itsrena9750]

I'm not convinced of his Mcirc proof. It's not clear. It is like he wasn't really prepped for this lecture

[@addiskflie4131]

Prove that the language L= {ai: ai ϵL (Mi)} is Turing acceptable and undecidable.

[@Mike-ci5io]

43:40 it should be.......If input w' != w AND w' != w rotated one place, REJECT

[@TheDaliaJonas]

thanks!

[@none-xv2mb]

H has R inside at 19:47 ... I like the sound "krrh"