How do you prove Rice's Theorem in 12 minutes? - Easy Theory

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