Left-Reset Turing Machines (LRTM) Explained

Here we look at another Turing machine variant, namely the left-reset Turing Machine (LRTM). Here, the RESET instruction will have the tape head immediately jump to the first cell on the tape. The way to simulate this is with (1) shifting the input 1 cell to the right, (2) placing a special symbol in the first cell of the tape, and (3) whenever we want to simulate a RESET transition, execute multiple L transitions until we encounter the $, and then move R one position. We go over the many details needed in how to implement this correctly, but this is the basic idea.

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.

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

#easytheory

Youtube Live Streaming (Sundays) - subscribe for when these occur.

Social Media:
Facebook Page: https://www.facebook.com/easytheory/
Facebook group: https://www.facebook.com/groups/easytheory/
Twitter: https://twitter.com/EasyTheory

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

Gold Supporters: Micah Wood
Silver Supporters: Timmy Gy

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