Voorbeelden van Turingmachines - Turing machine examples
Hieronder volgen voorbeelden ter aanvulling van het artikel Turingmachine .
Het allereerste voorbeeld van Turing
De volgende tabel is Turing's allereerste voorbeeld ( Alan Turing 1937):
- "1. Er kan een machine worden geconstrueerd om de reeks te berekenen 0 1 0 1 0 1..." (0 <blanco> 1 <blanco> 0...) ( Onbeslisbaar p. 119)
| Configuratie | Gedrag | ||
|---|---|---|---|
| m-configuratie (staat) |
Band symbool | Bandbewerkingen | Definitieve m-configuratie (staat) |
| B | blank | P0, R | C |
| C | blank | R | e |
| e | blank | P1, R | F |
| F | blank | R | B |
Met betrekking tot welke acties de machine daadwerkelijk doet, stelt Turing (1936) ( Undecidable p. 121) het volgende:
- "Deze [voorbeeld] tabel (en alle volgende tabellen van dezelfde soort) moet worden begrepen dat voor een configuratie beschreven in de eerste twee kolommen de bewerkingen in de derde kolom achtereenvolgens worden uitgevoerd, en de machine gaat dan over in de m-configuratie in de laatste kolom." (Onbeslisbaar p. 121)
Hij maakt dit heel duidelijk wanneer hij de bovenstaande tabel reduceert tot een enkele instructie genaamd "b" ( Onbeslisbaar p. 120), maar zijn instructie bestaat uit 3 regels. Instructie "b" heeft drie verschillende symboolmogelijkheden {Geen, 0, 1}. Elke mogelijkheid wordt gevolgd door een reeks acties totdat we bij de meest rechtse kolom komen, waar de uiteindelijke m-configuratie "b" is:
| Huidige m-configuratie (instructie) | Band symbool | Operaties op de band | Definitieve m-configuratie (instructie) |
|---|---|---|---|
| B | Geen | P0 | B |
| B | 0 | R, R, P1 | B |
| B | 1 | R, R, P0 | B |
Zoals opgemerkt door een aantal commentatoren, waaronder Turing (1937) zelf (bijv. Post (1936), Post (1947), Kleene (1952), Wang (1954)), zijn de Turing-instructies niet atomair - verdere vereenvoudigingen van het model kunnen worden gemaakt zonder de rekenkracht te verminderen; zie meer bij Post-Turing-machine .
Zoals vermeld in het artikel Turing machine , stelde Turing voor om zijn tafel verder te verstuiven door slechts een enkele print/wissen toe te staan gevolgd door een enkele bandbeweging L/R/N. Hij geeft ons dit voorbeeld van het eerste kleine tafeltje dat geconverteerd is ( Onbeslisbaar , p. 127):
| Huidige m-configuratie (Turing-status) | Band symbool | Print-operatie | Tape-beweging | Definitieve m-configuratie (Turing-status) |
|---|---|---|---|---|
| q 1 | blank | P0 | R | q 2 |
| q 2 | blank | P blanco, dwz E | R | q 3 |
| q 3 | blank | P1 | R | q 4 |
| q 4 | blank | P blanco, dwz E | R | q 1 |
Turing's verklaring impliceert nog steeds vijf atomaire operaties. Bij een gegeven instructie (m-configuratie) de machine:
- let op het tape-symbool onder het hoofd
- op basis van het waargenomen symbool gaat naar de juiste instructiereeks om te gebruiken
- drukt symbool S j af of wist of doet niets
- beweegt de band naar links, rechts of helemaal niet
- gaat naar de laatste m-configuratie voor dat symbool
Omdat de acties van een Turing-machine niet atomair zijn, moet een simulatie van de machine elke 5-tupel verstuiven tot een reeks eenvoudigere acties. Een mogelijkheid - gebruikt in de volgende voorbeelden van "gedrag" van zijn machine - is als volgt:
- (q i ) Test het bandsymbool onder de kop: als het symbool S 0 is, ga naar q i .01, als symbool S 1 naar q i .11 gaat, als symbool S 2 naar q i .21 gaat, enz.
- (q i .01) print symbool S j 0 of wis of doe niets ga dan naar q i .02
- (q i .02) verplaats de band naar links of rechts of helemaal niet ga dan naar qm0
- (q i .11) druk symbool S j 1 af of wis of doe niets ga dan naar q i .12
- (q i .12) verplaats de band naar links of rechts of helemaal niet ga dan naar qm1
- (q i .21) druk symbool S j 2 af of wis of doe niets ga dan naar q i .22
- (q i .22) verplaats de band naar links of naar rechts of helemaal niet ga dan naar qm2
- (etc - alle symbolen moeten worden verantwoord)
Zogenaamde "canonieke" eindige-toestandsmachines doen de symbooltests "parallel"; zie meer bij microprogrammering .
In het volgende voorbeeld van wat de machine doet, zullen we enkele eigenaardigheden van Turing's modellen opmerken:
- "De conventie om de cijfers alleen op alternatieve vierkanten te schrijven is erg handig: ik zal er altijd gebruik van maken." (Onbeslisbaar p. 121)
Dus bij het afdrukken slaat hij elk ander vierkant over. De opgedrukte vierkanten worden F-vierkanten genoemd; de lege vierkanten ertussen kunnen worden gebruikt voor "markeringen" en worden "E-vierkanten" genoemd zoals in "aanvaardbaar om te wissen". De F-vierkanten zijn op hun beurt zijn "Figuurvierkanten" en zullen alleen de symbolen 1 of 0 dragen - symbolen die hij "cijfers" noemde (zoals in "binaire getallen").
In dit voorbeeld begint de tape "blanco" en worden vervolgens de "figuren" erop afgedrukt. Kortheidshalve worden hier alleen de TABLE-statussen getoond:
Dezelfde "run" met alle tussentijdse tape-afdrukken en bewegingen wordt hier getoond:
Een nauwkeurige blik op de tabel onthult bepaalde problemen met Turing's eigen voorbeeld - niet alle symbolen worden verklaard.
Stel bijvoorbeeld dat zijn band aanvankelijk niet blanco was. Wat zou er gebeuren? De Turingmachine zou andere waarden lezen dan de beoogde waarden.
Een kopie-subroutine
Dit is een zeer belangrijke subroutine die wordt gebruikt in de "vermenigvuldigen"-routine.
De Turing-machine van het voorbeeld verwerkt een reeks van nullen en enen, waarbij 0 wordt weergegeven door het blanco symbool. Het is zijn taak om elke reeks enen die op de band worden aangetroffen te verdubbelen door er een 0 tussen te schrijven. Als het hoofd bijvoorbeeld "111" leest, zal het een 0 schrijven en vervolgens "111". De uitvoer is "1110111".
Om zijn taak te volbrengen, heeft deze Turing-machine slechts 5 bedrijfstoestanden nodig, die {s 1 , s 2 , s 3 , s 4 , s 5 } worden genoemd. Elke staat voert 4 acties uit:
- Lees het symbool onder de kop
- Schrijf het uitvoersymbool dat is bepaald door de staat
- Verplaats de band naar links of naar rechts, bepaald door de staat
- Schakel over naar de volgende staat bepaald door de huidige staat:
Een "run" van de machinereeksen door 16 machineconfiguraties (ook wel Turing-staten genoemd):
Het gedrag van deze machine kan worden beschreven als een lus: het begint in s 1 , vervangt de eerste 1 door een 0 en gebruikt vervolgens s 2 om naar rechts te gaan, waarbij 1s wordt overgeslagen en de eerste 0 wordt aangetroffen. s 3 slaat dan de volgende reeks enen over (aanvankelijk zijn er geen) en vervangt de eerste 0 die het vindt door een 1. s 4 gaat terug naar links, slaat 1s over totdat het een 0 vindt en schakelt over naar s 5 . s 5 gaat dan naar links en slaat 1s over totdat het de 0 vindt die oorspronkelijk door s 1 is geschreven .
Het vervangt die 0 door een 1, beweegt één positie naar rechts en voert opnieuw s 1 in voor nog een ronde van de lus.
Dit gaat door totdat s 1 een 0 vindt (dit is de 0 in het midden van de twee reeksen van 1s), waarna de machine stopt.
Alternatieve beschrijving
Een andere beschrijving ziet het probleem als het bijhouden van hoeveel "1"en er zijn. We kunnen niet één toestand gebruiken voor elk mogelijk getal (een toestand voor elk van 0,1,2,3,4,5,6 enz.), omdat we dan oneindige toestanden nodig hebben om alle natuurlijke getallen weer te geven, en de state machine is eindig - we zullen dit op de een of andere manier moeten volgen met behulp van de tape.
De basismanier waarop het werkt, is door elke "1" naar de andere kant te kopiëren, door heen en weer te gaan - het is intelligent genoeg om te onthouden op welk deel van de reis het zich bevindt. In meer detail draagt het elke "1" naar de andere kant, door de scheidende "0" in het midden te herkennen en de "0" aan de andere kant te herkennen om te weten dat het einde is bereikt. Het komt terug met dezelfde methode, waarbij de middelste "0" wordt gedetecteerd en vervolgens de "0" aan de originele kant. Deze "0" aan de originele kant is de sleutel tot de puzzel van hoe het het aantal enen bijhoudt.
De truc is dat voordat het de "1" draagt, het dat cijfer markeert als "genomen" door het te vervangen door een "0". Wanneer het terugkeert, vult het die "0" weer in met een "1", gaat dan verder naar de volgende , markeert het met een "0" en herhaalt de cyclus, draagt die "1" over enzovoort. Bij elke heen- en terugreis komt de markering "0" een stap dichter bij het midden . Dit is hoe het bijhoudt hoeveel "1"'s het heeft overgenomen.
Wanneer het terugkeert, ziet de markering "0" eruit als het einde van de verzameling "1"-en - alle "1"-en die al zijn overgenomen, zijn er onzichtbaar voor (aan de andere kant van de markering "0" ) en zo is het alsof het werkt aan een (N-1) getal van "1"s - vergelijkbaar met een bewijs door wiskundige inductie .
Een volledige "run" met de resultaten van de tussenliggende "bewegingen". Om het beter te zien, klik op de afbeelding en klik vervolgens op de download met hogere resolutie:
3-staten Bezige Bever
De volgende Turing-instructiestabel is afgeleid van Peterson (1988) pagina 198, figuur 7.15. Peterson beweegt het hoofd; in het volgende model beweegt de band.
| Band symbool | Huidige staat A | Huidige staat B | Huidige staat C | ||||||
|---|---|---|---|---|---|---|---|---|---|
| Schrijf symbool | Verplaats band | Volgende staat | Schrijf symbool | Verplaats band | Volgende staat | Schrijf symbool | Verplaats band | Volgende staat | |
| 0 | 1 | R | B | 1 | L | EEN | 1 | L | B |
| 1 | 1 | L | C | 1 | R | B | 1 | N | HALT |
De "toestand"-tekening van de 3-toestanden-bezige bever toont de interne reeksen van gebeurtenissen die nodig zijn om "de toestand" daadwerkelijk uit te voeren. Zoals hierboven opgemerkt, maakt Turing (1937) het volkomen duidelijk dat dit de juiste interpretatie is van de 5-tupels die de instructie beschrijven ( Undecidable , p. 119). Voor meer informatie over de verneveling van Turing 5-tupels zie Post-Turing machine :
De volgende tabel toont de "gecomprimeerde" run - alleen de Turing-statussen:
De volledige "run" van de 3-state drukke bever. De resulterende Turing-toestanden (wat Turing de "m-configuraties" - "machine-configuraties" noemde) worden grijs gemarkeerd weergegeven in kolom A, en ook onder de instructies van de machine (kolommen AF-AU)):
Referenties
Voor volledige referenties zie Turingmachine .
- Ivars Peterson, 1988, The Mathematical Tourist: Snapshots of Modern Mathematics , WH Freeman and Company, New York, ISBN 0-7167-2064-7 (pbk.). Turingmachines worden beschreven op pp. 194ff, het drukke bevervoorbeeld staat in figuur 7.15 op pagina 198.
- Martin Davis redacteur, 1965 The Undecidable: Basic Papers on Undecidable Propositions, onoplosbare problemen en berekenbare functies , Raven Press, New York, geen ISBN, geen kaartcatalogusnummer.
- Alan Turing, 1937, On Computable Numbers, with an Application to the Entscheidungsproblem , pp. 116ff, met kort commentaar door Davis op pagina 115.
- Alan Turing, 1937, op berekenbare getallen, met een toepassing op het Entscheidungsprobleem. Een correctie , p. 152-154.
