Turing Machines - what are they? + Formal Definition

Here we define what a Turing machine (TM) is, and give a formal definition. It's an extension of a DFA or a PDA in that (1) the input can be overwritten with new values, (2) the "tape head" can move back and forth, and (3) new cells can be allocated at any point (if the tape head is at the "right end" and tries to move right). We will eventually show that this is equivalent to the modern notion of a "computer."

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

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