Savitchin lause (1970):
NSPACE (f(n)) ⊆ DSPACE (f²(n)).Eli jos ei-deterministinen Turingin kone voi ratkaista ongelman käyttämällä f ( n ) muistia, niin deterministinen Turingin kone voi tehdä sen muistin neliölle.
| Todiste: |
| Harkitse Turingin konetta, jossa on tulo ja työnauha. Sen konfiguraatio voidaan koodata seuraavasti: koodaa työnauhan sijainti ja sisältö (vie muistin), syöttönauhan sijainti (vie muistin). Siitä lähtien kokoonpanon koko on .
Päästää . Sitten on ei-deterministinen Turingin kone, joka tunnistaa tämän kielen. Harkitse aputoimintoa, joka laskee mahdollisuuden siirtyä kokoonpanosta konfiguraatioon enintään siirtymissä: Tavoittavuus (I, J, k): jos (k = 0) palautus (IJ) tai (I = J) // tietue (IJ) tarkoittaa mahdollisuutta siirtää MT konfiguraatiosta I kokoonpanoon J yhdessä vaiheessa else for (Y) // luettele välikokoonpanot, jos Reach(I, Y, k-1) ja Reach(Y, J, k-1) palauttavat tosi return falseTällä toiminnolla on rekursion syvyys, jokaisella rekursiotasolla se käyttää muistia nykyisten konfiguraatioiden tallentamiseen. Harkitse Turingin konetta, joka tunnistaa kielen. Tällä koneella voi olla kokoonpanoja. Tämä selitetään seuraavasti. Olkoon siinä nauhaaakkosten tilat ja symbolit. Erilaisten viivojen määrä, jotka voivat näkyä työnauhalla. Syöttönauhan pää voi olla yhdessä asennoista ja yhdessä työnauhasta. Siten kaikkien mahdollisten kokoonpanojen kokonaismäärä ei ylitä . Tarkastellaan funktiota, joka tietyllä sanalla tarkistaa, kuuluuko se kieleen: Tarkista (x, L): ( T) // toista hyväksyviä tiloja sisältävien kokoonpanojen yli, jos Reach(S, T, ) palauttaa tosi return falseJos sana kuuluu kieleen, se hyväksytään, koska kaikki mahdolliset pääsyreitit otetaan huomioon. Tämä saadaan funktiolle meille määritetystä rekursiosta. Ja jos sanaa ei sallita per askel (kaikkien mahdollisten kokoonpanojen lukumäärä), se on taatusti kielletty. Tämän seurauksena funktiolla on rekursion syvyys , jokaisella rekursiotasolla käytetään muistia. Sitten kaikki tämä toiminto käyttää muistia. |