Here we show that determining if a Turing Machine state is "useless" is undecidable. Easy Theory Website: https://www.easytheory.org Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join Donation (appears on streams): https://streamlabs.com/easytheory1/tip Paypal: https://paypal.me/easytheory Patreon: https://www.patreon.com/easytheory Discord: https://discord.gg/SD4U3hs #easytheory Youtube Live Streaming (Sundays) - subscribe for when these occur. Social Media: Facebook Page: https://www.facebook.com/easytheory/ Facebook group: https://www.facebook.com/groups/easytheory/ Twitter: https://twitter.com/EasyTheory Merch: Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122 Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1 Gold Supporters: Micah Wood Silver Supporters: Timmy Gy ▶SEND ME THEORY QUESTIONS◀ ryan.e.dougherty@icloud.com ▶ABOUT ME◀ I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes. ... https://www.youtube.com/watch?v=PvdnxMmd2lA

Here we prove that the emptiness problem for Turing Machines is undecidable via Rice's theorem; this problem is also known as the E_TM problem. This is a simple application of Rice, and all we need to do is to show that the language is a nontrivial property of TM languages. The example TMs needed are very easy and straightforward. Easy Theory Website: https://www.easytheory.org Discord: https://discord.gg/SD4U3hs If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1 ▶ABOUT ME◀ I am a professor of Computer Science, and am passionate about it. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes. The views expressed in this video are not reflective of any of my current or former employers. ... https://www.youtube.com/watch?v=b33N0rDhVlY

Here we prove (and state) the pumping lemma for context-free languages (CFL), by observing a parse tree of a CFG in Chomsky Normal Form (CNF). The properties of the parse tree allow us to show that if the string generated is big enough, the longest root-to-leaf path in the parse tree must repeat a variable. We utilize this fact to generate more parse trees (i.e., more strings the CFG makes), and look at the properties of parts of this string. Easy Theory Website: https://www.easytheory.org Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join Donation (appears on streams): https://streamlabs.com/easytheory1/tip Paypal: https://paypal.me/easytheory Patreon: https://www.patreon.com/easytheory Discord: https://discord.gg/SD4U3hs #easytheory Youtube Live Streaming (Sundays) - subscribe for when these occur. Social Media: Facebook Page: https://www.facebook.com/easytheory/ Facebook group: https://www.facebook.com/groups/easytheory/ Twitter: https://twitter.com/EasyTheory Merch: Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122 Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1 Gold Supporters: Micah Wood Silver Supporters: Timmy Gy ▶SEND ME THEORY QUESTIONS◀ ryan.e.dougherty@icloud.com ▶ABOUT ME◀ I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes. ... https://www.youtube.com/watch?v=-UH9L2sJpPQ

Here we prove Rice's Theorem in 12 minutes, which is the shortest proof I can find! The idea is to show that every nontrivial property of Turing Machine languages is undecidable. We show that if such a property were decidable, then we can decide A_TM, which is well known to be undecidable. The trick is to use the fact that the property is nontrivial to find a machine that is in the property, and another that is not, and to construct a new machine that behaves like one if and only if the input TM accepts w. Patreon: https://www.patreon.com/easytheory If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1 ▶ADDITIONAL QUESTIONS◀ 1. Does the property always have to be nontrivial? 2. Does the property always have to be a property of TM languages? 3. Are there examples of the property that are recognizable? ▶SEND ME THEORY QUESTIONS◀ ryan.e.dougherty@icloud.com ▶ABOUT ME◀ I am a professor of Computer Science, and am passionate about CS theory. I have taught over 12 courses at Arizona State University, as well as Colgate University, including several sections of undergraduate theory. ... https://www.youtube.com/watch?v=jIAEpYwJgbA