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.
The TM is accepting language, L = {0^2^n | n>=0} But we have to add one extra transition to the diagram in the video, i.e. at state q3 add a self-loop (X->R)
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.
It's seeing if there are 2^n zeros. It cuts the number of zeros in half on every sweep, essentially keeping track whether if there are an even number of zeros on every sweep. If by the time there is only one zero, it accepts it. If at any point there was an odd number of zeros, it rejects it.
@@rathors7184 but it doesn't accept 8 0's, it becomes UX0X0X0X,U and when back to beginning it gets stuck in q3 because there is no 0 after a 0, so it doesn't accept 2^3, actually it doesn't even accept any more 0's than 4 0's, and it has to start with a 0, and after 2 0's, other two 0's must be consecutive and it doesn't accept 3 total 0's, other than these conditions it accepts x infinitely, edit: i saw the channel's comment and x is meant as tape language only so not input, then that makes this machine accept 2^n, 0
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
This is okay to check the acceptance or rejection of a given string once we have the transition graph. However, I am not sure about drawing a transition graph for a given language. Your lectures seem to be for the lecturers, but learners.
It's often hard to do so for an arbitrary language, but what I would do is to split the language into "simpler" languages, and then combine them. For TMs specifically, think first about how the "layout" of the tape contents should be, and then design the TM around that idea (or if you want to use multiple tapes, etc.).
Great question. It can be either, but I intended the alphabet to just be {0}, and not have x. If it did, then the language would be substantially different.
@@EasyTheory So given that the input alphabet is {0} it seems that the accepted language would be limited to {0, 00, 0000}. Any other combination of 0's seems to end up failing in state q3 with either an x or a blank input, except for an empty string which will fail in q0.
This is correct if the input alphabet consists only of 0s and 1s. It can also be equivalently written as 01*(01*(00)?1*)? with the final 1* inside the group, thus being included in the ? ('optional') quantifier at the end. However, if we allow for *any* symbols as input on the tape, especially including _ ('space') as a possible input, then the regular expression is a little bit different (here I will use the common dot-symbol "." to represent 'any symbol' as is common in regular expressions): 01*(01*(00)?1*)?(_.*)? In other words, if your input tape has a space followed by any string of any symbols at the end, then it will also be accepted. You could think of this as working very similar to how end-of-line comments work in many programming languages. Here, instead of the typical // delimiter for comments, it just uses a single _ (space-symbol). [This explains why I suggested the equivalent with the final 1* inside the first optional group, since the structure of the regular expression better matches the structure of the Turing machine graph.] The full language accepts both: 0110100111 but also the same string followed by a space-delimited 'comment': 0110100111_Hello, world! Or, if the input alphabet is restricted to only 0, 1, and _, then you could write the comment in some binary (or ternary!) code like this one with a meaningless/random comment at the end: 0110100111_10101110101000__001_1
@@dn6824 idk i tried doing it multiple times and i keep getting stuck with X as input on q3 with no possible transitions. $00000000u $u0000000u $uX000000u $uX000000u $uX0X0000u $uX0X0000u $uX0X0X00u $uX0X0X0Xu $uX0X0X0Xu ... $uX0X0X0Xu ; u -> R $uX0X0X0Xu ; X -> R $uXXX0X0Xu ; 0 -> X, R $uXXX0X0Xu ; X -> R $uXXX0X0Xu ; 0 -> R then we have X on q3 and no possible transitions. pls tell me if you see what im doing wrong.
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’m saving as many lectures as I am offered. An amazing Educator. Obviously loves to teach. Thankyou
Thank you, you made learning TOC much easier, hope your channel will receive more attention
Thanks very much!
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.
you saved my lifeee !! you are better than my professor lol
You're very welcome!
"Look at q_0, and we see a 0 on the tape. Well! By Golly!"
- Prof. Dougherty, 2022
I need to add "By Golly" to my phrase arsenal.
you're an absolute SLAY! great explanation
Thank you! You explaination made so much more sense than my professors.
how do you decide on the transition function after seeing the problem what is the fundamental of it?
The TM is accepting language, L = {0^2^n | n>=0}
But we have to add one extra transition to the diagram in the video, i.e. at state q3 add a self-loop (X->R)
how do u get to know this?
@@shifa_imran The same TM diagram is given in the TOC book of Michael Sipser. Do refer to it and you will understand better.
@@akashnayak3752 Do you have any ideas where I can find information about "a^c^b" ?
@@begumaygun9173 Sorry I really have no idea.
@@akashnayak3752 thank you anyway
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.
This is super late, but I believe it checks for an even input of 0. I tried 5 0's and it reject, but 6 0's accepted and 2 0's accepted
@@Shadowdoctor117 it accepts a single 0
@@Shadowdoctor117 And it doesn't actually accept 6 0s. Try it while actually tracking the changes to the tape to see.
It's seeing if there are 2^n zeros. It cuts the number of zeros in half on every sweep, essentially keeping track whether if there are an even number of zeros on every sweep. If by the time there is only one zero, it accepts it. If at any point there was an odd number of zeros, it rejects it.
@@rathors7184 but it doesn't accept 8 0's, it becomes UX0X0X0X,U and when back to beginning it gets stuck in q3 because there is no 0 after a 0, so it doesn't accept 2^3, actually it doesn't even accept any more 0's than 4 0's, and it has to start with a 0, and after 2 0's, other two 0's must be consecutive and it doesn't accept 3 total 0's, other than these conditions it accepts x infinitely, edit: i saw the channel's comment and x is meant as tape language only so not input, then that makes this machine accept 2^n, 0
Love your intro to computation lectures; we have a similar course in uni and I find the lectures on turing machines a bit confusing.
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
This is okay to check the acceptance or rejection of a given string once we have the transition graph. However, I am not sure about drawing a transition graph for a given language. Your lectures seem to be for the lecturers, but learners.
Hi Professor,
Could you please explain how to design a Transducer TM that can stimulate a DFA ?
Thank you very much
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
It's often hard to do so for an arbitrary language, but what I would do is to split the language into "simpler" languages, and then combine them. For TMs specifically, think first about how the "layout" of the tape contents should be, and then design the TM around that idea (or if you want to use multiple tapes, etc.).
how would a transition function look with this? is there a video on that?
I have one question sir, how can we design a TM such that (0^n 10^3n) how do we solve this?
I'm surprised I never ran into TM's in discrete math. I was reading an article on AI and it mentioned the TM. So, here I am :)
you made my mind click thank you
thanks a lot for you effort
So does it accept even numbers?
it recognizes {0^(2^n) | n ≥ 0}. in other words, strings of 0's whose lengths are powers of 2
is x part of the input alphabet or only the tape alphabet?
Great question. It can be either, but I intended the alphabet to just be {0}, and not have x. If it did, then the language would be substantially different.
@@EasyTheory So given that the input alphabet is {0} it seems that the accepted language would be limited to {0, 00, 0000}. Any other combination of 0's seems to end up failing in state q3 with either an x or a blank input, except for an empty string which will fail in q0.
@@GDX17 Are you sure about this? Think again about possible strings that could be in this language.
@@moatef1886 does it accept whenever the amount of zeros is equal to a power of two?
@@alexm.2960 Yes. :)
wow, thank you so much
thanks dude
God bless you!
Okay, I think it accepts strings that satisfy this regular expression: 01*(01*(00)?)?1*.
This is correct if the input alphabet consists only of 0s and 1s. It can also be equivalently written as 01*(01*(00)?1*)? with the final 1* inside the group, thus being included in the ? ('optional') quantifier at the end.
However, if we allow for *any* symbols as input on the tape, especially including _ ('space') as a possible input, then the regular expression is a little bit different (here I will use the common dot-symbol "." to represent 'any symbol' as is common in regular expressions):
01*(01*(00)?1*)?(_.*)?
In other words, if your input tape has a space followed by any string of any symbols at the end, then it will also be accepted. You could think of this as working very similar to how end-of-line comments work in many programming languages. Here, instead of the typical // delimiter for comments, it just uses a single _ (space-symbol).
[This explains why I suggested the equivalent with the final 1* inside the first optional group, since the structure of the regular expression better matches the structure of the Turing machine graph.]
The full language accepts both:
0110100111
but also the same string followed by a space-delimited 'comment':
0110100111_Hello, world!
Or, if the input alphabet is restricted to only 0, 1, and _, then you could write the comment in some binary (or ternary!) code like this one with a meaningless/random comment at the end:
0110100111_10101110101000__001_1
it recognizes {0^(2^n) | n ≥ 0}. in other words, strings of 0's whose lengths are powers of 2
@@dn6824 0^8 is not accepted isnt it?
@@dzbro1194 yes it does. try running thru the state machine for n=3, or in other words 00000000 like you mentioned
@@dn6824
idk i tried doing it multiple times and i keep getting stuck with X as input on q3 with no possible transitions.
$00000000u
$u0000000u
$uX000000u
$uX000000u
$uX0X0000u
$uX0X0000u
$uX0X0X00u
$uX0X0X0Xu
$uX0X0X0Xu
...
$uX0X0X0Xu ; u -> R
$uX0X0X0Xu ; X -> R
$uXXX0X0Xu ; 0 -> X, R
$uXXX0X0Xu ; X -> R
$uXXX0X0Xu ; 0 -> R
then we have X on q3 and no possible transitions.
pls tell me if you see what im doing wrong.
So I think the language describes all strings composed as 0{00,x}*
I guess the machine computes strings with just one zero or even no. of zeroes
Nope. Doesn't accept 6 or more 0s either.
it recognizes {0^(2^n) | n ≥ 0}. in other words, strings of 0's whose lengths are powers of 2
Just wanted to say great videos, but could you please change the starting music..
this made no sense at all
what degree teaches that stuff? because that's the path I want to follow(the math, theoretical aspect of cs)
I'm on Computer Science and I study this stuff, maybe go to that or mathematics