Turingmaskin
teoretisk modell för att utföra beräkningar som utvecklades av Alan Turing år 1936 Från Wikipedia, den fria encyklopedin
teoretisk modell för att utföra beräkningar som utvecklades av Alan Turing år 1936 Från Wikipedia, den fria encyklopedin
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:
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, Σ, δ, q0, F) där
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, Σ, δ, s1, F)
| 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":
|
|
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
