Turing Machine Example and Computation (Can you guess what it does?)
Vložit
- čas přidán 23. 11. 2020
- Here we give an example of a Turing Machine (TM), and go through computing a given input string on that TM. We have to keep track of (1) the contents of the tape, (2) where the tape head is on the tape, and (3) what state we are currently in. There are a lot of steps, but each one is quite simple. We also go over conventions in how the transitions are written (as well as what happens if they are not written). Can you guess what the TM actually computes?
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 • Turing Machines - what... for more details.
Easy Theory Website: www.easytheory.org
Become a member: / @easytheory
Donation (appears on streams): streamlabs.com/easytheory1/tip
Paypal: paypal.me/easytheory
Patreon: / easytheory
Discord: / discord
#easytheory
Merch:
Language Hierarchy Apparel: teespring.com/language-hierar...
Pumping Lemma Apparel: teespring.com/pumping-lemma-f...
If you like this content, please consider subscribing to my channel: / @easytheory
▶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.
So I am doing coursework from home this term b/c my immune system has issues and covid is still a thing... I want to let you know, I don't even really watch the lecture recordings. I come here and Voila! I understand!!!!! It's almost magical.
I watched videos related to the topic both in my own language (Turkish) and in English. I couldn't understand the topic even from Indian professors. But when I watched your video, I really understood the topic. You're amazing.
Thank you, you made learning TOC much easier, hope your channel will receive more attention
"Look at q_0, and we see a 0 on the tape. Well! By Golly!"
you saved my lifeee !! you are better than my professor lol
you're an absolute SLAY! great explanation
Love your intro to computation lectures; we have a similar course in uni and I find the lectures on turing machines a bit confusing.
thanks a lot for you effort
Hi Professor,
Hello Professor Dougherty, It would be beneficial to post PDF, JPG, or PNG of the machine to follow the video. I use windows snipping to copy the image on the screen. Thanks
you made my mind click thank you
thanks dude
how would a transition function look with this? is there a video on that?
The video is awesome, thank you. What would be great to have is how do we start from a definition of a language to implementing a TM for it
I have one question sir, how can we design a TM such that (0^n 10^3n) how do we solve this?
wow, thank you so much <3
God bless you!
I appreciate how clear the video is and how the TM works - but it would be great if you told us what it did. It seems to be replacing the 0's with X's but I am not sure if it is only checking the tape for X's and 0's or also checking for an even number of 0's.
The TM is accepting language, L = {0^2^n | n>=0}
what degree teaches that stuff? because that's the path I want to follow(the math, theoretical aspect of cs)