Відео

Question: does the word w=0^n1^n have 2n characters? like n zeros and n ones?

thank you very much!!:))))))))))))

can any one explain is subsequence is regular as it still accepts bbb which is not a subsequence

@Easy Theory Excuse me Sir, why |Y| >=1 ?? It must be greater than 0 according to the pumping lemma condition that is |Y|>0

very shitty video lmao

This problem is solved this year 🎉

Why do you sound like you’re about to cry

You motivated me enough to learn for my toc examn despite me having difficulties trying to get an edge over everything in this subject, maybe im just too foolish on myself, but never did I stop, I always come back to toc and learn from it despite me having said that I do not like the subject since it has no "real application" but you and your channel proved me wrong and gave me a total different view of things. Thank you alot

I guess what happens is that, e.g. if x=<M, w> is a turing machine that accepts w in 2 steps, L' is the language after applying h to L, then x<1> is NOT in the language but x<2> is However, h(x<1>) = h(x<2>) = x. By definition, x is in L' So, the only way for x to be in L' is if, for some n, x<n> is in L But, that would be solving the halting problem so L' is not decidable

Thanks for this. I rlly needed to watch this to get motivation to push through my theory of computation class.

I'm in bed in a room and for the infinite time that night I am being moved to another room. Guess there may be an infinite number of rooms but there is no sleep for any of the infinite number of guests.

Your machine recognize this language: {w contains an equal number of a's, b's and c's} not this {a^nb^nc^n: n≥0}

Brilliant !

36:55 could we just choose one condition and ignore the other?

Thank you!

You can explain really well

19:30 Where can I find a video for that algorithm?

It's the faults and flaws in your videos that make them so authentically human. We have all been craving for that authenticity in this fake-AI-yotube era. And real learning also happens when you have that human authenticity. Too much polishing might be a danger for that authenticity. Please be cautious. PS: I stopped watching 3Blue1Brown because of that polish. 3Blue1Brown is an amazing channel and the person has done tremendously great educational work and authentic work. But, a lot of people, also recently realized that because his videos are so smooth and easy to understand that you just don't retain or learn anything. Real learning happens when you experience some difficulty.

2:20 : that right there is the experience towards Physics I too have shared. Only you and Feynman have ever described this experience in such a beautiful manner.

Thanks that was very interresting thanks

Nice and easy explanation

Does anyone know what he means or the author of which discrete book. I hear sickser?

In the final factorial proof, I think there is a slight error for the case where p = 1 (which is allowed by the lemma). In that case, the final inequality p!+p < (p+1)! does not hold since 1!+1 = 2!. I think the solution to this issue is shown in the previous where you just used a longer w string. Something like w = 0^(p+1)! could be used instead.

10:53 doesnt q5 go when on a to q2 and q3 ?

GOD

When reducing inputs/outputs, how does the multiplexing work if the inputs are different lengths? Can you still extract them out from the combined string?

I love how you edit it to condense it as much as possible. Great work and thank you :)

10:30 word

you sir are a person on par with Sipser himself, thank you so much ❤❤❤❤❤❤

i thought it was (0100110010)* and not (01∪011∪010)* 20 minutes wasted scratching my head. i also noticed that based on what he did the string 0101 is accepted if you take the path: {1,2}->0->{3}->1->{1,2,4}->0->{1,2,3,5}->1->{1,2,4} 0101 ends in {1,2,4} which is a final state.

don't know if your going to see this but i can't find any source that explains how part A is able to find the description of <B> to print. I am assuming its known beforehand as if it wasn't it would just be another scenerio of needing self reference of machine but how is it that we know <B>.

Thank you

i was reading my notes from my lecture on this topic and had a really tough time understanding it. this cleared things up for me perfectly. thanks sir, youre a life saver.

damn bro cs theory is crazy

This argument is improperly defined. lets define D(f) = ~H(f, "f"), take a moment to convince yourself this is equivalent to what was said in the video. If we walk through the execution pipeline, first D is called with argument f. Then H is called with arguments f and "f". Finally f is called with argument "f" and if it accepts we reject and vice versa. Now lets evaluate the alleged contradiction case: D(D) = ~H(D, "D"). Once again convince yourself of the validity of this notation. Here we can see the issue, an argument mismatch. In the execution pipeline D is called first with argument D, then H is called with arguments D and "D". Which calls D with argument "D" and the result is the opposite of that. I hope you can convince yourself from there of the fact that D(D) = ~D("D") is not actually a contradiction at all, that is if D(D) accepts, all that means is D("D") rejects.

Thanks for making this video. Too often people assume correct interpretation is easy and obvious, even though misunderstandings are common even in simple everyday contexts. I think it is really usefull to clear them up is by doing just what you have done: go over actual examples of missed distinctions, etc. If anything, we need more videos like this.

You're a god

why if x is in the form 0^n 1^n we accept?

Thank you sir it was very helpful for me ......

Question: In 2:05:11 you used the p! trick to prove that x and y can be different. Could you have used a string of this format: 0^p11^p0 (x terminates after the first 1) to prove that x an y can be of different length? I ask this because I understand that to prove that a string is not anymore in the language, in this case, proving that one of the two conditions fails is enough.

this is really well explained. i cant thank enough

I thank you a lot for this video. I am gonna take the exam on the 22th July of Theory of Computation and this helped me clear some doubts. Morevorer, I really like the way you get excited as soon you prove something cool. Thanks again!

why S is deleted from B in 12.33?

L={a^(n) | n is a prime number} x=a^(m-1),y=a^1,z=a^(p-m+1-1). s= a^(m-1) a^1 a^(p-m+1-1)>=p =>s=a^(1)a(p-m) >=p. by the lemma rules the string s must be in the language therefor s must be in length of any prime number and therefor p could potentionally be of the length of that prime number. the lowest prime number is 2 so we can start by i=2 a^(2)a(p-m) =>[reminder: m>=1 because x=a^(m-1) and |x|>=0 so if m>=0 it means that could be x=a^(0-1) meaning |x|>=-1 and thats not possible so m must start from 1 therfore m>=1]=> a^(2)a(p-1)=>a^(p+1). since p could be a prime number as mentioned in the start, it could be that p=2 and then a^(p+1)=>a^(2+1)=>a^(3)=> 'a' is in the length of a prime number so the resulted string of i=2 is still in the language and that was not helping us because we look for a contradiction. i=7 s=a^(7)a(p-1) => a^(p+6)=>a^(2+6)=>a^(8)=>'a' in the length of 8 and 8 is not a prime number so we reached a contradiction and therefor L is irregular language.

Thank you soo much. Had to study this for finals and I was confused by my own notes. After many vids yours was the only one that answered all my confusions.