Moving Left Three Times in a Row is Undecidable - Easy Theory

Here we show that the problem of determining whether an arbitrary Turing Machine moves left three times in a row is undecidable, but checking if such a machine moves left at all IS decidable! There is a very fine line between decidable and undecidable here. The trick with the decidable part is to run the machine "long enough" before you know that it will never move left; and for the undecidable part, encoding each transition to always interject a Right move and then a Left move, and force 3 lefts in a row at the end. (Update: it IS decidable to check if the Turing Machine moves left TWICE in a row; try to prove why this is.)

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 1:45 - Moving Left At Least Once is Decidable 5:06 - Moving Left 3 Times in a Row is Undecidable

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=64b_O8ryoNA