![Easy Theory](/img/default-banner.jpg)
- 420
- 3 325 274
Easy Theory
United States
Приєднався 2 бер 2020
This is a channel about making Computer Science theory as easy as possible.
Why This All Matters
Easy Theory Website: www.easytheory.org
If you like this content, please consider subscribing to my channel: ua-cam.com/channels/3VY6RTXegnoSD_q446oBdg.html
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about it. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
The views expressed in this video are not reflective of any of my current or former employers.
If you like this content, please consider subscribing to my channel: ua-cam.com/channels/3VY6RTXegnoSD_q446oBdg.html
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about it. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
The views expressed in this video are not reflective of any of my current or former employers.
Переглядів: 2 929
Відео
Planar Machines in Theory
Переглядів 6223 місяці тому
Here we consider "planar" machines in the undergraduate Theory of Computing class, and whether they are possible to be made, that is, a machine whose drawing does not have edge crossings. We prove that for regular languages, context-free languages, and Turing Machine languages, there is a corresponding "planar" machine. For example, every regular language has a planar NFA. CFG to PDA conversion...
Fourteen DFA Examples? No Problem!
Переглядів 8 тис.8 місяців тому
Here we solve Sipser problem 1.6, which involves 14 DFA (Deterministic Finite Automaton) problems. I give my strategies as well as ways for solving other problems. Timestamps: 0:00 - Intro 0:19 - DFA for binary strings beginning with 1, end with 0 3:02 - DFA for binary strings with at least three 1s 4:50 - DFA for binary strings that contain 0101 8:39 - DFA for binary strings with third symbol ...
An Update
Переглядів 6 тис.9 місяців тому
Thanks for supporting the channel and letting us hit 20k subscribers and over 2 million total views! If you like this content, please consider subscribing to my channel: ua-cam.com/channels/3VY6RTXegnoSD_q446oBdg.html ▶ABOUT ME◀ I am a professor of Computer Science, and am passionate about it. I have taught many courses at several different universities, including several sections of undergradu...
This CompSci Video was 100% written by ChatGPT
Переглядів 2,5 тис.Рік тому
ChatGPT can make this video instantly popular, right?...right? Easy Theory Website: www.easytheory.org Discord: discord.gg/SD4U3hs If you like this content, please consider subscribing to my channel: ua-cam.com/channels/3VY6RTXegnoSD_q446oBdg.html ▶ABOUT ME◀ I am a professor of Computer Science, and am passionate about it. I have taught many courses at several different universities, including ...
[April Fools] Exponential Lower Bounds for Circuit Families (P ≠ NP)
Переглядів 1,7 тис.Рік тому
Here we prove that P ≠ NP by giving an exponential lower bound for circuit families. If you like this content, please consider subscribing to my channel: ua-cam.com/channels/3VY6RTXegnoSD_q446oBdg.html ▶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 g...
Turning 30
Переглядів 4 тис.Рік тому
Here I give my thoughts about turning 30...yeah...and also some experiences in theory along the way. Timeline: 0:00 - Intro 0:16 - First Theory (Guest) Lecture 1:13 - Theory Recitations 1:58 - First Theory Talk 3:44 - First Conference Talk 5:33 - Dissertation Defense 6:31 - Outro If you like this content, please consider subscribing to my channel: ua-cam.com/channels/3VY6RTXegnoSD_q446oBdg.html...
wish me luck
Переглядів 2,9 тис.Рік тому
If you like this content, please consider subscribing to my channel: ua-cam.com/channels/3VY6RTXegnoSD_q446oBdg.html ▶ABOUT ME◀ I am a professor of Computer Science, and am passionate about it. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes. The views expressed in this video are not reflective of any of...
ChatGPT vs. Professor's Computer Science Exam
Переглядів 5 тис.Рік тому
Here we feed questions from a theoretical computer science exam I have given into ChatGPT, and analyze the output answers it gives. (Yes, ChatGPT generated this video description.) For those who may not be familiar, ChatGPT is a state-of-the-art natural language processing system that is capable of generating human-like responses to prompts and questions. In this experiment, we will be testing ...
I proved a math conjecture
Переглядів 2,6 тис.Рік тому
Original covering arrays video: ua-cam.com/video/m1j4OBs1wsY/v-deo.html&ab_channel=EasyTheory arXiv preprint: arxiv.org/pdf/2211.01209.pdf Here we discuss a recent proof of mine of a conjecture in my research area, which has to do with sizes of covering arrays. I first go over what the problem, which is determining the asymptotic sizes (# of rows) of covering arrays of "higher index", which is ...
How to Become a Professor in 6 Steps
Переглядів 1,4 тис.Рік тому
Here we go over the REALLY EASY process of how to become a professor. Timeline: 0:00 - Intro 0:35 - Step 1: Get a PhD 1:17 - Step 2: Starting an Application 1:37 - Step 2a: Teaching Statement 2:13 - Step 2b: Research Statement 2:59 - Step 2c: Letters of Recommendation 3:30 - Step 2d: What Website to Apply On 4:02 - Step 2e: Advice 5:19 - Step 3: Phone Interview 6:11 - Step 4: On-Campus Intervie...
a student tried to bribe me once
Переглядів 3,3 тис.Рік тому
Yeah, so that happened. *sigh* Easy Theory Website: www.easytheory.org Discord: discord.gg/SD4U3hs If you like this content, please consider subscribing to my channel: ua-cam.com/channels/3VY6RTXegnoSD_q446oBdg.html ▶ABOUT ME◀ I am a professor of Computer Science, and am passionate about it. I have taught many courses at several different universities, including several sections of undergraduat...
The REAL Reason why Math/Humanities aren't "Useless"
Переглядів 1,9 тис.Рік тому
Here we talk about why ALL classes in university are important, including math AND humanities. The reason is really simple: that we instructors want all of you to be critical thinkers in tackling any complex problem or situation in which you will ever find yourself. Easy Theory Website: www.easytheory.org Discord: discord.gg/SD4U3hs If you like this content, please consider subscribing to my ch...
Rice's Theorem Example: Emptiness for Turing Machines
Переглядів 2,8 тис.2 роки тому
Rice's Theorem Example: Emptiness for Turing Machines
Rice's Theorem (Undecidability): 5 Proofs and Examples
Переглядів 13 тис.2 роки тому
Rice's Theorem (Undecidability): 5 Proofs and Examples
Context-Free Grammar (CFG) Example: Non-Palindromes
Переглядів 2 тис.2 роки тому
Context-Free Grammar (CFG) Example: Non-Palindromes
Context-Free Grammar (CFG) Example: Nested Pairs
Переглядів 1 тис.2 роки тому
Context-Free Grammar (CFG) Example: Nested Pairs
Context-Free Grammar (CFG) Example: Complement of 0^n1^n2^n
Переглядів 5 тис.2 роки тому
Context-Free Grammar (CFG) Example: Complement of 0^n1^n2^n
Context-Free Grammar (CFG) Example: Equal Pairs
Переглядів 8312 роки тому
Context-Free Grammar (CFG) Example: Equal Pairs
Context-Free Grammar (CFG) Example: {a^i b^j c^k : i at most j+k}
Переглядів 5 тис.2 роки тому
Context-Free Grammar (CFG) Example: {a^i b^j c^k : i at most j k}
Context-Free Grammars (CFGs): 5 Intermediate Examples
Переглядів 22 тис.2 роки тому
Context-Free Grammars (CFGs): 5 Intermediate Examples
Context-Free Grammar (CFG) Example: (0 U 1)*
Переглядів 1,4 тис.2 роки тому
Context-Free Grammar (CFG) Example: (0 U 1)*
Context-Free Grammar (CFG) Example: 0*1*
Переглядів 2,7 тис.2 роки тому
Context-Free Grammar (CFG) Example: 0*1*
Context-Free Grammar (CFG) Example: {a^i b^j c^k : i != j}
Переглядів 14 тис.2 роки тому
Context-Free Grammar (CFG) Example: {a^i b^j c^k : i != j}
Context-Free Grammar (CFG) Example: Palindromes
Переглядів 7 тис.2 роки тому
Context-Free Grammar (CFG) Example: Palindromes
Context-Free Grammar (CFG) Example: Union/Concat/Star
Переглядів 4,2 тис.2 роки тому
Context-Free Grammar (CFG) Example: Union/Concat/Star
Context-Free Grammars (CFGs): 5 Easy Examples
Переглядів 44 тис.2 роки тому
Context-Free Grammars (CFGs): 5 Easy Examples
Context Free Grammar to Pushdown Automaton Conversion (CFG to PDA)
Переглядів 35 тис.2 роки тому
Context Free Grammar to Pushdown Automaton Conversion (CFG to PDA)
Horses and Colors (Induction False "Proof")
Переглядів 3 тис.2 роки тому
Horses and Colors (Induction False "Proof")
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 am guessing we have to encode additional details and the example was just a super simplified version? Thank you!
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.