Turing Machine Explainer | Solved Examples | Part 2 | Theory of Computation | Sridhar Iyer

It consists of a head which reads the input tape. A state register stores the state of the Turing machine. After reading an input symbol, it is replaced with another symbol, its internal state is changed, and it moves from one cell to the right or left. If the TM reaches the final state, the input string is accepted, otherwise rejected. A TM can be formally described as a 7-tuple (Q, X, Σ, δ, q0, B, F) where − Q is a finite set of states X is the tape alphabet Σ is the input alphabet Δ is a transition function; δ : Q × X → Q × X × {Left_shift, Right_shift}. q0 is the initial state B is the blank symbol F is the set of final states Applications of TM: a. Language Recognition b. Language Generation c. Computation of some functions ABOUT THE VIDEO : In this video I will introduce you all to the concept of Turing Machines. I will also show you how to solve problems based on Palindromes. We will see how to design a TM for a language L={a^n b^n} Kindly Use the Comments Section if you have queries regarding the concept taught in the video. MY OTHER PLAYLISTS: 1. Cryptography and System Security : https://www.youtube.com/playlist?list=PLx2aAxxVN1NV-cQTrfm1XnWU1rDrN3QsJ 2. Advanced System Security and Digital Forensics https://www.youtube.com/watch?v=8Zvjk9iGBzs&list=PLx2aAxxVN1NVk9JwAQwCNA159FrSXQ5Hn