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!
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)
+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)
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.
Best Professor for Theory of Computation . I would truly appreciate you for your good teaching.
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!
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)
Really good explanation! For visual learners, the drawings make this more easily digestible
21:50 : actually this is a turing-reduction (not a mapping-reduction), but proving problems undecidable, we can use it.
This is a good explanation. It will take some time to understand this but it is worth it!
At 43:40, why Mw just accept if w`=w ? Why should it simulate for that ?
+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)
+Intelli Vester,Thanks a lot.
What is the significance of simulating M on input w in the Mw machine?
just beautiful. thank you man
Thank you so much, I finally understand!
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.
the sign of m accepts, m :> , I have seen it in Haskell
I'm not convinced of his Mcirc proof. It's not clear. It is like he wasn't really prepped for this lecture
Prove that the language L= {ai: ai ϵL (Mi)} is Turing acceptable and undecidable.
43:40 it should be.......If input w' != w AND w' != w rotated one place, REJECT
Whenever I have had bad professors, Professor Gusfield has always rescued me
What's the text book's name?
Abhijay Vuyyuuru michell Spenser
Love this lecture
Very good professor I wish my India teacher Graham was good like you - Muhibear
H has R inside at 19:47 ... I like the sound "krrh"
Thank god I found this. I cannot understand my India professor's lectures
thanks!