Undecidable Languages - Easy Theory

Currently Playing: Rice's Theorem Proof using the Recursion Theorem?! - Easy Theory

Here we prove Rice's Theorem using the Recursion Theorem (https://www.youtube.com/watch?v=iXpp5X6WPkE&ab_channel=EasyTheory). The idea is very simple: have the machine obtain its own description, and then simulate itself based on whether or not it has the property, but with a "different" machine that has the opposite property. Specifically, if A has the property, and B does not, then if we find our own machine does have the property, we simulate B on the same input, not A (and simulate A if we do not have the property). This yields a contradiction about the property itself being decidable. What is Rice's Theorem? It is a result that shows a lot of languages are undecidable using simple criteria, involving whether the language is nontrivial (not empty and not everything), and if the language involves Turing Machines and the criteria to be in the language is based on that of the TMs. See https://www.youtube.com/watch?v=kr7n_3LpWhc&ab_channel=EasyTheory for more details. Thanks to the following supporters of the channel for helping support this video. If you want to contribute, links are below. Names are listed in alphabetical order by surname. Platinum: Micah Wood Silver: Josh Hibschman, Timmy Gy, Patrik Keinonen, Travis Schnider, and Tao Su 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 Youtube Live Streaming (Sundays) - subscribe for when these occur. 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 ▶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.