Turingmaskin

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

[redigera] 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.

[redigera] Formell definition

Hopcroft och Ullman ^[1] definierar en (deterministisk) Turingmaskin som en 7-tupel $M = (Q,Γ, b,Σ,δ, q 0, F)$ där

$Q$ är en ändlig icke-tom mängd av tillstånd
$Γ$ är en ändlig icke-tom mängd av symboler
$b \in \Gamma$ är den tomma symbolen (den enda symbolen som tillåts finnas oändligt många gånger på remsan under något beräkningssteg)
$\Sigma\subseteq\Gamma\setminus\{b\}$ är mängden av indata-symboler (d.v.s. en delmängd av alla symboler utom den tomma symbolen)
$\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L,R,N\}$ är övergångsfunktionen där L = steg åt vänster, R = steg åt höger, N = stå stilla.
$q_0 \in Q$ är starttillståndet
$F \subseteq Q$ är mängden av sluttillstånd

[redigera] 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,Σ,δ, s 1, F)$

$Q = {s 1, s 2, s 3, s 4, s 5, s 6}$
$Γ = {1,0}$
$Σ = {1}$
$F = {s 6}$
$δ$ beskrivs av följande tabell:

aktuellt tillstånd	läst symbol		skriven symbol	nytt tillstånd	rörelse
s1	1	->	0	s2	R
s1	0	->	0	s6	N
s2	1	->	1	s2	R
s2	0	->	0	s3	R
s3	0	->	1	s4	L
s3	1	->	1	s3	R
s4	1	->	1	s4	L
s4	0	->	0	s5	L
s5	1	->	1	s5	L
s5	0	->	1	s1	R

Maskinen genomlöper t.ex. 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-

[redigera] Referenser

^ 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.

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.