Icketerministisk Turingmaskin

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 8 januari 2022; kontroller kräver 5 redigeringar .

En icke-deterministisk Turing-maskin (NMT)  är en Turing-maskin vars övergångsfunktion är en icke- deterministisk oändlig automat .

Enhet

En deterministisk (vanlig, klassisk) Turing-maskin har en övergångsfunktion som, genom kombinationen av det aktuella tillståndet och tecknet på bandet, bestämmer tre element: karaktären som kommer att skrivas till bandet, riktningen huvudet kommer att röra sig längs med bandet och det nya tillståndet för tillståndsmaskinen. Till exempel, Xpå ett band, 3definierar tillståndet unikt en övergång till tillståndet 4, skriver ett tecken till bandet Yoch flyttar huvudet en position åt vänster.

I fallet med en icke-deterministisk Turing-maskin kan kombinationen av automatens nuvarande tillstånd och symbolen på bandet tillåta flera övergångar till nästa tillstånd samtidigt parallellt. Till exempel, Xpå band och tillstånd, 3tillåter det både ett tillstånd 4med ett tecken skrivet till band Yoch ett huvudskifte till höger, och ett tillstånd 5med ett tecken skrivet till band Zoch en huvudförskjutning till vänster. Således kan en icke-härledd Turing-maskin vara i många stater samtidigt.

Till skillnad från en deterministisk Turing-maskin, som har en enda "beräkningsväg", har den icke-deterministiska versionen ett "beräkningsträd" (i allmänhet ett exponentiellt antal vägar). En icke-deterministisk Turing-maskin sägs acceptera inmatning om någon gren av trädet stannar i ett accepterande tillstånd, annars accepterar inte HMT inmatning. (Svaren "ja" och "nej" i fallet med icke-deterministiska beräkningar är alltså inte symmetriska.)

Definition

Formellt definieras en icke-deterministisk Turing-maskin som en ordnad sex element i vissa uppsättningar: , där:

Ekvivalens med en deterministisk Turing-maskin

Trots den till synes större kraften hos icke-deterministiska maskiner på grund av det faktum att de utför flera möjliga beräkningar samtidigt (vilket bara kräver att minst en av dem slutar i ett accepterande tillstånd), vilket språk som helst som tillåts av en icke-deterministisk Turing-maskin är också tillåtet av en vanlig deterministisk Turing-maskin eftersom den kan simulera vilken icke-deterministisk övergång som helst och göra flera kopior av tillståndet om en tvetydighet uppstår.

Modellering av icke-determinism kräver mycket mer tid, frågan om att uppskatta kostnadsskillnaden är öppen: i det speciella fallet med en tidsgräns i form av ett polynom av längden på ingången, är denna fråga det klassiska problemet " P = NP ".

Klassen av algoritmer som körs i polynomtid på icke-deterministiska Turing-maskiner kallas NP-klassen .

Exempel

Betrakta problemet med att kontrollera att ett givet b -bits heltal N ( 2b -1 ≤N<2b ) är sammansatt . Då är b  längden på indata, i förhållande till vilken beräkningstiden beaktas . Svaret "JA" är ett sammansatt tal och "NEJ" är ett primtal . Denna uppgift är ett komplement till primalitetstestet .

En icke-deterministisk algoritm för denna uppgift kan till exempel vara följande:

(Algoritmen är inte skriven direkt som en definition av en Turing-maskin.)

I beräkningstiden för denna algoritm är den definierande delen delningstiden, vilket kan göras i O (b 2 ) steg, vilket är polynomtid . Så uppgiften är i NP-klassen .

För att implementera en sådan beräkningstid är det nödvändigt att välja antalet m framgångsrikt eller utföra beräkningar längs alla möjliga vägar (för alla möjliga m ) samtidigt på många kopior av maskinen.

Om du simulerar denna algoritm på en deterministisk Turing-maskin och provar alla möjliga alternativ i tur och ordning, måste du kontrollera N-2=O(2 b ) grenar. Således kommer den totala beräkningstiden att vara O(b 2 2 b ) steg, vilket redan är exponentiell tid , som är betydligt längre än polynomtiden. Således faller denna algoritm inte i klassen P . (Men andra, snabbare algoritmer för detta problem kan användas som körs i polynomtid och därmed faller problemet i klass P.)

Litteratur