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.

 

Vad är en Turingmaskin?

En Turingmaskin är en abstrakt beräkningsmodell som används för att formalisera vad som menas med "beräkningsbarhet". Modellen består i grunden av:

  • En oändlig bandremsa uppdelad i celler som innehåller symboler från ett ändligt alfabet.
  • En läs-/skrivhuvud som kan läsa symbolen på den cell den står på, skriva en symbol och flytta sig åt vänster eller höger.
  • En ändlig uppsättning tillstånd som beskriver maskinens interna läge.
  • En övergångsfunktion (regler) som, givet nuvarande tillstånd och den lästa symbolen, bestämmer vad som ska skrivas, vilket tillstånd som ska antas och i vilken riktning huvudet ska flyttas.

Formell definition och varianter

Formellt definieras en Turingmaskin ofta som en sjugradig tupel (Q, Σ, Γ, δ, q0, qaccept, qreject) där Q är mängden tillstånd, Σ indataalfabetet, Γ bandalfabetet, δ övergångsfunktionen, q0 starttillstånd och qaccept/qreject accepterande/avvisande tillstånd. Det finns flera varianter:

  • Deterministisk Turingmaskin (DTM) — exakt en möjlig övergång för varje kombination av tillstånd och symbol.
  • Ikke-deterministisk Turingmaskin (NDTM) — flera möjliga övergångar; används i komplexitetsteori för att definiera klassen NP.
  • Universal Turingmaskin (UTM) — en maskin som kan simulera vilken annan Turingmaskin som helst givet en kodning av den maskinen och dess indata; visar att en enda maskin kan utföra alla beräkningar som definieras av modellen.
  • Andra varianter: multitapemaskiner, icke-deterministiska, stokastiska och begränsade versioner (t.ex. linjärt begränsad).

Historia och bakgrund

Alan Turing presenterade Turingmaskinen i artikeln "On Computable Numbers" (1936) som en del av arbetet med Entscheidungsproblem (beslutsproblemet) inom matematiken. Samtidigt formulerades andra liknande idéer av bland andra Alonzo Church; det ledde till Church–Turing‑tesen, som informellt säger att alla rimligt definierade modeller av beräkning kan utföra samma mängd beräkningar som en Turingmaskin.

Betydelse inom datavetenskap

Turingmaskinen är central för flera områden:

  • Teori för beräkningsbarhet: Den avgör vilka problem som är beräkningsbara (deciderbara) och vilka som är omöjliga att lösa med någon algoritm. Exempel: stoppningsproblemet (haltingproblemet) är bevisat icke-avgörbart.
  • Komplexitetsteori: Modellen används för att definiera komplexitetsklasser som P, NP, EXP med flera och för att studera tids- och rumsresurser.
  • Formella språk och automatteori: Turingmaskiner visar relationen mellan språkklasser och beräkningsmodeller (till exempel rekursivt uppräkneliga språk).
  • Grund för moderna datorer: Trots att Turingmaskinen är en förenklad matematisk modell, fångar den kärnan i vad en digital dator kan beräkna; begrepp som program, universella maskiner och tolkare hänger nära ihop med Turingmaskinens idéer.

Exempel och intuitiv förståelse

En enkel Turingmaskin kan till exempel avgöra om ett binärt tal innehåller ett jämnt antal ettor genom att växla mellan två tillstånd (jämn/udda) när den läser en etta och lämna andra symboler oförändrade. En universal Turingmaskin kan läsa en kodning av sådan maskin och ett givet indata och simulera dess arbete steg för steg.

Begränsningar och viktiga resultat

  • Oavgörbarhet: Vissa problem, såsom stoppningsproblemet, har visats vara icke-avgörbara för Turingmaskiner — ingen algoritm kan lösa dem i alla fall.
  • Praktiska begränsningar: Turingmaskinen är ett teoretiskt redskap och ignorerar praktiska aspekter som tidskostnad, parallellism eller fysiska begränsningar, men dessa aspekter studeras i komplexitetsteori och andra modeller.

Sammanfattning

Turingmaskinen är en enkel men kraftfull abstraktion som formulerar vad det innebär att beräkna något med en algoritm. Den har lagt grunden för modern teoretisk datavetenskap, gett upphov till centrala begrepp som beräkningsbarhet, universella maskiner och komplexitetsklasser, och fortfarande fungerar som referensmodell när man diskuterar vilka problem som kan lösas av datorer och vilka som är fundamentalt omöjliga.