Savitchův teorém (1970):
NSPACE (f(n)) ⊆ DSPACE (f²(n)).To znamená, že pokud nedeterministický Turingův stroj dokáže vyřešit problém pomocí f ( n ) paměti, pak deterministický Turingův stroj to dokáže pro druhou mocninu paměti.
| Důkaz: |
| Uvažujme Turingův stroj se vstupem a pracovní páskou. Jeho konfiguraci lze zakódovat následovně: zakódujte polohu a obsah pracovní pásky (zabírá paměť), polohu vstupní pásky (zabírá paměť). Od , pak velikost konfigurace bude .
Nechte Pak je tu nedeterministický Turingův stroj, který tento jazyk rozpozná. Zvažte pomocnou funkci, která vypočítá možnost přechodu z konfigurace do konfigurace pouze za přechody: Reach (I, J, k): if (k = 0) return (IJ) or (I = J) // záznam (IJ) znamená možnost přesunout MT z konfigurace I do konfigurace J v jednom kroku else for (Y) // vyjmenujte mezilehlé konfigurace , pokud Reach(I, Y, k-1) a Reach(Y, J, k-1) vrátí true return falseTato funkce má hloubku rekurze, na každé úrovni rekurze využívá paměť k ukládání aktuálních konfigurací. Představte si Turingův stroj, který rozpoznává jazyk. Tento stroj může mít konfigurace. To je vysvětleno následovně. Ať má stavy a symboly páskové abecedy. Počet různých řádků, které se mohou objevit na pracovní pásce. Hlava na vstupní pásce může být v jedné z poloh a v jedné z pracovních pásek. Celkový počet všech možných konfigurací tedy nepřesahuje . Uvažujme funkci, která při daném slovu kontroluje, zda patří do jazyka: Zkontrolujte (x, L): pro (T) // iterujte přes konfigurace, které obsahují přijímací stavy , pokud Reach(S, T, ) vrátí true return falsePokud slovo patří do jazyka, bude přijato, protože budou zváženy všechny možné cesty přijetí. To zajišťuje hloubka rekurze, která nám byla pro funkci zadána. A pokud slovo není povoleno na krok (počet všech možných konfigurací), pak je zaručeno, že nebude povoleno. Výsledkem je, že funkce má hloubku rekurze , na každé úrovni se používá rekurzní paměť. Pak veškerá tato funkce využívá paměť. |