Savitchs teorem (1970):
NSPACE (f(n)) ⊆ DSPACE (f²(n)).Det vill säga, om en icke-deterministisk Turing-maskin kan lösa ett problem med hjälp av f ( n )-minne, så kan en deterministisk Turing-maskin göra det för kvadraten av minne.
| Bevis: |
| Tänk på en Turing-maskin med en ingång och ett fungerande band. Dess konfiguration kan kodas enligt följande: koda positionen och innehållet på arbetsbandet (upptar minne), positionen för inmatningsbandet (tar upp minne). Sedan kommer storleken på konfigurationen att vara .
Låt . Sedan finns det en icke-deterministisk Turing-maskin som känner igen detta språk. Tänk på en hjälpfunktion som beräknar möjligheten för övergång från konfiguration till konfiguration i endast övergångar: Räckvidd (I, J, k): om (k = 0) retur (IJ) eller (I = J) // record (IJ) betyder möjligheten att flytta MT från konfiguration I till konfiguration J i ett steg annat för (Y) // räkna upp mellanliggande konfigurationer om Reach(I, Y, k-1) och Reach(Y, J, k-1) returnerar true return falseDenna funktion har ett rekursionsdjup, på varje nivå av rekursion använder minnet för att lagra aktuella konfigurationer. Tänk på en Turing-maskin som känner igen ett språk. Denna maskin kan ha konfigurationer. Detta förklaras enligt följande. Låt den ha tillstånd och symboler för bandalfabetet. Antalet olika linjer som kan förekomma på arbetsbandet. Huvudet på inmatningsbandet kan vara i en av positionerna och i en av arbetsbanden. Det totala antalet möjliga konfigurationer överstiger alltså inte . Betrakta en funktion som, givet ett givet ord, kontrollerar om det tillhör språket: Kontrollera (x, L): för (T) // iterera över konfigurationer som innehåller accepterande tillstånd om Reach(S, T, ) returnerar true return falseOm ordet tillhör språket, kommer det att tillåtas, eftersom alla möjliga vägar för antagning kommer att beaktas. Detta tillhandahålls av det rekursionsdjup som anges för oss för funktionen. Och om ett ord inte är tillåtet per steg (antalet av alla möjliga konfigurationer), så är det garanterat inte tillåtet. Som ett resultat har funktionen ett rekursionsdjup, på varje nivå av rekursionsminne används. Då använder all denna funktion minne. |