Nondeterministisk Turing-maskine

En ikke-deterministisk Turing-maskine (NMT)  er en Turing-maskine, hvis overgangsfunktion er en ikke- deterministisk uendelig automat .

Enhed

En deterministisk (almindelig, klassisk) Turing-maskine har en overgangsfunktion, der ved kombinationen af ​​den aktuelle tilstand og tegnet på båndet bestemmer tre elementer: det tegn, der vil blive skrevet til båndet, den retning, hovedet vil bevæge sig langs. båndet og tilstandsmaskinens nye tilstand. For eksempel Xpå et bånd 3definerer tilstanden entydigt en overgang til tilstanden 4, skriver et tegn til båndet Yog flytter hovedet en position til venstre.

I tilfælde af en ikke-deterministisk Turing-maskine kan kombinationen af ​​automatens aktuelle tilstand og symbolet på båndet tillade flere overgange til de næste tilstande samtidigt parallelt. For eksempel Xpå bånd og tilstand 3tillader den både en tilstand 4med et tegn skrevet til bånd Yog et hovedskift til højre og en tilstand 5med et tegn skrevet til bånd Zog et hovedskift til venstre. En ikke-afledt Turing-maskine kan således være i mange stater på samme tid.

I modsætning til en deterministisk Turing-maskine, som har en enkelt "beregningssti", har den ikke-deterministiske version et "beregningstræ" (generelt et eksponentielt antal stier). En ikke-deterministisk Turing-maskine siges at acceptere input, hvis en gren af ​​træet stopper i en accepterende tilstand, ellers accepterer HMT ikke input. (Svarene "ja" og "nej" i tilfælde af ikke-deterministiske beregninger er således ikke symmetriske.)

Definition

Formelt defineres en ikke-deterministisk Turing-maskine som et ordnet seks elementer i nogle sæt: , hvor:

•  er et begrænset sæt af tilstande
•  — begrænset sæt af tegn (båndalfabet)
•  - udgangstilstand
•  - mellemrum ( )
•  er et begrænset sæt af accepterende tilstande
•  er en kortlægning med flere værdier fra et tilstand-symbol-par, kaldet overgangsfunktionen.

Ækvivalens med en deterministisk Turing-maskine

På trods af den tilsyneladende større kraft af ikke-deterministiske maskiner på grund af det faktum, at de udfører flere mulige beregninger på én gang (kræver kun, at mindst én af dem ender i en accepterende tilstand), ethvert sprog, der er tilladt af en ikke-deterministisk Turing-maskine er også tilladt af en almindelig deterministisk Turing-maskine, fordi den kan simulere enhver ikke-deterministisk overgang og lave flere kopier af tilstanden, hvis der opstår en tvetydighed.

Modellering af ikke-determinisme kræver meget mere tid, spørgsmålet om at estimere omkostningsforskellen er åbent: i det særlige tilfælde med en tidsgrænse i form af et polynomium af længden af ​​input, er dette spørgsmål det klassiske problem " P = NP ".

Klassen af ​​algoritmer , der kører i polynomiel tid på ikke-deterministiske Turing-maskiner, kaldes NP-klassen .

Eksempel

Overvej problemet med at kontrollere, at et givet b - bit heltal N ( 2b -1 ≤N< 2b ) er sammensat . Så er b  længden af ​​inputdataene, i forhold til hvilken beregningstiden tages i betragtning . Svaret "JA" er et sammensat tal, og "NEJ" er et primtal . Denne opgave er komplementær til primalitetstesten .

En ikke-deterministisk algoritme til denne opgave kan for eksempel være følgende:

• Vælg et ikke-deterministisk heltal m , således at 1<m<N .
• Divider N med m , lad os betegne resten med a .
• Hvis a=0 giv svaret "JA" ( så er m en divisor af N ), ellers giv svaret "NEJ".

(Algoritmen er ikke skrevet direkte som en definition af en Turing-maskine.)

I beregningstiden for denne algoritme er den definerende del divisionstiden, hvilket kan udføres i O (b 2 ) trin, som er polynomisk tid . Så opgaven er i NP-klassen .

For at implementere en sådan beregningstid er det nødvendigt at vælge tallet m med succes eller udføre beregninger langs alle mulige stier (for alle mulige m ) samtidigt på mange kopier af maskinen.

Hvis du simulerer denne algoritme på en deterministisk Turing-maskine, og prøver alle mulige muligheder efter tur, skal du kontrollere N-2=O( 2b ) -grene. Den samlede beregningstid vil således være O(b 2 2 b ) trin, som allerede er eksponentiel tid , som er væsentlig længere end polynomiel tid. Denne algoritme falder således ikke ind i klassen P . (Men andre, hurtigere algoritmer til dette problem kan anvendes, der kører i polynomiel tid, og dermed falder problemet i klasse P.)

Litteratur

• John Hopcroft, Rajeev Motwani, Jeffrey Ullman. Introduktion til automatteori, sprog og beregning. - M . : "Williams" , 2002. - 528 s. - ISBN 0-201-44124-1 .
• Karpov Yu. G. Teori om automater. - Peter, 2003. - ISBN 5-318-00537-3 .