Here we show how to create a CFG for the language (0 U 1)*. Easy Theory Website: https://www.easytheory.org Discord: https://discord.gg/SD4U3hs If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1 ▶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. ... https://www.youtube.com/watch?v=xFxtsgNouI4

Here we show that the problem of determining whether an arbitrary Turing Machine moves left three times in a row is undecidable, but checking if such a machine moves left *at all* IS decidable! There is a very fine line between decidable and undecidable here. The trick with the decidable part is to run the machine "long enough" before you know that it will never move left; and for the undecidable part, encoding each transition to always interject a Right move and then a Left move, and force 3 lefts in a row at the end. (Update: it IS decidable to check if the Turing Machine moves left TWICE in a row; try to prove why this is.) Thanks to the following supporters of the channel for helping support this video. If you want to contribute, links are below. Names are listed in alphabetical order by surname. Platinum: Micah Wood Silver: Josh Hibschman, Timmy Gy, Patrik Keinonen, Travis Schnider, and Tao Su Timeline: 0:00 - Intro 1:45 - Moving Left At Least Once is Decidable 5:06 - Moving Left 3 Times in a Row is Undecidable Easy Theory Website: https://www.easytheory.org Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join Donation (appears on streams): https://streamlabs.com/easytheory1/tip Paypal: https://paypal.me/easytheory Patreon: https://www.patreon.com/easytheory Discord: https://discord.gg/SD4U3hs Youtube Live Streaming (Sundays) - subscribe for when these occur. Merch: Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122 Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1 ▶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. ... https://www.youtube.com/watch?v=64b_O8ryoNA

Easy Theory Website: https://www.easytheory.org Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join Donation (appears on streams): https://streamlabs.com/easytheory1/tip Paypal: https://paypal.me/easytheory Patreon: https://www.patreon.com/easytheory Discord: https://discord.gg/SD4U3hs #easytheory #gate #theory Youtube Live Streaming (Sundays) - subscribe for when these occur. Social Media: Facebook Page: https://www.facebook.com/easytheory/ Facebook group: https://www.facebook.com/groups/easytheory/ Twitter: https://twitter.com/EasyTheory Merch: Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122 Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1 Gold Supporters: Micah Wood Silver Supporters: Timmy Gy ▶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. ... https://www.youtube.com/watch?v=KkiVE49i-Kw

Here we look at Tom Scott's "sorting algorithms and big-O notation" video and assess its accuracy, as well as give some additional insight. His video is here: https://www.youtube.com/watch?v=RGuJga2Gl_k&ab_channel=TomScott. He goes over algorithms to sort items, and why certain algorithms are "slower" than others in a certain sense. The algorithms he mentions are: bubble sort, insertion sort, quicksort, and bogosort (like, why even?), and gives animations to each. I mention several (more esoteric) others. Big-O is important, but only gives a "mostly true" picture of how algorithms behave compared to each other. Thanks to the following supporters of the channel for helping support this video. If you want to contribute, links are below. Names are listed in alphabetical order by surname. Platinum: Micah Wood Silver: Timmy Gy, Josh Hibschman, Patrik Keinonen, Travis Schnider, and Tao Su -------------------------------------------------------------------------------------------------------------- If you need help, here are some relevant links: Big-O: https://www.youtube.com/watch?v=rP5peOkXsbY&ab_channel=EasyTheory Algorithms Playlist: https://www.youtube.com/watch?v=sT3ImMy0fRE&list=PLylTVsqZiRXNArM--1hbcrlJyZn7EpNJU&index=1&ab_channel=EasyTheory -------------------------------------------------------------------------------------------------------------- Easy Theory Website: https://www.easytheory.org Become a member: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join Donation (appears on streams): https://streamlabs.com/easytheory1/tip Paypal: https://paypal.me/easytheory Patreon: https://www.patreon.com/easytheory Discord: https://discord.gg/SD4U3hs Youtube Live Streaming (Sundays) - subscribe for when these occur. Merch: Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122 Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1 ▶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. ... https://www.youtube.com/watch?v=YvBw_M6Dboc