Teorema lui Savitch

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 24 aprilie 2021; verificarea necesită 1 editare .

Teorema lui Savitch (1970):

NSPACE (f(n)) ⊆ DSPACE (f²(n)).

Adică, dacă o mașină Turing nedeterministă poate rezolva o problemă folosind memoria f ( n ), atunci o mașină Turing deterministă o poate face pentru pătratul memoriei.

Consecințele

Aplicație practică

Dovada:
Luați în considerare o mașină Turing cu o intrare și o bandă de lucru. Configurația sa poate fi codificată după cum urmează: codifică poziția și conținutul benzii de lucru (ocupă memorie), poziția benzii de intrare (ocupă memorie). Din moment ce , atunci dimensiunea configurației va fi .

Lăsa . Apoi există o mașină Turing nedeterministă care recunoaște acest limbaj.

Luați în considerare o funcție auxiliară care calculează posibilitatea trecerii de la configurație la configurare în nu mai mult de tranziții:

Atinge (I, J, k): dacă (k = 0) întoarcere (IJ) sau (I = J) // înregistrare (IJ) înseamnă capacitatea de a muta MT de la configurația I la configurația J într-un singur pas else pentru (Y) // enumeră configurațiile intermediare dacă Reach(I, Y, k-1) și Reach(Y, J, k-1) returnează true return false

Această funcție are o adâncime de recursivitate, la fiecare nivel de recursivitate folosește memoria pentru a stoca configurațiile curente.

Luați în considerare o mașină Turing care recunoaște o limbă. Această mașină poate avea configurații. Acest lucru este explicat după cum urmează. Lasă-l să aibă stări și simboluri ale alfabetului benzii. Numărul de linii diferite care pot apărea pe banda de lucru. Capul de pe banda de intrare poate fi într-una din poziții și într-una din banda de lucru. Astfel, numărul total al tuturor configurațiilor posibile nu depășește .

Luați în considerare o funcție care, dat un cuvânt dat, verifică dacă acesta aparține limbajului:

Verificați (x, L): pentru (T) // repetare peste configurații care conțin stări de acceptare dacă Reach(S, T, ) returnează adevărat return false

Dacă cuvântul aparține limbii, atunci va fi admis, deoarece vor fi luate în considerare toate căile posibile de admitere. Acest lucru este oferit de adâncimea de recursivitate specificată pentru noi pentru funcție. Și dacă un cuvânt nu este permis pe pas (numărul tuturor configurațiilor posibile), atunci este garantat că nu va fi permis. Ca urmare, funcția are o adâncime de recursivitate, la fiecare nivel de recursivitate este utilizată memoria. Apoi toată această funcție folosește memoria.

Literatură