The Recursion Theorem: Proof + Examples (Advanced ToC) - Easy Theory

Here we prove the recursion theorem, which is one of the most important results in computability theory. This informally shows that any Turing Machine can "obtain" its own description on the tape, and then compute something with it. This video follows Sipser's presentation of the recursion theorem, with slight alterations to make understanding easier. The recursion theorem is not super difficult to show, but it gives the theorist a strong tool to show that many languages are undecidable, not recognizable, or even not computable in only a few lines.

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

Timeline: 0:00 - Intro 0:15 - Informal Description of Recursion Theorem 1:29 - The convert_to_TM function 3:50 - Construction of the SELF Turing Machine 10:15 - Formal Statement of Recursion Theorem 12:26 - Proof of the Recursion Theorem 17:45 - Example 1: A_TM is not Decidable 20:23 - Example 2: MIN_TM is not Recognizable

What is a Turing Machine? It is a state machine that has a set of states, input, tape alphabet, a start state, exactly one accept state, and exactly one reject state. See https://www.youtube.com/watch?v=j0bIxPqlYLE&ab_channel=EasyTheory for more details.

▶CONTRIBUTE◀ 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. ... https://www.youtube.com/watch?v=iXpp5X6WPkE