Undecidable Language Example: Moving Left Three 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:   / discord  

If you like this content, please consider subscribing to my channel:    / @easytheory  

▶SEND ME THEORY QUESTIONS◀
[email protected]

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