Undecidable Languages - Easy Theory

Currently Playing: 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: 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.