Universal Turing maskin

Inom datavetenskap är en universell Turing-maskin ( UTM ) en Turing-maskin som kan simulera en godtycklig Turing-maskin på godtycklig inmatning. Den universella maskinen uppnår i huvudsak detta genom att läsa både beskrivningen av maskinen som ska simuleras och indata till den maskinen från dess eget band. Alan Turing introducerade idén om en sådan maskin 1936–1937. Denna princip anses vara ursprunget till idén om en dator med lagrat program som användes av John von Neumann 1946 för "Electronic Computing Instrument" som nu bär von Neumanns namn: von Neumann-arkitekturen .

När det gäller beräkningskomplexitet behöver en multi-tape universell Turing-maskin bara vara långsammare med logaritmisk faktor jämfört med de maskiner som den simulerar.

Introduktion

Varje Turing-maskin beräknar en viss fast partiell beräkningsbar funktion från inmatningssträngarna över dess alfabet . I den meningen beter den sig som en dator med ett fast program. Däremot kan vi koda handlingstabellen för vilken Turing-maskin som helst i en sträng. Således kan vi konstruera en Turing-maskin som förväntar sig på sitt band en sträng som beskriver en handlingstabell följt av en sträng som beskriver inmatningsbandet, och beräknar det band som den kodade Turing-maskinen skulle ha beräknat. Turing beskrev en sådan konstruktion fullständigt i sin uppsats från 1936:

"Det är möjligt att uppfinna en enda maskin som kan användas för att beräkna vilken beräkningsbar sekvens som helst. Om denna maskin U är försedd med ett band på vars början skrivs SD ["standardbeskrivning" av en åtgärdstabell] för någon dator maskin M , då kommer U att beräkna samma sekvens som M ."

Dator med lagrat program

Davis gör ett övertygande argument att Turings uppfattning om vad som nu kallas "den lagrade programdatorn", att placera "åtgärdstabellen" - instruktionerna för maskinen - i samma "minne" som indata, starkt påverkade John von Neumanns uppfattning om den första amerikanska datorn med diskret symbol (i motsats till analog) - EDVAC . Davis citerar Time Magazine för detta, att "alla som trycker på ett tangentbord ... arbetar på en inkarnation av en Turing-maskin", och att "John von Neumann [byggde] på Alan Turings arbete" (Davis 2000: 193 som citerar Time Magazine av den 29 mars 1999).

Davis hävdar att Turings dator med Automatic Computing Engine (ACE) "förutsåg" begreppen mikroprogrammering ( mikrokod ) och RISC- processorer (Davis 2000:188). Knuth citerar Turings arbete med ACE-datorn som att designa "hårdvara för att underlätta subrutinkoppling" (Knuth 1973:225); Davis refererar också till detta arbete som Turings användning av en hårdvaru-"stack" (Davis 2000:237 fotnot 18).

Eftersom Turing Machine uppmuntrade konstruktionen av datorer , uppmuntrade UTM utvecklingen av den nya datavetenskapen . En tidig, om inte den allra första, assembler föreslogs "av en ung hot-shot programmerare" för EDVAC (Davis 2000:192). Von Neumanns "första seriösa program ... [var] att helt enkelt sortera data effektivt" (Davis 2000:184). Knuth konstaterar att subrutinavkastningen inbäddad i själva programmet snarare än i speciella register kan tillskrivas von Neumann och Goldstine. Knuth konstaterar vidare det

Den första tolkningsrutinen kan sägas vara "Universal Turing Machine" ... Tolkningsrutiner i konventionell mening nämndes av John Mauchly i hans föreläsningar vid Moore School 1946 ... Turing deltog också i denna utveckling; tolkningssystem för Pilot ACE-datorn skrevs under hans ledning.

— Knuth 1973:226

Davis nämner kortfattat operativsystem och kompilatorer som resultat av begreppet program-as-data (Davis 2000:185).

Vissa kan dock ta upp problem med denna bedömning. På den tiden (mitten av 1940-talet till mitten av 1950-talet) var en relativt liten kader av forskare intimt involverade i arkitekturen av de nya "digitala datorerna". Hao Wang (1954), en ung forskare vid denna tid, gjorde följande observation:

Turings teori om beräkningsbara funktioner gick före men har inte mycket påverkat den omfattande faktiska konstruktionen av digitala datorer. Dessa två aspekter av teori och praktik har utvecklats nästan helt oberoende av varandra. Det främsta skälet är utan tvekan att logiker är intresserade av frågor som är radikalt annorlunda än de som de tillämpade matematikerna och elektroingenjörerna främst sysslar med. Det kan dock inte undgå att framstå som ganska märkligt att ofta samma begrepp uttrycks med mycket olika termer i de två utvecklingarna.

— Wang 1954, 1957:63

Wang hoppades att hans tidning skulle "koppla ihop de två tillvägagångssätten". Minsky bekräftar faktiskt detta: "att den första formuleringen av Turing-maskinteorin i datorliknande modeller dyker upp i Wang (1957)" (Minsky 1967:200). Minsky fortsätter med att demonstrera Turing-ekvivalensen för en diskmaskin .

När det gäller minskningen av datorer till enkla Turing-likvärdiga modeller (och vice versa), är Minskys beteckning av Wang som "den första formuleringen" öppen för debatt. Medan både Minskys uppsats från 1961 och Wangs uppsats från 1957 citeras av Shepherdson och Sturgis (1963), citerar och sammanfattar de också de europeiska matematikerna Kaphenst (1959), Ershov (1959) och Péter (1958) arbete. Namnen på matematikerna Hermes (1954, 1955, 1961) och Kaphenst (1959) förekommer i bibliografierna för både Sheperdson-Sturgis (1963) och Elgot-Robinson (1961). Två andra namn av betydelse är de kanadensiska forskarna Melzak (1961) och Lambek (1961). För mycket mer se Turing-maskinmotsvarigheter ; referenser finns på registermaskinen .

Matematisk teori

Med denna kodning av handlingstabeller som strängar blir det i princip möjligt för Turing-maskiner att svara på frågor om beteendet hos andra Turing-maskiner. De flesta av dessa frågor är dock oavgjorda , vilket innebär att funktionen i fråga inte kan beräknas mekaniskt. Till exempel, problemet med att avgöra om en godtycklig Turing-maskin kommer att stanna på en viss ingång, eller på alla ingångar, känd som Halting-problemet , visade sig i allmänhet vara oavgjord i Turings originaltidning. Rice's teorem visar att alla icke-triviala frågor om resultatet från en Turing-maskin är oavgjorda.

En universell Turing-maskin kan beräkna vilken rekursiv funktion som helst , bestämma vilket rekursivt språk som helst och acceptera vilket rekursivt uppräknat språk som helst . Enligt Church–Turing-avhandlingen är de problem som kan lösas av en universell Turing-maskin exakt de problem som kan lösas med en algoritm eller en effektiv beräkningsmetod, för alla rimliga definitioner av dessa termer. Av dessa skäl fungerar en universell Turing-maskin som en standard att jämföra beräkningssystem mot, och ett system som kan simulera en universell Turing-maskin kallas Turing complete .

En abstrakt version av den universella Turing-maskinen är den universella funktionen , en beräkningsbar funktion som kan användas för att beräkna vilken annan beräkningsbar funktion som helst. UTM -satsen bevisar förekomsten av en sådan funktion.

Effektivitet

Utan förlust av allmänhet kan inmatningen av Turing-maskinen antas vara i alfabetet {0, 1}; vilket annat ändligt alfabet som helst kan kodas över {0, 1}. Beteendet hos en Turing-maskin M bestäms av dess övergångsfunktion. Den här funktionen kan också enkelt kodas som en sträng över alfabetet {0, 1}. Storleken på alfabetet av M , antalet band det har och storleken på tillståndsutrymmet kan härledas från övergångsfunktionens tabell. De särskiljande tillstånden och symbolerna kan identifieras genom sin position, t.ex. kan de två första tillstånden enligt konvention vara start- och stopptillstånd. Följaktligen kan varje Turing-maskin kodas som en sträng över alfabetet {0, 1}. Dessutom sammankallar vi att varje ogiltig kodning mappas till en trivial Turing-maskin som omedelbart stannar, och att varje Turing-maskin kan ha ett oändligt antal kodningar genom att utfylla kodningen med ett godtyckligt antal (säg) 1:or i slutet, precis som kommentarer arbeta i ett programmeringsspråk. Det borde inte vara någon överraskning att vi kan uppnå denna kodning med tanke på förekomsten av ett Gödel-tal och beräkningsekvivalens mellan Turing-maskiner och μ-rekursiva funktioner . På liknande sätt associerar vår konstruktion till varje binär sträng α , en Turing-maskin M _α .

Med utgångspunkt från ovanstående kodning, 1966 visade FC Hennie och RE Stearns att givet en Turing-maskin M _α som stannar på ingång x inom N steg, så finns det en multi-tape universell Turing-maskin som stannar på ingångarna α , x (given på olika band) i CN log N , där C är en maskinspecifik konstant som inte beror på längden på ingången x , men som beror på M :s alfabetstorlek, antal band och antal tillstånd. Detta är faktiskt en ${\displaystyle {\mathcal {O}}\left(N\log {N}\right)}-$ simulering, med hjälp av Donald Knuths Big O-notation . Motsvarande resultat för rymdkomplexitet snarare än tidskomplexitet är att vi kan simulera på ett sätt som använder som mest CN- celler i vilket skede av beräkningen som helst, en ${\mathcal {O}}(N )$ simulering.

Minsta maskiner

När Alan Turing kom på idén om en universell maskin hade han i åtanke den enklaste beräkningsmodellen som var kraftfull nog att beräkna alla möjliga funktioner som kan beräknas. Claude Shannon ställde först uttryckligen frågan om att hitta den minsta möjliga universella Turing-maskinen 1956. Han visade att två symboler var tillräckliga så länge som tillräckligt många tillstånd användes (eller vice versa), och att det alltid var möjligt att byta tillstånd mot symboler. Han visade också att ingen universell Turing-maskin för en stat kunde existera.

Marvin Minsky upptäckte en 7-stats 4-symbol universell Turing-maskin 1962 med 2-tagssystem . Andra små universella Turing-maskiner har sedan dess hittats av Yurii Rogozhin och andra genom att utöka detta tillvägagångssätt för simulering av taggsystem. Om vi betecknar med ( m , n ) klassen av UTM med m tillstånd och n symboler har följande tupler hittats: (15, 2), (9, 3), (6, 4), (5, 5), (4, 6), (3, 9) och (2, 18). Rogozhins (4, 6) maskin använder endast 22 instruktioner, och ingen standard UTM med mindre beskrivningskomplexitet är känd.

Att generalisera den vanliga Turing-maskinmodellen tillåter dock ännu mindre UTM. En sådan generalisering är att tillåta ett oändligt upprepat ord på den ena eller båda sidorna av Turingmaskinens ingång, och därmed utöka definitionen av universalitet och känd som "halvsvag" respektive "svag" universalitet. Små svagt universella Turing-maskiner som simulerar Rule 110 cellulära automaten har getts för (6, 2), (3, 3) och (2, 4) tillståndssymbolpar. Beviset på universalitet för Wolframs 2-tillstånd 3-symbol Turing-maskin utökar begreppet svag universalitet ytterligare genom att tillåta vissa icke-periodiska initiala konfigurationer. Andra varianter av den vanliga Turing-maskinmodellen som ger små UTM:er inkluderar maskiner med flera tejper eller tejper av flera dimensioner, och maskiner kopplade med en finit automat .

Maskiner utan interna tillstånd

Om flera huvuden är tillåtna på en Turing-maskin krävs inga interna tillstånd; som "tillstånd" kan kodas i bandet. Tänk till exempel på en tejp med 6 färger: 0, 1, 2, 0A, 1A, 2A. Tänk på ett band som 0,0,1,2,2A,0,2,1 där en 3-hövdad Turing-maskin är placerad över trippeln (2,2A,0). Reglerna omvandlar sedan valfri trippel till en annan trippel och flyttar 3-huvudena åt vänster eller höger. Till exempel kan reglerna konvertera (2,2A,0) till (2,1,0) och flytta huvudet åt vänster. Således fungerar maskinen i det här exemplet som en 3-färgs Turing-maskin med interna tillstånd A och B (representerade utan bokstav). Fallet för en 2-hövdad Turing-maskin är väldigt lika. Således kan en 2-hövdad Turing-maskin vara Universal med 6 färger. Det är inte känt vad det minsta antalet färger som behövs för en flerhövdad Turing-maskin är eller om en 2-färgad Universal Turing-maskin är möjlig med flera huvuden. Det betyder också att omskrivningsregler är Turing kompletta eftersom trippelreglerna är likvärdiga med omskrivningsregler. Om man förlänger tejpen till två dimensioner med ett huvud som samplar en bokstav och dess 8 grannar, behövs bara 2 färger, eftersom till exempel en färg kan kodas i ett vertikalt trippelmönster som 110.

Exempel på universell maskinkodning

För dem som skulle anta utmaningen att designa en UTM exakt som Turing specificerade, se artikeln av Davies i Copeland (2004:103ff). Davies korrigerar felen i originalet och visar hur en provkörning skulle se ut. Han säger sig ha framgångsrikt kört en (något förenklad) simulering.

Följande exempel är hämtat från Turing (1936). För mer om detta exempel, se Turing-maskinexempel .

Turing använde sju symboler { A, C, D, R, L, N, ; } för att koda varje 5-tupel; som beskrivs i artikeln Turing-maskin är hans 5-tuplar endast av typerna N1, N2 och N3. Numret för varje "m-konfiguration" (instruktion, tillstånd) representeras av "D" följt av en unär sträng av A, t.ex. "q3" = DAAA. På liknande sätt kodar han symbolerna tomma som "D", symbolen "0" som "DC", symbolen "1" som DCC, etc. Symbolerna "R", "L" och "N" finns kvar i befintligt skick.

Efter kodning "sammansätts" varje 5-tupel till en sträng i den ordning som visas i följande tabell:

Aktuell m-konfiguration	Tejpsymbol	Utskriftsdrift	Tape-motion	Slutlig m-konfiguration	Aktuell m-konfigurationskod	Tejpa symbolkod	Utskriftskod	Tape-motion-kod	Slutlig m-konfigurationskod	5-tuppel monterad kod
q1	tom	P0	R	q2	DA	D	DC	R	DAA	DADDCRDAA
q2	tom	E	R	q3	DAA	D	D	R	DAAA	DAADDRDAAA
q3	tom	P1	R	q4	DAAA	D	DCC	R	DAAAA	DAAADDCCRDAAAA
q4	tom	E	R	q1	DAAAA	D	D	R	DA	DAAAADDRDA

Slutligen strängas koderna för alla fyra 5-tuplarna ihop till en kod som startas av ";" och separerade med ";" dvs:

; DADDCRDAA ; DAADDRDAAA ; DAAADDCCRDAAAA ; DAAAADDRDA

Denna kod placerade han på alternativa rutor - "F-rutorna" - och lämnade "E-rutorna" (de som kan raderas) tomma. Den slutliga monteringen av koden på bandet för U-maskinen består av att placera två specialsymboler ("e") efter varandra, sedan separeras koden på alternativa rutor, och sist dubbelkolonsymbolen " :: " (mellanrum visas här med "." för tydlighetens skull):

ee. ; .DADDCRDAA ; .DAADDRDAAA ; .DAAADDCCRDAAAA ; .DAAAADDRDA :: ......

U-maskinens handlingstabell (tillståndsövergångstabell) ansvarar för att avkoda symbolerna. Turings actiontabell håller reda på sin plats med markörerna "u", "v", "x", "y", "z" genom att placera dem i "E-rutor" till höger om "den markerade symbolen" – till exempel , för att markera den aktuella instruktionen z placeras till höger om ";" x behåller platsen med avseende på den aktuella "m-konfigurationen" DAA. U-maskinens actionbord kommer att skjuta runt dessa symboler (radera dem och placera dem på olika platser) allt eftersom beräkningen fortskrider:

ee. ; .DADDCRDAA ; z D.AA x D.DRDAAA ; .DAAADDCCRDAAAA ; .DAAAADDRDA :: ......

Turings actionbord för sin U-maskin är väldigt involverat.

Ett antal andra kommentatorer (särskilt Penrose 1989 ) ger exempel på sätt att koda instruktioner för Universal-maskinen. Precis som Penrose använder de flesta kommentatorer endast binära symboler, dvs endast symbolerna { 0, 1 } eller { blank, mark | }. Penrose går längre och skriver ut hela sin U-maskinkod (Penrose 1989:71–73). Han hävdar att det verkligen är en U-maskinkod, ett enormt antal som sträcker sig över nästan 2 helsidor med 1:or och 0:or. För läsare som är intresserade av enklare kodningar för Post–Turing-maskinen kan diskussionen om Davis i Steen (Steen 1980:251ff) vara användbar.

Asperti och Ricciotti beskrev en multi-tape UTM definierad genom att komponera elementära maskiner med mycket enkel semantik, snarare än att explicit ge sin fullständiga handlingstabell. Detta tillvägagångssätt var tillräckligt modulärt för att tillåta dem att formellt bevisa riktigheten av maskinen i Matita proof assistant.

Programmering av Turing-maskiner

Olika språk på högre nivå är designade för att kompileras till en Turing-maskin. Exempel inkluderar Laconic och Turing Machine Descriptor.

Se även

Alternerande Turing-maskin
Von Neumann universell konstruktör – ett försök att bygga en självreplikerande Turing-maskin
Kleenes T-predikat – ett liknande koncept för µ-rekursiva funktioner
Turing fullständighet

Allmänna referenser

Arora, Sanjeev; Barak, Boaz (2009). Complexity Theory: A Modern Approach . Cambridge University Press. ISBN 978-0-521-42426-4 . avsnitt 1.4, "Maskiner som strängar och den universella Turing-maskinen" och 1.7, "Proof of theorem 1.9"

Original papper

Turing, AM (1936). "På beräkningsbara nummer, med en applikation till Entscheidungsproblemet" ( PDF) .

Seminära papper

Hennie, FC; Stearns, RE (1966). "Tvåbandssimulering av Turingmaskiner med flera band". Journal of the ACM . 13 (4): 533. doi : 10.1145/321356.321362 . S2CID 2347143 .

Genomförande

Kamvysselis (Kellis), Manolis (1999). "Scheme Implementation of a Universal Turing Machine" . Självpublicerad .

Formell verifiering

Asperti, Andrea; Ricciotti, Wilmer (2015). "En formalisering av Turing-maskiner med flera band" (PDF) . Teoretisk datavetenskap . Elsevier. 603 : 23–42. doi : 10.1016/j.tcs.2015.07.013 . ISSN 0304-3975 .

Andra referenser

Copeland, Jack , red. (2004), The Essential Turing: Seminal Writings in Computing, Logic, Philosophy, Artificial Intelligence, and Artificial Life plus The Secrets of Enigma , Oxford UK: Oxford University Press, ISBN 0-19-825079-7
Davis, Martin (1980), "What is Computation?", i Steen, Lynn Arthur (red.), Mathematics Today: Twelve Informal Essays , New York: Vintage Books (Random House), ISBN 978-0-394-74503- 9 .
Davis, Martin (2000), Engines of Logic: Mathematicians and the origin of the Computer (1:a upplagan), New York NY: WW Norton & Company, ISBN 0-393-32229-7 , (pb.)
Goldstine, Herman H.; von Neumann, John. Planering och kodning av problemen för ett elektroniskt datorinstrument . Institutet för avancerade studier (Rep. 1947 utg.). Princeton. Bell, C. Gordon; Newell, Allen (1971). Computer Structures: Readings and Examples (Reprinted ed.). New York: McGraw-Hill Book Company. s. 92–119 . ISBN 0-07-004357-4 .
Herken, Rolf (1995), The Universal Turing Machine – A Half-Century Survey , Springer Verlag, ISBN 3-211-82637-8
Knuth, Donald E. (1973), The Art of Computer Programming , vol. 1/Fundamental Algorithms (andra upplagan), Addison-Wesley Publishing Company Den första av Knuths serie med tre texter.
Kudlek, Manfred; Rogozhin, Yurii (2002), "En universell Turing-maskin med 3 tillstånd och 9 symboler", i Werner Kuich; Grzegorz Rozenberg; Arto Salomaa (red.), Developments in Language Theory: 5th International Conference, DLT 2001 Wien, Österrike, 16–21 juli 2001, Revised Papers , Lecture Notes in Computer Science, vol. 2295, Springer, s. 311–318, doi : 10.1007/3-540-46011-x_27 , ISBN 978-3-540-43453-5
Minsky, Marvin (1962), "Size and Structure of Universal Turing Machines using Tag Systems, Rekursiv funktionsteori", Proc. Symp. Pure Mathematics , Providence RI: American Mathematical Society, 5 : 229–238, doi : 10.1090/pspum/005/0142452
Neary, Turlough; Woods, Damien (2009), "Fyra små universella turingmaskiner" (PDF) , Fundamenta Informaticae , 91 (1): 123–144, doi : 10.3233/FI-2009-0036
Neary, Turlough; Woods, Damien (2009b), "Small Weakly Universal Turing Machines", 17th International Symposium on Fundamentals of Computation Theory , Lecture Notes in Computer Science, vol. 5699, Springer, s. 262–273
Penrose, Roger (1989), The Emperor's New Mind , Oxford UK: Oxford University Press, ISBN 0-19-851973-7 , (hc.), (pb.)
Rogozhin, Yurii (1996), "Small Universal Turing Machines", Theoretical Computer Science , 168 (2): 215–240, doi : 10.1016/S0304-3975(96)00077-1
Shannon, Claude (1956), "A Universal Turing Machine with Two Internal States", Automata Studies , Princeton, NJ: Princeton University Press, s. 157–165
Turing, AM (1936), "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society , 2, vol. 42, s. 230–65, doi : 10.1112/plms/s2-42.1.230 , S2CID 73712
Turing, AM (1938), "On Computable Numbers, with an Application to the Entscheidungsproblem: A correction", Proceedings of the London Mathematical Society , 2 (publicerad 1937), vol. 43, nr. 6, s. 544–6, doi : 10.1112/plms/s2-43.6.544 ) Davis, Martin, ed. (1965). The Unecidable (Reprint ed.). Hewlett, NY: Raven Press. s. 115–154. med korrigeringar av Turings UTM av Emil Post jfr fotnot 11 s:299

externa länkar

Smith, Alvy Ray. "Ett visitkort Universal Turing Machine" (PDF) . Hämtad 2 januari 2020 .