Turingmaskin

En Turingmaskin är en teoretisk modell för att utföra beräkningar. Den utvecklades av matematikern Alan Turing år 1936. Syftet med Turingmaskinen är att betrakta algoritmiska lösningars gränser.

En Turingmaskin konstrueras för att lösa ett givet problem, medan den universella Turingmaskinen kan lösa vilket problem som helst. Man kan alltså tänka sig Turingmaskinen som ett datorprogram som utför ett visst program, medan den universella Turingmaskinen kan tänkas som programmerbar.

Enligt Church-Turings hypotes kan alla tänkbara beräkningsprocesser utföras av en Turingmaskin. Med andra ord är det den mest kraftfulla beräkningsmekanismen som existerar. Denna tes är inte i strikt matematisk mening bevisad, men allmänt accepterad som sann.

Teorierna som Alan Turing skapade, samt den teoretiska Turingmaskinen, har haft en stor betydelse i utvecklingen och konstruktionen av de första datorerna. Alla moderna datorer kan dessutom simuleras med en Turingmaskin. Alan Turings teorier har också en viktig roll inom den matematiska logiken.

Turingmaskinen består av fyra delar:

• En remsa uppdelad i rutor. Remsan är så lång som det behövs för maskinen att utföra det den ska, den teoretiska Turingmaskinen har en oändligt lång remsa. Rutorna är fyllda med symboler, men de kan även vara tomma. Remsan som ges åt Turingmaskinen är oftast redan färdigt ifylld med problemet som ska lösas, men kan även vara helt blank beroende på vad maskinen ska göra.
• Ett läs- och skrivhuvud. Huvudet befinner i varje ögonblick vid en viss ruta och kan röra sig en ruta i taget åt antingen vänster eller höger. Huvudet kan läsa symbolen som står i rutan och ersätta den med en ny. I vissa modeller är huvudet det som rör på sig och i andra rör sig remsan och huvudet är stilla.
• En styrenhet som sparar Turingmaskinens tillstånd. Turingmaskinen kan ha ett godtyckligt ändligt antal tillstånd. Den startar alltid i ett starttillstånd och byter sedan tillstånd genom att följa instruktionerna som getts maskinen.
• Instruktionerna lagras i en instruktionstabell. De beskriver vad maskinen skall göra beroende på vilket tillstånd den befinner sig i och vilken symbol som finns i den nuvarande rutan. ^[1]

Turingmaskinens funktion baserar sig på att maskinen ges en färdigt ifylld remsa med problemet som den ska lösa. Maskinen modifierar remsan med hjälp av instruktionerna den fått. Det finns en instruktion/regel för varje kombination av aktuellt tillstånd och aktuell symbol. Reglerna anger om maskinen ska (1) skriva eller sudda i den aktuella rutan (2) flytta huvudet till vänster eller höger (eller stå stilla) efteråt och (3) behålla samma tillstånd eller byta till ett annat. Till exempel kan en av instruktionerna låta på följande sätt: om det vid tillstånd 35 står 1 på remsan, ska den bytas till 0, därefter ändras tillståndet till tillstånd 6.

När maskinen börjat sitt arbete kan något av följande inträffa: den kommer till en instruktion som säger att arbetet är klart och maskinen skall stoppa, eller den kommer aldrig till en sådan instruktion och maskinen fortsätter då att arbeta i all oändlighet.

Det finns också varianter av Turingmaskin som har flera remsor och läs-/skrivhuvuden, men detta påverkar inte maskinens förmåga att göra beräkningar, bara hur lång tid det tar.

Varje del i maskinen och dess funktioner är ändliga, diskreta och särskiljbara, det är den oändliga remsan som leder till maskinens obegränsade lagringsutrymme.^[2]

Det finns flera matematiska formella definitioner av en Turingmaskin som alla är likvärdiga. Hopcroft och Ullman ^[3] definierar en (deterministisk) Turingmaskin som en 7-tupel M = (Q, Γ, b, Σ, δ, q₀, F) där

• Q är en ändlig icke-tom mängd av tillstånd.
• Γ är en ändlig icke-tom mängd av symboler.
• b ∈ Γ är den tomma symbolen (den enda symbolen som tillåts finnas oändligt många gånger på remsan under något beräkningssteg).
• Σ ⊆ Γ ∖ {b} är mängden av indata-symboler (d.v.s. en delmängd av alla symboler utom den tomma symbolen).
• δ: Q × Γ → Q × Γ × {L, R} är övergångsfunktionen där L = flytta läshuvudet åt vänster, R = flytta läshuvudet åt höger.
• q₀ ∈ Q är starttillståndet.
• F ⊆ Q är mängden av sluttillstånd.

Denna definition gäller för en enremsig Turingmaskin men kan modifieras för att beskriva en flerremsig sådan.

Alan Mathison Turing föddes den 23 juni 1912 i Maida Vale, London och dog den 7 juni 1954, i Wilmslow, Cheishire. Turing var matematiker och kryptoanalytiker. Turing anses ha lagt grunden till dagens informations- och datateknologi.^[4]

Redan som barn märkte man att Turing var begåvad. Han började studera vid King’s College i Cambridge och sedan fortsatte han sina studier i Princeton där han tog sin doktorsexamen med utmärkta vitsord.

Turing är mest känd för utvecklingen av Turingmaskinen och utformningen av Turingtestet. Han bevisade också att det inte finns en lösning till avgörbarhetsproblemet med att först visa att Turingmaskinens stopproblem är obestämbart. Under andra världskriget var han ledare för den grupp som knäckte tyskarnas Enigmachiffer. Man har uppskattat att detta arbete förkortade kriget med mellan två och fyra år.

Alan Turing hade ett livslångt intresse för maskiner. Han hade som barn alltid drömt om att uppfinna skrivmaskinen.

År 1936 studerade Turing för sin Ph.D vid Princetonuniversitetet. Turing publicerade då ett arbete “On Computable Numbers, with an application to the Entscheidungsproblem,” där han för första gången beskrev Turingmaskinen.^[5]. Artikeln blev grunden för datavetenskap. Turing kallade maskinen först för “a-machine”, en förkortning för automatisk maskin, men den blev senare känd som Turingmaskinen.

När han utvecklade Turingmaskinen var inte hans mening att utveckla en dator utan han ville beskriva en metod för att avgöra om ett problem var lösbart eller inte. ^[6]  

Dagens moderna datorer baserar sig på flera av idéerna som ligger till grund för Turingmaskinen. Det är därmed ingen överraskning att moderna datorer och Turingmaskinen har mycket gemensamt. En Turingmaskin klarar av att utföra allt som en dator klarar av. Den egentliga skillnaden ligger i hur många operationer och hur lång tid som behövs för att lösa ett problem. Turingmaskinens operationer är enkla och okomplicerade och det kan behövas många steg innan ett problem är löst. En dator å andra sidan har ett begränsat ändligt minne som gör att den kan ha svårt att lösa vissa typer av problem. ^[7]

Det sägs ibland att Turingmaskinen opererar långsamt jämfört med en dator. Detta är egentligen inte sant. Eftersom Turingmaskinen är en teoretisk modell, opererar den inte med någon bestämd hastighet i förhållande till den verkliga världen. Däremot arbetar en dator med en hastighet som, liksom deras minne, är begränsat av tekniska faktorer.^[8]

Förutom den ordinära Turingmaskinen finns det också liknande maskiner som till exempel flerremsig (eng. Multi-tape) Turingmaskin, flerspårig (eng. Multi-track) Turingmaskin, icke-deterministisk (eng. Non-deterministic) Turingmaskin och universell Turingmaskin.

Den flerremsiga Turingmaskinen är en variant av den vanliga Turingmaskinen som har flera remsor. Varje remsa har ett eget skriv- och läshuvud. Denna modell kan tyckas vara mera kraftfull och bättre vilket inte riktigt är sant. Varje flerremsig maskin kan ersättas med en enkelremsig maskin, den enkelremsiga maskinen använder som mest kvadratiskt mer beräkningstid för att lösa ett givet problem. Det finns inte heller någon skillnad i vilka problem som kan lösas av de olika maskinerna.

Den flerspåriga Turingmaskinen är en specifik sort av flerremsig Turingmaskinen. Flerspåriga Turingmaskinen innehåller flera spår men endast ett huvud som skriver och läser alla spår. I en vanlig N-remsig Turingmaskin, flyttas n huvuden oberoende varandra.

I en icke-deterministisk Turingmaskin finns det för varje tillstånd en grupp av handlingar som Turingmaskinen kan välja mellan. Det vill säga, övergångarna är inte deterministiska. Maskinen används för att undersöka en dators förmåga och begränsningar. P vs NP-problemet är ett av de viktigaste olösta problemen inom teoretisk datalogi, frågan gäller hur svårt det är att på en deterministisk dator att simulera icke-deterministiska beräkningar.

Universella Turingmaskinen är en Turingmaskin vars programmering simulerar andra Turingmaskiner. Den Universella Turingmaskinen kan simulera vilken annan Turingmaskin som helst genom att från remsan läsa in en beskrivning av denna specifika Turingmaskin.

Följande Turingmaskin läser en remsa med ettor och "fördubblar" dessa genom att skriva samma antal ettor efter de första, separerade av en tom ruta (0). Det vill säga med "111" som indata produceras resultatet "1110111". Maskinen har sex tillstånd varav s1 är starttillståndet och s6 är sluttillståndet och maskinen startar med läshuvudet vid den första ettan (den längst till vänster).

M = (Q, Γ, 0, Σ, δ, s₁, F)

• Q = {s₁, s₂, s₃, s₄, s₅, s₆}
• Γ = {1, 0}
• Σ = {1}
• F = {s₆}
• δ beskrivs av följande tabell:

Maskinen genomlöper till exempel följande steg när den får en remsa med indata "11":

• Turingkomplett

Den här artikeln är helt eller delvis baserad på material från finskspråkiga Wikipedia.

Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia.

• Wikimedia Commons har media som rör Turingmaskin.
  Bilder & media