How to apply Rice's Theorem in 5 Minutes? - Easy Theory

Here we look at the language of TMs that accept at most 3 strings, and show via Rice's Theorem that it is undecidable. The key is to point out that THREE_TM is a nontrivial property of Turing Machine languages. I show how to do this in general, and when one should use Rice's Theorem and when one should not.

Timestamps: 0:00 - Intro 0:54 - Step 0: can we apply Rice's Theorem? 1:30 - Step 1: Property of Turing Machine languages 2:45 - Step 2: The property is non-trivial 4:25 - Conclusion of proof

Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join Paypal: https://paypal.me/easytheory 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. What about TMs accepting at most 3 strings and have at most 7 states?
2. What about TMs accepting at least 0 strings?

▶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=kr7n_3LpWhc