Turing maskin

Turing machine (MT)  är en abstrakt executor (abstrakt dator). Det föreslogs av Alan Turing 1936 för att formalisera konceptet med en algoritm .

En Turing-maskin är en förlängning av en finit automat och kan enligt Church-Turing-avhandlingen simulera alla exekutorer (genom att sätta övergångsregler) som på något sätt implementerar en steg-för-steg-beräkningsprocess där varje beräkningssteg är ganska elementärt.

Det vill säga, vilken intuitiv algoritm som helst kan implementeras med hjälp av någon Turing-maskin [1] .

Enhet

Sammansättningen av Turing-maskinen inkluderar ett band obegränsat i båda riktningarna (Turing-maskiner som har flera oändliga band är möjliga), uppdelat i celler [2] [3] , och en kontrollenhet (även kallad ett skrivläshuvud ( GZCH ) ), som kan vara i en av de många staterna . Antalet möjliga tillstånd för styranordningen är ändligt och exakt givet.

Kontrollenheten kan röra sig åt vänster och höger längs bandet, läsa och skriva tecken i något ändligt alfabet till cellerna. En speciell tom symbol tilldelas, som fyller alla celler på bandet, utom de av dem (ett ändligt tal) på vilka indata skrivs.

Styrenheten fungerar enligt övergångsreglerna , som representerar algoritmen som implementeras av den givna Turing-maskinen. Varje övergångsregel instruerar maskinen, beroende på det aktuella tillståndet och den symbol som observeras i den aktuella cellen, att skriva en ny symbol till denna cell, gå till det nya tillståndet och flytta en cell till vänster eller höger. Vissa tillstånd i Turing-maskinen kan markeras som terminal , och övergången till någon av dem innebär slutet på arbetet, algoritmens stopp.

En Turing-maskin sägs vara deterministisk om varje kombination av tillstånd och bandsymbol i tabellen matchar högst en regel. Om det finns ett "bandsymbol-tillstånd"-par för vilket det finns 2 eller fler instruktioner, kallas en sådan Turing-maskin icke- deterministisk .

Beskrivning av Turing-maskinen

En specifik Turing-maskin specificeras genom att räkna upp elementen i uppsättningen bokstäver i alfabetet A, uppsättningen av tillstånd Q och uppsättningen regler som maskinen fungerar efter. De har formen: q i a j →q i1 a j1 d k (om huvudet är i tillståndet qi , och bokstaven a j skrivs i den övervakade cellen , går huvudet in i tillståndet qi1 , a j1 skrivs till cellen istället för ett j , huvudet gör en rörelse d k , som har tre alternativ: en cell till vänster (L), en cell till höger (R), stanna på plats (N)). För varje möjlig konfiguration <q i , a j > finns det exakt en regel (för en icke-deterministisk Turing-maskin kan det finnas fler regler). Det finns inga regler bara för det slutliga tillståndet, en gång i vilket maskinen stannar. Dessutom måste du ange start- och slutlägen, den initiala konfigurationen på bandet och platsen för maskinhuvudet.

Exempel

Ett exempel på en Turingmaskin för att multiplicera tal i det enära talsystemet . Regelposten "q i a j →q i1 a j1 R/L/N" ska förstås på följande sätt: q i  är tillståndet i vilket denna regel exekveras, a j  är data i cellen där huvudet är belägen, q i1  är det tillstånd du vill gå till, och j1  - vad du behöver skriva till cellen, R / L / N - kommandot för att flytta.

Maskinen fungerar enligt följande uppsättning regler:

Beskrivning av stater:

Multiplicera med hjälp av MT 3 med 2 i enhetssystemet. Protokollet indikerar de initiala och slutliga tillstånden för MT, den initiala konfigurationen på bandet och platsen för maskinhuvudet (understruken symbol).

Start. Vi är i tillståndet q 0 , matade in data i maskinen: *111x11=*, maskinhuvudet finns på det första tecknet *.

1:a steget. Vi tittar på regeltabellen vad maskinen kommer att göra, i tillståndet q 0 och över "*"-symbolen. Denna regel kommer från den första kolumnen i den femte raden - q 0 *→q 0 *R. Det betyder att vi flyttar till tillståndet q 0 (det vill säga vi ändrar det inte), symbolen blir "*" (det vill säga den ändras inte) och vi flyttar längs texten "*111x11=*" vi skrev in till höger med en position (R), då finns det en 1 för det 1:a tecknet. I sin tur bearbetas tillståndet q 0 1 (1:a kolumnen 1:a raden) av regeln q 0 1→q 0 1R. Det vill säga, återigen är det bara en övergång till höger med 1 position. Detta händer tills vi står på symbolen "x". Och så vidare: vi tar tillståndet (index vid q), tar symbolen som vi står på (understruken symbol), kopplar ihop dem och tittar på bearbetningen av den resulterande kombinationen enligt regeltabellen.

I enkla ord är multiplikationsalgoritmen följande: vi markerar den första enheten av den andra faktorn, ersätter den med bokstaven "a" och överför hela den första faktorn bortom likhetstecknet. Överföringen görs genom att växelvis ersätta enheterna i den första multiplikatorn med "a" och lägga till samma antal enheter i slutet av raden (till vänster om "*" längst till höger). Sedan ändrar vi alla "a" upp till multiplikationstecknet "x" tillbaka till enheter. Och cykeln upprepas. I själva verket, trots allt, A multiplicerat med B kan representeras som A + A + A B gånger. Vi markerar nu den 2:a enheten i den 2:a multiplikatorn med bokstaven "a" och överför enheterna igen. När det inte finns några enheter före "="-tecknet, är multiplikationen klar.

Turing fullständighet

Vi kan säga att Turing-maskinen är den enklaste linjära minnesdatorn som, enligt formella regler, transformerar indata med hjälp av en sekvens av elementära åtgärder .

Det elementära med åtgärder är att handlingen endast ändrar en liten bit data i minnet (i fallet med en Turing-maskin, endast en cell), och antalet möjliga åtgärder är begränsat. Trots Turing-maskinens enkelhet kan allt beräknas på den som kan beräknas på vilken annan maskin som helst som utför beräkningar med en sekvens av elementära operationer. Denna egenskap kallas fullständighet .

Ett naturligt sätt att bevisa att beräkningsalgoritmer som kan implementeras på en maskin kan implementeras på en annan är att simulera den första maskinen på den andra.

Imitationen är som följer. Beskrivningen av programmet (driftsreglerna) för den första maskinen och indata som skulle ha tagits emot vid ingången till den första maskinen matas till ingången på den andra maskinen. Det är nödvändigt att beskriva ett sådant program (driftsreglerna för den andra maskinen) så att utdata som ett resultat av beräkningar är densamma som den första maskinen skulle returnera om den fick data .

Som sagt, på en Turing-maskin är det möjligt att imitera (genom att ställa in övergångsreglerna) alla andra exekutorer som på något sätt implementerar processen med steg-för-steg-beräkning, där varje steg i beräkningen är ganska elementärt.

På en Turing-maskin kan du simulera en Post-maskin , normala Markov-algoritmer och vilket program som helst för vanliga datorer som konverterar indata till utdata enligt någon algoritm. I sin tur är det på olika abstrakta exekutorer möjligt att imitera Turing Machine. Exekutorer för vilka detta är möjligt kallas Turing komplett.

Det finns program för konventionella datorer som efterliknar driften av en Turing-maskin. Men denna simulering är ofullständig, eftersom Turing-maskinen har ett abstrakt oändligt band. Ett oändligt databand kan inte helt simuleras på en dator med ett ändligt minne: det totala datorminnet - RAM, hårddiskar, olika externa lagringsmedier, processorregister och cache etc. - kan vara mycket stort, men ändå är det alltid ändligt . Den teoretiska gränsen för mängden information som kan finnas inuti en given yta är, upp till en faktor, lika med entropin för ett svart hål med samma yta.

Turingmaskinvarianter

Turingmaskinmodellen tillåter förlängningar. Man kan överväga Turing-maskiner med ett godtyckligt antal band och flerdimensionella band med olika begränsningar. Alla dessa maskiner är dock Turing kompletta och modelleras av en vanlig Turing-maskin.

En Turing-maskin som körs på ett semi-oändligt band

Som ett exempel på en sådan reduktion, överväg följande teorem: För vilken Turing-maskin som helst, finns det en motsvarande Turing-maskin som körs på ett semi-oändligt band (det vill säga ett band som är oändligt i en riktning).

Betrakta beviset från Yu. G. Karpov i boken Theory of Automata. Beviset för detta teorem är konstruktivt, det vill säga vi kommer att ge en algoritm med vilken, för vilken Turing-maskin som helst, en likvärdig Turing-maskin med en deklarerad egenskap kan konstrueras. Först numrerar vi godtyckligt cellerna i MT-arbetsbandet, det vill säga vi bestämmer den nya platsen för information på bandet:

Sedan numrerar vi om cellerna, och vi antar att symbolen "*" inte finns i MT-ordboken:

Slutligen ändrar vi Turing-maskinen genom att dubbla dess antal tillstånd och ändra förskjutningen av läs-skrivhuvudet så att i en grupp av tillstånd är maskinens funktion likvärdig med dess drift i den skuggade zonen och i den andra gruppen av tillstånd maskinen fungerar som originalmaskinen gör i det oskuggade området. Om symbolen '*' påträffas under MT-drift, har läs-skrivhuvudet nått zongränsen:

Det ursprungliga tillståndet för en ny Turing-maskin är inställt i en eller annan zon, beroende på var i originalbandet läs-skrivhuvudet var placerat i den ursprungliga konfigurationen. Uppenbarligen, till vänster om de begränsande markörerna "*" används inte tejpen i motsvarande Turing-maskin.

Tvådimensionella Turing-maskiner

• Ant Langton

Se även

• JFLAP plattformsoberoende program - automatsimulator, Turing-maskiner, grammatik, ritar automatgraf
• Universal Turingmaskin
• Icketerministisk Turingmaskin
• Probabilistisk Turing-maskin
• Turing kvantmaskin
• Teori om algoritmer
• Turing träsk
• Turing diagram
• Minskys bil

Andra abstrakta implementerare och formella datorsystem

• Normal Markov-algoritm ( produktionsprogrammering )
• Postens maskin ( automatisk programmering )
• Rekursiv funktion (beräkningsbarhetsteori)
• Lambdakalkyl ( funktionell programmering )
• Brainfuck ( imperativ programmering )

Anteckningar

1. ↑ Nefyodov, 1992 , sid. 97.
2. ↑ Nefyodov, 1992 , sid. 94.
3. ↑ Ebbinhouse, 1972 , sid. 24.

Litteratur

• John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Kapitel 8. Introduktion till Turing Machine Theory // Introduktion till automatteori, språk och beräkningar. - M. : Williams , 2002. - 528 sid. - ISBN 0-201-44124-1 .
• Karpov Yu. G. Theory of automata. - Peter, 2003. - ISBN 5-318-00537-3 .
• Ebbinhaus GD, Jacobs K., Man FK, Hermes G. Turingmaskiner och rekursiva funktioner. — M .: Mir, 1972. — 262 sid.
• Nefedov V. N., Osipova V. A. Kurs i diskret matematik. — M. : MAI, 1992. — 260 sid.

Länkar

• Turingmaskin // Föreläsning av Alexander Shen i PostNauka- projektet (2013-06-04)

Ordböcker och uppslagsverk	Stor dansk stor kines Britannica (online) Universalis
I bibliografiska kataloger BNE : XX550362 BNF : 11978871z GND : 4203525-9 J9U : 987007555894805171 LCCN : sh85138778 NDL : 00573533 SUDOC : 027831655