Twierdzenie o prędkości liniowej

W teorii złożoności obliczeniowej twierdzenie o liniowym przyspieszeniu dla maszyn Turinga stwierdza, że ​​przy dowolnym rzeczywistym c > 0 i dowolnej maszynie Turinga z taśmą k rozwiązującej problem w czasie f ( n ), istnieje inna maszyna z taśmą k , która rozwiązuje ten sam problem w czas co najwyżej f ( n )/ c + 2 n + 3 , gdzie k > 1. Jeśli pierwotna maszyna jest niedeterministyczna , to nowa maszyna jest również niedeterministyczna. Stałe 2 i 3 w 2 n + 3 można obniżyć na przykład do n + 2.

Dowód

Konstrukcja polega na spakowaniu kilku symboli taśmowych pierwotnej maszyny M w jeden symbol taśmowy nowej maszyny N . Ma to podobny efekt jak używanie dłuższych słów i poleceń w procesorach: przyspiesza obliczenia, ale zwiększa rozmiar maszyny. To, ile starych symboli zostanie umieszczonych w nowym symbolu, zależy od pożądanego przyspieszenia.

Załóżmy, że nowa maszyna pakuje trzy stare symbole w nowy symbol. Wtedy $: składa się z$ nowej maszyny to symboli i spakowanych Nowa maszyna ma taką samą liczbę k > 1 taśm. Stan N składa się z następujących elementów:

• stan M ;
• dla każdej taśmy trzy upakowane symbole, które opisują upakowany symbol pod nagłówkiem, upakowany symbol po lewej stronie i upakowany symbol po prawej stronie; I
• dla każdej taśmy, oryginalne położenie głowicy w symbolu opakowania pod nagłówkiem N .

Nowa maszyna N rozpoczyna się od zakodowania danych wejściowych do nowego alfabetu (dlatego jej alfabet musi zawierać ${\ displaystyle \ Sigma}$ ). Na przykład, jeśli wejście do 2-taśmowego M znajduje się po lewej stronie, to po zakodowaniu konfiguracja taśmy N znajduje się po prawej stronie:

[#

_

A

B

B

A

B

B

A

_

...]

[#

(_,_,_)

(_,_,_)

(_,_,_)

...]

[#

_

_

_

_

_

_

_

_

_

...]

[#

(_,a,b)

(b, a, b)

(b,a,_)

...]

Nowa maszyna pakuje trzy stare symbole (np. pusty symbol _ , symbol a i symbol b ) w nowy symbol (tutaj (_, a , b )) i kopiuje go na drugiej taśmie, kasując pierwszą taśmę . Pod koniec inicjalizacji nowa maszyna kieruje głowę na początek. Ogólnie wymaga to 2 n + 3 kroków.

Po inicjalizacji stan N to ${\ Displaystyle (q_ {0} ;~~~?,(\_,\_,\_),?;~~~?,(\_,a,b),?;~~~[1,1])} ,$ gdzie symbol ${\ styl wyświetlania?}$ oznacza, że ​​zostanie on później uzupełniony przez maszynę; symbol oznacza, że ​​​​głowica oryginalnej maszyny wskazuje na pierwsze symbole wewnątrz $) }$$\$ i ${\ Displaystyle (\ _, a, b)}$ . Teraz maszyna zaczyna symulować m = 3 przejścia M używając sześciu własnych przejść (w tym konkretnym przypadku nie będzie przyspieszenia, ale generalnie m może być znacznie większe niż sześć). Niech konfiguracje M i N będą:

[#

_

_

B

B

A

B

B

A

_

...]

[#

(_,a,b)

(b, a, b)

( b ,_, _)

...]

[#

_

A

B

B

A

B

B

_

_

...]

[#

(_,_, b )

(b, a, b)

(b,a,_)

...]

gdzie pogrubione symbole wskazują pozycję głowy. Stan N to ${\ Displaystyle (q; ~~~?, ( \_,\_,b),?;~~~?,(b,\_,\_),?;~~~[3,1])}$ . Teraz dzieje się co następuje:

• N porusza się w prawo, w lewo, w lewo, w prawo. Po czterech ruchach maszyna N ma wszystkie swoje ${\ Displaystyle?}$ wypełniony, a jego stan staje się ${\ Displaystyle (q; ~~~ \ #, (\ _, \ _, b), (b, a, b); ~~~ (b, a, b), (b, \_,\_),(\_,\_,\_);~~~[3,1])}$
• Teraz N aktualizuje swoje symbole i stan zgodnie z m = 3 przejściami oryginalnej maszyny. Może to wymagać dwóch ruchów (zaktualizuj bieżący symbol i zaktualizuj jeden z sąsiednich symboli). Załóżmy, że oryginalna maszyna porusza się w następujący sposób (z odpowiednią konfiguracją N po prawej):

[#

_

_

_

_

_

B

B

A

_

...]

[#

(_,a,b)

( b ,_,_)

(_,_,_)

...]

[#

_

A

B

B

_

_

_

_

_

...]

[#

(_,_,_)

(_,_, b )

(b,a,_)

...]

Zatem stan N staje się ${\ Displaystyle (q'; ~~ ~?,(\_,\_,b),?;~~~?,(b,\_,\_),?;~~~[3,1])}$ .

Złożoność

Inicjalizacja wymaga 2 n + 3 kroków. W symulacji 6 kroków N symuluje m kroków M . Wybór m > 6 do daje czas działania ograniczony przez ${\ Displaystyle f (n) / c + 2n + 3.}$