Turingmaskin

Från Wikipedia
Hoppa till navigering Hoppa till sök
Ej att förväxla med Turingtest.
En modell av Turingmaskinen

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.

Uppbyggnad[redigera | redigera wikitext]

Turingmaskinen består av fyra delar:

  • En remsa delad upp i rutor. Remsan är så lång som det behövs för maskinen att utföra det den ska, ideala 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 kan röra sig endast en ruta åt 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 huvudet på remsan men är själv stilla.
  • En styrenhet som sparar Turingmaskinens tillstånd. Turingmaskinen kan ha oändligt med tillstånd. Styrenheten bestämmer Turingmaskinens tillstånd från instruktionerna som getts maskinen.
  • En viss längds instruktion, där det står för varje tillstånd en regel som styrenheten följer.[1]
Representation av läshuvudet och remsan

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. Instruktioner innehåller regler för vad den ska göra vid olika tillstånd. De innehåller två av dessa tre saker: (1) om maskinen ska skriva eller sudda ut en symbol eller (2) flytta huvudet till vänster eller höger och (3) behålla samma tillstånd eller byta, men notera (1) och (2) kan inte ske på samma instruktion. 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, sedan byt till tillstånd 6. För varje tillstånd finns det en egen regel för vad huvudet ska göra för varje symbol som finns.

Styrenheten är den som tolkar instruktionerna och ger sedan order till huvudet. Styrenheten har ändligt med tillstånd, med ett par undantag. Styrenheten börjar alltid vid ett början tillstånd, som ändras sen på basis av instruktionerna och slutar vid ett av två sluttillstånd, ett där dess uppgift lyckas och en där det inte sker. Turingmaskinen slutar då den kommit fram till en lösning, detta sker då den nått ett tillstånd och en symbol som det inte finns en instruktion för vad den ska göra. Om Turingmaskinen misslyckas kommer den att hålla på i en evighet, till exempel vid problem som är olösbara.

Turingmaskinen kan även ha fler än en remsa. Om man vill ha en mer effektiv Turingmaskin, lönar det sig att ha en remsa därifrån den får sina instruktioner och en annan som den skriver på. Detta år på grund av att då hamnar maskinen fara tillbaka alltid och rensa de onödiga symbolerna, vilket resulterar i fler steg.

Varje del i maskinen och dess funktioner är ändliga, diskreta och särskiljbara, det är den oändliga remsan och oändliga körningstiden, som leder till maskinens obundna lagringsutrymme.[2]

Formell definition[redigera | redigera wikitext]

Turingmaskinen har flera formella definitioner, men oavsett uppenbara skillnader, finns det en definition som gäller alla Turingmaskiner. Hopcroft och Ullman [3] definierar en (deterministisk) Turingmaskin som en 7-tupel M = (Q, Γ, b, Σ, δ, q0, 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.
  • q0Q är starttillståndet.
  • FQ är mängden av sluttillstånd.

Denna definition är egentligen bara för en enremsig Turingmaskin, men kan lätt tillämpas för flerremsiga då de också har bara ett tillstånd under uträkningens gång.  Med flerremsiga måste dock övergångsfunktionen läsas för varje remsa skillt och se i vilket tillstånd man hamnar i efter att alla huvuden har flyttats. I en flerremsig maskin antar man att varje huvud gör sina räkningar samtidigt och de flyttas i samma takt. Man måste märka att huvuden vid de olika remsorna rör sig på olika sätt. Övergångsfunktionen fungerar så att dess funktion baserar sig på alla de symboler huvuden läst och därför är inte de andra huvudens rörelse oberoende av de lästa symbolerna av andra huvuden. Nu baserar alltså övergångsfunktionen sig på alla symboler som blivit lästa av huvuden.

Ett språk L och Σ är ett rekursivt uppräkningsbart språk, bara om det finns någon Turingmaskin som förstår språket. Dessa språk baserar sig på den formella definitionen för Turingmaskinen, för att med hjälp av den definitionen kan även dessa språk definieras.[4]

Historia[redigera | redigera wikitext]

Alan Turing[redigera | redigera wikitext]

Huvudartikel: Alan Turing
Alan Turing

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

Redan som barn märkte man att Turing hade genialiska egenskaper. Han började studera vid King’s College i Cambridge och sedan fortsatte han sina studier i Princeton där han tog sin examen men 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ämbar. Han var även ledare för gruppen som under andra världskriget löste den tyska nazikoden Enigma. Man har uppskattat att detta arbete förkortade kriget med mellan två och fyra år.

Turingmaskinen[redigera | redigera wikitext]

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 hans Ph.D I Princeton universitetet. Turing publicerade ett arbete “On Computable Numbers, with an application to the Entscheidungsproblem,” var han för första gången beskrev Turingmaskinen.[6] Beskrivningen av Turingmaskinen hade många samma drag som en riktig dator, till exempel användningen av en remsa som minne. Artikel blev grunden för datavetenskap.Turing namngav maskinen först “a-machine”, 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 problem som är lösbara. Men som sagt hade den ändå många liknande drag som en dator.[7]  

Jämförelse med datorer[redigera | redigera wikitext]

Dagens moderna datorer baserar sig på den ideologiska 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 klarar till och med av mera. En väsentlig skillnad mellan Turingmaskinen och datorer är mängden data de kan behandla. Eftersom Turingmaskin är en teoretisk maskin, kan den behandla en oändligt stor mängd data tack vare sitt obegränsade minne. Datorer däremot har ett begränsat minne på grund faktorer som kommer emot i den riktiga världen.[8]

En annan relevant skillnad mellan Turingmaskinen och datorer är deras snabbhet. Även denna skillnad beror på hinder som inte gäller för den teoretiska modellen, Turingmaskinen. Det beskrivs ibland att Turingmaskinen operationaliserar långsamt. Detta är ett falskt påstående. Eftersom Turingmaskinen är en teoretisk modell, opererar den inte med någon bestämd hastighet i förhållande till den riktiga världen. Därmed funktionerar datorer med en hastighet som, liksom deras minne, är begränsat av tekniska faktorer.[9]

Andra Turingmaskiner[redigera | redigera wikitext]

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.

Flerremsiga Turingmaskinen är likadan som Turingmaskinen bara att den har flera remsor. Varje remsa har ett eget skriv- och läshuvud. Denna modell verkar mera kraftfull och bättre vilket inte riktigt är sant. Vilken som helst flerremsig maskin kan ersättas med en enkelremsig maskin, den enkelremsiga maskinen har endast kvadratiskt mer beräkningstid. Dessutom kan inte den flerremsiga maskinen räkna ut fler funktioner än en enkelremsig maskin.

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,  flyttar n huvuden oberoende av n spår.

För varje tillstånd och symboler i en icke-deterministisk Turingmaskin finns det en grupp av handlingar som Turingmaskinen kan ha. 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. Universella Turingmaskinen kan köra vilken Turingmaskin som helst på någon inmatning medan en Turingmaskin tar någon inmatning och genererar en utmatning.

Exempel[redigera | redigera wikitext]

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). D.v.s 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, Σ, δ, s1, F)

  • Q = {s1, s2, s3, s4, s5, s6}
  • Γ = {1, 0}
  • Σ = {1}
  • F = {s6}
  • δ beskrivs av följande tabell:
Aktuellt
tillstånd
Läst
symbol
Skriven
symbol
Nytt
tillstånd
Rörelse Kommentar
s1 0 0 s6 N Ingen (mer) etta att kopiera. Klar!
s1 1 0 s2 R Kopiera denna etta till näst-nästa nolla högerut, lämna en nolla som markering för tillbakavägen (markerad som kursiv i tabellerna nedan).
s2 1 1 s2 R Leta vidare högerut efter första nollan.
s2 0 0 s3 R Första nollan hittad. Gå vidare till s3, som hittar andra.
s3 1 1 s3 R Leta vidare högerut efter andra nollan.
s3 0 1 s4 L Andra nollan hittad, skriv en etta och gå tillbaka två nollor.
s4 1 1 s4 L Leta vidare vänsterut efter första nollan på tillbakavägen.
s4 0 0 s5 L Första nollan hittad. Gå vidare till s5 som hittar andra.
s5 1 1 s5 L Leta vidare vänsterut efter andra nollan (den som s1 lämnade som markering).
s5 0 1 s1 R Nollan hittad. Skriv tillbaka den etta som s1 skrev över, och börja sedan om från början, men utgå från ett steg åt höger.

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

Steg Tillstånd Remsa
1 s1 11000
2 s2 01000
3 s2 01000
4 s3 01000
5 s4 01010
6 s5 01010
7 s5 01010
8 s1 11010
Steg Tillstånd Remsa
9 s2 10010
10 s3 10010
11 s3 10010
12 s4 10011
13 s4 10011
14 s5 10011
15 s1 11011
16 s6 -stopp-

Se även[redigera | redigera wikitext]

Referenser[redigera | redigera wikitext]

  1. ^ ”AlanTuring.net What is a Turing machine?”. www.alanturing.net. http://www.alanturing.net/turing_archive/pages/Reference%20Articles/What%20is%20a%20Turing%20Machine.html. Läst 12 april 2019. 
  2. ^ ”CSC 4170 Informal Definition of Turing Machines”. www.seas.upenn.edu. https://www.seas.upenn.edu/~cit596/notes/dave/turing1.html. Läst 12 april 2019. 
  3. ^ Hopcroft, John; Ullman, Jeffrey (1979). Introduction to Automata Theory, Languages and Computation (1:a utgåvan). Reading Mass.: Addison-Wesley. sid. 148. ISBN 0-201-02988-X 
  4. ^ ”formal definition of a Turing machine”. planetmath.org. https://planetmath.org/formaldefinitionofaturingmachine. Läst 12 april 2019. 
  5. ^ ”Alan Turing - ETHW”. ethw.org. https://ethw.org/Alan_Turing. Läst 12 april 2019. 
  6. ^ Watson, Ian. ”How Alan Turing Invented the Computer Age” (på en). Scientific American Blog Network. https://blogs.scientificamerican.com/guest-blog/how-alan-turing-invented-the-computer-age/. Läst 12 april 2019. 
  7. ^ ”History of Computing Science: The Turing Machine”. www.eingang.org. http://www.eingang.org/Lecture/turing2.html. Läst 12 april 2019. 
  8. ^ ”American Institute of Science”. www.aiscience.org. http://www.aiscience.org/journal/allissues/ijeecs.html;jsessionid=3288D470CD52F5B47BFB85C05D20FD35.tomcat1. Läst 12 april 2019. 
  9. ^ ”AlanTuring.net”. www.alanturing.net. Arkiverad från originalet den 12 oktober 2018. https://web.archive.org/web/20181012014022/http://www.alanturing.net/. Läst 12 april 2019. 
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