Turingmaskin
Från Rilpedia
En Turingmaskin är en abstrakt mekanism, en teoretisk modell, för att utföra beräkningar, som utvecklades av Alan Turing år 1936. Turingmaskinen konstruerades till den enklast möjliga mekanismen som är kapabel att utföra icke-triviala beräkningar, och spelar en central roll i teorierna för beräkningsbarhet och beräkningskomplexitet, samt allmänt inom den matematiska logiken.
En Turingmaskin kan konstrueras för att lösa ett givet problem (en specifik turingmaskin), men det går också att konstruera en universell turingmaskin som är kapabel att läsa en kodad beskrivning av en specifik turingmaskin med dess indata, och sedan utföra denna maskins beräkning.
Church-Turings hypotes säger att varje tänkbar beräkningsprocess kan utföras av en Turingmaskin, och alltså att det rent principiellt inte finns någon mer kraftfull beräkningsmekanism. Denna tes är inte i strikt matematisk mening bevisad, men allmänt accepterad som sann. Argument som talar för tesen är bland andra att andra försök till teoretiska modeller av beräkningsprocesser, som till exempel Churchs lambdakalkyl, rekursionsteori och post-maskiner, kan visas vara ekvivalenta med turingmaskiner. Alla dagens datorer kan också betraktas som turingmaskiner: de kan med andra ord simuleras av en sådan.
Teorierna om turingmaskiner fick stor betydelse för konstruktionerna av de första datorerna, till exempel Z3 .
Innehåll |
Informell beskrivning
En Turingmaskin består av
- en remsa med ett oändligt antal rutor, som var och en kan innehålla en symbol eller vara tom
- ett skriv- och läshuvud som kan förflytta sig längs remsan åt höger eller vänster en ruta i taget, och skriva en symbol i eller läsa en symbol från den ruta den befinner sig vid.
- en styrenhet som kan befinna sig i ett ändligt antal olika tillstånd (eng. states)
Läs-och skrivhuvudet rör sig längs remsan på order av styrenheten. Maskinen arbetar i diskreta beräkningssteg som styrs av en nästatillståndsfunktion eller övergångsfunktion (eng. transition function eller action table), ett slags program. Denna funktion kan beskrivas som en tabell som anger, för varje kombination av tillstånd i styrenheten och symbol i aktuell ruta, det beräkningsteg (eng. action) som ska utföras. Ett beräkningssteg kan vara att flytta sig ett steg åt ena eller andra hållet på remsan, och läsa eller skriva en symbol i aktuell ruta. Tabellen anger också vilket tillstånd styrenheten övergår till efter att ha utfört beräkningsteget.
Maskinen startar med ett starttillstånd och en given position på remsan, och avslutar beräkningen när ett sluttillstånd uppnås. Beräkningen kan misslyckas genom att maskinen aldrig uppnår sluttillståndet och fortsätter i all oändlighet.
Formell definition
Hopcroft och Ullman [1] 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
är den tomma symbolen (den enda symbolen som tillåts finnas oändligt många gånger på remsan under något beräkningssteg)
är mängden av indata-symboler (d.v.s. en delmängd av alla symboler utom den tomma symbolen)
är övergångsfunktionen där L = steg åt vänster, R = steg åt höger, N = stå stilla.
är starttillståndet
är mängden av sluttillstånd
Exempel
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 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 t.ex. följande steg när den får en remsa med indata "11":
|
|
Referenser
- ↑ Hopcroft, John; Ullman, Jeffrey: Introduction to Automata Theory, Languages and Computation, Addison-Wesley, Reading Mass. 1979, 1:a utgåvan, sid. 148. ISBN 0-201-02988-X.
- Artikeln är, helt eller delvis, en översättning från tyskspråkiga Wikipedia.
- Artikeln är, helt eller delvis, en översättning från engelskspråkiga Wikipedia.
Se även
Bör ej förväxlas med Turingtest.
