Generally i dont comment on youtube videos , Thanks for this playlist i completed at a stretch 113 videos from 1 in one day and i have attempted my exam good thank you...
Thank you so much sir for providing such a great tutorials.. Tommorow is my exam of toc and since 1 day i was only watching these tutorials...and right now it's 2.45 am in the morning and i have just finished these tutorials..tnkuh so much .. again..
So according to my professor, in order for a reduction from A to B to occur, not only do we need to show that A implies B, but that B implies A. In this case, we're reducing from Atm to PCP, so we need to show not only that if our problem of PCP is solvable imply the input of Atm is solvable (solvable meaning accepted by the Turing machine that runs it), but also that if the input of Atm is solvable, it implies that the PCP problem is possible. There's key information missing regarding how it's a both way implication. Even if this is not the case, several key steps in the proof is missing. For one, the problem he's solving is a modified PCP problem, which assumes that the first domino in the matching set is the one with the initial configuration of the Turing machine on the bottom tile. Without this assumption, any domino from step 4 would be a match, meaning any Turing machine with a symbol in its tape character set would produce a PCP problem with a match. This is useless in proving PCP is undecidable. This video works as a broad, general look at the proof of PCP, and for that kudos, and I think you did a great job in making reductions more accessible to people. But commenters are calling this a perfect explanation, which is just not true
Yes. As Rohan said two way conversion is only required to establish equivalence of the two problems. But for one problem to reduce to another, it need not be equivalent.
Hey maybe you can clear my doubt...Are there any rules for creating the dominos in each step? Like why did we have the first domino as #/#q0 aba# and why not in some other form? Same question for Step 6 (#/B#) and Step 7 (q2##/#) dominos also....any clarification will be really appreciated.
First general Draft: The input/state/tape of each TMP, including all the history, can be translated (see "Steps 1-7") in terms of dominos. This (see "Solution") remains true if we remove the history. If PCP would be decidable then the same would occur with TMP, which is (see Videos 100-101) not true.
Sir you are the best!! Your videos help me to sleep at night. Love you sir.. bas ek aur request thi ki ek aur esa example upload kardijiye on PCP, would be very helpful. Thanks again 💋💋
@Neso Academy; Sir, how is the Turing Machine shown in this lecture is related to/represents the ACCEPTANCE problem? Also are there any rules for creating the dominos in each step? Like why did we have the first domino as #/#q0 aba# and why not in some other form? Same question for Step 6 and 7 dominos also.... Pls clarify sir Or anyone who has clarity on these..ITS URGENT
A HUGE THANK YOU TO NESO ACADEMY WITH ALL YOUR LECTUTE VIDEOS I HAVE ATTEMPTED 60 MARKS IN SEMISTER CONFIDENTLY!
thankyou from my bottom of my heart!
Generally i dont comment on youtube videos , Thanks for this playlist i completed at a stretch 113 videos from 1 in one day and i have attempted my exam good thank you...
Wow
Thank you so much sir for providing such a great tutorials..
Tommorow is my exam of toc and since 1 day i was only watching these tutorials...and right now it's 2.45 am in the morning and i have just finished these tutorials..tnkuh so much .. again..
what u doing rn in life bro after engineering
Please answer it 😢
Yeah answer @gauravpant4288
Thanks sir for this precious knowledge and your precious time
So according to my professor, in order for a reduction from A to B to occur, not only do we need to show that A implies B, but that B implies A. In this case, we're reducing from Atm to PCP, so we need to show not only that if our problem of PCP is solvable imply the input of Atm is solvable (solvable meaning accepted by the Turing machine that runs it), but also that if the input of Atm is solvable, it implies that the PCP problem is possible. There's key information missing regarding how it's a both way implication.
Even if this is not the case, several key steps in the proof is missing. For one, the problem he's solving is a modified PCP problem, which assumes that the first domino in the matching set is the one with the initial configuration of the Turing machine on the bottom tile. Without this assumption, any domino from step 4 would be a match, meaning any Turing machine with a symbol in its tape character set would produce a PCP problem with a match. This is useless in proving PCP is undecidable.
This video works as a broad, general look at the proof of PCP, and for that kudos, and I think you did a great job in making reductions more accessible to people. But commenters are calling this a perfect explanation, which is just not true
that doesn't sound right, cause then it's equivalence not reduction
Yes. As Rohan said two way conversion is only required to establish equivalence of the two problems. But for one problem to reduce to another, it need not be equivalent.
Please include some video on LBA , thank you for all this amazing content.
Why isn't than Partially Decidable when sometimes we have solutions and sometimes not ?
excellent,marvelous,no words
thank you so much for your support . awasome work ,thank you , thank you , thank you.
2x speed users.............. RIP
What are u blabbering 😒😒😒
Bhai mai to 3x pr sun rh tha😢😢
😶🌫️😶🌫️😶🌫️😶🌫️😶🌫️
X_x
Ur doing a grt job👍perfect explanation👏
Hey maybe you can clear my doubt...Are there any rules for creating the dominos in each step? Like why did we have the first domino as #/#q0 aba# and why not in some other form? Same question for Step 6 (#/B#) and Step 7 (q2##/#) dominos also....any clarification will be really appreciated.
@@neonguy8000 Have you got the answer yet??...if yes the please do share it with me.
First general Draft:
The input/state/tape of each TMP, including all the history, can be translated (see "Steps 1-7") in terms of dominos.
This (see "Solution") remains true if we remove the history.
If PCP would be decidable then the same would occur with TMP, which is (see Videos 100-101) not true.
Finally completed👌💯
thanks to your lectures
Sir you are the best!! Your videos help me to sleep at night. Love you sir.. bas ek aur request thi ki ek aur esa example upload kardijiye on PCP, would be very helpful. Thanks again 💋💋
Yes, please upload one more example. You are the best!!!
a good 27 min. sleep . 🥱
Pls make a video on example of pcp
thank you sir i got a lot of information from this tutorial.
awesome! thanks Neso!
what is the logic of the conversion steps?
but if we found the solution and matched the string how it is undecidable , is it not decidable?
Could we use dominos for eg q0 a/X q1 as a q0/ q1x? For finding solution for pcp
why you but y in step 2 and you didnt in step 1 it same situation
Ur explaination is very clear nd ur voice is similar to tollywood actor mahesh babu..
where is the acceptance problem of tuning machine?
@Neso Academy; Sir, how is the Turing Machine shown in this lecture is related to/represents the ACCEPTANCE problem? Also are there any rules for creating the dominos in each step? Like why did we have the first domino as #/#q0 aba# and why not in some other form? Same question for Step 6 and 7 dominos also.... Pls clarify sir Or anyone who has clarity on these..ITS URGENT
exactly, this video barely makes any sense
@@arjavgarg5801 one more if we found the solution, how it become undecidable
thank you sir
Perfect explanation...
Bro how right and left can go to final state q2
THANK YOU
sir, all your videos are informative, but why do you repeat the same sentence so many times?
What about LBA
se prendo un bel voto mi tatuo il tuo logo indianozzo