[RIP to Walter Savitch, who passed away earlier this year.]

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. The unedited version of this video is here:    • Theory of Computation: Savitch's Theo...  

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    • Turing Machines - what are they? + Fo...   for more details.

Timeline:
0:00 - Intro
0:58 - Brute-force simulation
4:00 - Analysis of brute-force space
5:40 - Idea to re-use space
8:40 - The CANYIELD function
13:30 - Recursive cases
21:20 - Analysis of total space needed

Easy Theory Website: https://www.easytheory.org
Become a member:    / @easytheory  
Donation (appears on streams): https://streamlabs.com/easytheory1/tip
Paypal: https://paypal.me/easytheory
Patreon:   / easytheory  
Discord:   / discord  

Youtube Live Streaming (Sundays) - subscribe for when these occur.

Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierar...
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-f...

If you like this content, please consider subscribing to my channel:    / @easytheory  

▶SEND ME THEORY QUESTIONS◀
[email protected]

▶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.