Undecidable Problem: Moving Left 3 Times in a Row

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.)

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
Discord: https://discord.gg/SD4U3hs

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.