Turingmaskin
Turingmaskin är en term från datavetenskapen. En Turingmaskin är ett system av regler, tillstånd och övergångar snarare än en riktig maskin. Den beskrevs första gången 1936 av den engelske matematikern och datavetaren Alan Turing. Det finns två syften med en Turingmaskin: att avgöra formella språk och lösa matematiska funktioner. Turingmaskiner är en av de viktigaste formella modellerna i studiet av datavetenskap.
Modell av en Turing-maskin
Gemensamma grunder
En Turingmaskin består av följande komponenter (förenklat):
- En begränsad uppsättning tillstånd (med ett tillstånd markerat som starttillstånd; när en Turingmaskin körs har den alltid ett aktuellt tillstånd).
- Ett oändligt band med lagringsceller och en läs- och skrivenhet som kan röra sig på bandet.
- En definition av en så kallad övergångsfunktion
Dessutom måste ett arbetsalfabet (teckenuppsättning) definieras.
När en Turingmaskin startas måste ett ord (från arbetsalfabetet) finnas på maskinens oändliga band. Läs/skriv-enheten på det första tecknet läser nu det första tecknet och beroende på Turingmaskinens aktuella tillstånd skriver läs/skriv-enheten över tecknet med ett nytt eller flyttar en cell till vänster eller höger. Dessutom kan maskinens aktuella tillstånd bytas ut.
Turingmaskiner som bestämmer språk
I teorin om avgörbarhet sägs en Turingmaskin avgöra ett språk om den alltid kan avgöra om ett visst ord ingår i ett visst språk eller inte. Därför har maskinen vanligtvis två särskilda tillstånd som markeras som Acceptera och Avvisa. Efter en tid kommer ett av de två tillstånden att nås (beroende på det inmatade ordet) och maskinen stannar. Om endast ett av de två tillstånden någonsin kommer att nås, sägs Turingmaskinen vara halvt beslutsför om ett språk.
Turingmaskiner som beräknar funktioner
Om en Turingmaskin används för att beräkna funktioner har den bara ett sluttillstånd. När maskinen kommer till det tillståndet stannar den och resultatet av funktionen (beroende på inmatningen) kan hittas på bandet.
Turingmaskinernas inverkan
Turingmaskiner uppfanns inte för att byggas i verkligheten, men de är mycket viktiga för teoretisk datavetenskap eftersom de är en av de enklaste modellerna för datorer. Enligt Church-Turing-tesen är alla datorer bara lika kraftfulla som Turingmaskiner. Detta kan användas för att bevisa om ett problem kan lösas av en dator eller inte.
Variationer
- En Turing-maskin kan bestå av flera oändliga band (och flera läs/skriv-enheter). Det är dock bevisat att sådana maskiner bara är lika kraftfulla som maskiner med ett enda band. Maskiner med flera band är användbara när det gäller mer komplexa problem.
- Om en Turingmaskin har en icke-deterministisk övergångsfunktion kan det ske flera övergångar från ett tillstånd till många andra när ett tecken läses. Även detta ökar inte Turingmaskinernas styrka. Icke-deterministiska Turingmaskiner (som de kallas då) kan dock möjligen minska beräkningstiden kraftigt. Denna fråga behandlas i P kontra NP-diskussionen och är ännu inte löst. De flesta forskare antar dock att icke-deterministiska maskiner kan arbeta mycket snabbare med vissa problem.
- En universell Turingmaskin är en variant som kan simulera en Turingmaskin med en indata.
