[RIP to Walter Savitch, who passed away earlier this year.] <br /><br />Here we prove Savitch's theorem, which is giving an upper bound on the amount of space needed to deterministically simulate a nondeterministic TM that itself runs in a certain amount of space. The naive solution is just to brute-force all combinations of choices, but this wastes a lot of space. Savitch's main idea was to reduce the amount of space by "guessing" a midpoint in the computation, and if one can reach the middle, and then from the middle to the end, then we return yes. We analyze the space needed, and only the square of the original NTM's space suffices.<br /><br />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 <a href="https://www.youtube.com/watch?v=j0bIxPqlYLE&ab_channel=EasyTheory" target="_blank" rel="nofollow">https://www.youtube.com/watch?v=j0bIxPqlYLE&ab_channel=EasyTheory</a> for more details.<br /><br />Timeline:<br />0:00 - Intro<br />0:58 - Brute-force simulation<br />4:00 - Analysis of brute-force space<br />5:40 - Idea to re-use space<br />8:40 - The CANYIELD function<br />13:30 - Recursive cases<br />21:20 - Analysis of total space needed<br /><br />Easy Theory Website: <a href="https://www.easytheory.org" target="_blank" rel="nofollow">https://www.easytheory.org</a><br />Become a member: <a href="https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join" target="_blank" rel="nofollow">https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg/join</a><br />Donation (appears on streams): <a href="https://streamlabs.com/easytheory1/tip" target="_blank" rel="nofollow">https://streamlabs.com/easytheory1/tip</a><br />Paypal: <a href="https://paypal.me/easytheory" target="_blank" rel="nofollow">https://paypal.me/easytheory</a><br />Patreon: <a href="https://www.patreon.com/easytheory" target="_blank" rel="nofollow">https://www.patreon.com/easytheory</a><br />Discord: <a href="https://discord.gg/SD4U3hs" target="_blank" rel="nofollow">https://discord.gg/SD4U3hs</a><br /><br />Youtube Live Streaming (Sundays) - subscribe for when these occur.<br /><br />Merch:<br />Language Hierarchy Apparel: <a href="https://teespring.com/language-hierarchy?pid=2&cid=2122" target="_blank" rel="nofollow">https://teespring.com/language-hierarchy?pid=2&cid=2122</a><br />Pumping Lemma Apparel: <a href="https://teespring.com/pumping-lemma-for-regular-lang" target="_blank" rel="nofollow">https://teespring.com/pumping-lemma-for-regular-lang</a><br /><br />If you like this content, please consider subscribing to my channel: <a href="https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1" target="_blank" rel="nofollow">https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1</a><br /><br />▶SEND ME THEORY QUESTIONS◀<br />[email protected]<br /><br />▶ABOUT ME◀<br />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.<br />...<br /><a href="https://www.youtube.com/watch?v=PNycvm8RgcU" target="_blank" rel="nofollow">https://www.youtube.com/watch?v=PNycvm8RgcU</a>