Here we show that a language L is decidable if and only if it is recognizable and its complement is recognizable. One direction is straightforward, and the second relies on a recognizer for L and its complement must have one of the two accept on every string, and so we "run in parallel" until one of the two accepts. This shows that A_TM-complement is not recognizable.
Easy Theory Website: www.easytheory.org
Become a member: ru-vid.com/show-UC3VY6RTXegnoSD_q446oBdgjoin
Donation (appears on streams): streamlabs.com/easytheory1/tip
Paypal: paypal.me/easytheory
Patreon: www.patreon.com/easytheory
Discord: discord.gg/SD4U3hs
#easytheory
RU-vid Live Streaming (Sundays) - subscribe for when these occur.
Social Media:
Facebook Page: easytheory/
Facebook group: groups/easytheory/
Twitter: EasyTheory
Merch:
Language Hierarchy Apparel: teespring.com/language-hierarchy?pid=2&cid=2122
Pumping Lemma Apparel: teespring.com/pumping-lemma-for-regular-lang
If you like this content, please consider subscribing to my channel: ru-vid.com/show-UC3VY6RTXegnoSD_q446oBdg
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.
18 янв 2021
