Here we prove a "stronger" version of Rice's theorem, which involves nontrivial properties of Turing Machine languages. The basic idea is to add an additional constraint on what the property can be. Then through this, we can create a reduction from the complement of A_TM to the property, and the former is not recognizable, so the property itself cannot be recognizable. This is stronger because the original Rice's theorem only shows undecidability, but does not necessarily show not recognizable.
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 • How to Use Rice's Theo... for more details.
Contribute:
Patreon: / easytheory
Discord: / discord
Merch:
Language Hierarchy Apparel: teespring.com/language-hierar...
Pumping Lemma Apparel: teespring.com/pumping-lemma-f...
If you like this content, please consider subscribing to my channel: / @easytheory
Ultimate Supporters: (none)
Diamond Supporters: (none)
Platinum Supporters: (none)
Gold Supporters: Anonymous (x1), Micah Wood, Ben Pritchard
Silver Supporters: Timmy Gy
Supporters: Yash Singhal
▶ADDITIONAL QUESTIONS◀
1. What other constraints on P can you use to show not recognizable?
2. What sufficient criteria can show that P and complement of P are not 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.
Негізгі бет Strong Rice's Theorem
Пікірлер: 6