Linjär hastighetssats

I beräkningskomplexitetsteorin säger det linjära speedup-satsen för Turing-maskiner att givet valfri reell c > 0 och vilken turingmaskin som helst som löser ett problem i tiden f ( n ), så finns det en annan k -bandmaskin som löser samma problem i tid högst f ( n )/ c + 2 n + 3 , där k > 1. Om den ursprungliga maskinen är icke-deterministisk , är den nya maskinen också icke-deterministisk. Konstanterna 2 och 3 i 2 n + 3 kan till exempel sänkas till n + 2.

Bevis

Konstruktionen är baserad på att packa flera tejpsymboler för originalmaskinen M i en tejpsymbol för den nya maskinen N . Det har en liknande effekt som att använda längre ord och kommandon i processorer: det påskyndar beräkningarna men ökar maskinens storlek. Hur många gamla symboler som är packade i en ny symbol beror på önskad hastighet.

Anta att den nya maskinen packar tre gamla symboler till en ny symbol. Då är alfabetet för den nya maskinen $\Sigma \cup \Sigma ^{3}$ : det består av de ursprungliga symbolerna och de packade symbolerna. Den nya maskinen har samma antal k > 1 band. Ett tillstånd av N består av följande komponenter:

tillståndet M ;
för varje band, tre packade symboler som beskriver den packade symbolen under huvudet, den packade symbolen till vänster och den packade symbolen till höger; och
för varje band, den ursprungliga huvudpositionen inom den packade symbolen under huvudet på N .

Den nya maskinen N börjar med att koda den givna ingången till ett nytt alfabet (det är därför dess alfabet måste inkludera ${\displaystyle \Sigma } )$ . Till exempel, om ingången till 2-tape M är till vänster, är bandkonfigurationen av N till höger efter kodningen:

[ #

_

a

b

a

b

a

_

...]

[ #

(_,_,_)

...]

[ #

_

...]

[ #

(_,a,b)

(b,a,b)

(b,a,_)

...]

Den nya maskinen packar tre gamla symboler (t.ex. den tomma symbolen _ , symbolen a och symbolen b ) till en ny symbol (här (_, a , b )) och kopierar den till det andra bandet, samtidigt som det första bandet raderas . I slutet av initieringen riktar den nya maskinen huvudet till början. Sammantaget tar detta 2 n + 3 steg.

Efter initieringen är tillståndet för N ${\displaystyle (q_{0} ;~~~?,(\_,\_,\_),?;~~~?,(\_,a,b),?;~~~[1,1])} ,$ där symbolen $?$ betyder att den kommer att fyllas i av maskinen senare; symbolen $[1,1]$ betyder att huvudet på originalmaskinen pekar på de första symbolerna inuti $(\_,\_,\_)$ och $(\_,a,b)$ . Nu börjar maskinen simulera m = 3 övergångar av M med sex av sina egna övergångar (i detta konkreta fall kommer det inte att ske någon hastighet, men i allmänhet kan m vara mycket större än sex). Låt konfigurationerna för M och N vara:

[ #

_

b

a

b

a

_

...]

[ #

(_,a,b)

(b,a,b)

( b ,_,_)

...]

[ #

_

a

b

a

b

_

...]

[ #

(_,_, b )

(b,a,b)

(b,a,_)

...]

där de feta symbolerna indikerar huvudets position. Tillståndet för N är $(q;~~~?,( \_,\_,b),?;~~~?,(b,\_,\_),?;~~~[3,1])$ . Nu händer följande:

N flyttar höger, vänster, vänster, höger. Efter de fyra dragen har maskinen N alla sina $?$ fylls och dess tillstånd blir $(q;~~~\#,(\_,\_,b),(b,a,b);~~~(b,a, b),(b,\_,\_),(\_,\_,\_);~~~[3,1])$
Nu uppdaterar N sina symboler och tillstånd enligt m = 3 övergångar av originalmaskinen. Detta kan kräva två drag (uppdatera den aktuella symbolen och uppdatera en av dess intilliggande symboler). Anta att den ursprungliga maskinen rör sig enligt följande (med motsvarande konfiguration av N till höger):

[ #

_

b

a

_

...]

[ #

(_,a,b)

( b ,_,_)

(_,_,_)

...]

[ #

_

a

b

_

...]

[ #

(_,_,_)

(_,_, b )

(b,a,_)

...]

blir tillståndet för N $(q';~~ ~?,(\_,\_,b),?;~~~?,(b,\_,\_),?;~~~[3,1])$ .

Komplexitet

Initiering kräver 2 n + 3 steg. I simuleringen simulerar 6 steg av N m steg av M . Om du väljer m > 6 c produceras körtiden som begränsas av $f(n)/c+2n+3.$