Turing Machine -program, även om de konceptuellt enkelt kan visa upp flera vanliga funktioner beroende på uppgiften de är utformade för att utföra. Dessa funktioner finns inte nödvändigtvis i * varje * Turing Machine -program, men de visas ofta:
1. Statliga övergångar: Detta är den grundläggande byggstenen. Programmet dikterar hur maskinen övergår mellan tillstånd baserat på det aktuella tillståndet och symbolen som läses från bandet. Dessa övergångar involverar ofta:
* läser en symbol: Maskinen läser symbolen under huvudet.
* Skriva en symbol: Maskinen skriver en ny symbol till bandet och skriver över den föregående.
* Flytta huvudet: Maskinen flyttar huvudet ett läge till vänster eller höger.
* Ändra tillstånd: Maskinen övergår till ett nytt tillstånd.
2. Stater: Dessa representerar olika beräkningsstadier. Vanliga stater inkluderar:
* starttillstånd: Maskinens ursprungliga tillstånd.
* Acceptera tillstånd: Tillstånd som indikerar framgångsrik beräkning. Att nå ett accepterande tillstånd stoppar maskinen.
* Avvisande tillstånd: Tillstånd som indikerar misslyckad beräkning (t.ex. ingången var inte på det språk som TM känner igen).
* Mellanstater: Stater som representerar olika steg i algoritmen. Dessa är avgörande för komplexa beräkningar.
3. Bandmanipulation: Betydande delar av programmet involverar manipulering av bandet:
* Marking: Använda speciella symboler för att markera positioner på bandet, ofta för att hålla reda på framsteg eller mellanresultat.
* räkning: Med hjälp av sekvenser av symboler för att representera siffror eller mängder.
* Sökning: Flytta huvudet fram och tillbaka för att söka efter specifika symboler eller mönster.
* Kopiering: Duplicerar delar av bandet.
4. Slingor och subroutiner (implicit): Även om Turing-maskiner inte har uttryckliga slingor eller subroutiner på samma sätt som programmeringsspråk på högre nivå, kan deras beteende effektivt implementera dem genom noggrant utformade tillståndsövergångar. Maskinen kan upprepade gånger cykla genom en uppsättning tillstånd för att utföra en specifik operation, efterlikna en slinga eller övergång till en specifik uppsättning tillstånd för att utföra en underupptag innan du återvänder till huvudberäkningsflödet.
5. Ändlig statskontroll: Antalet stater är alltid ändligt, vilket återspeglar programmets ändliga karaktär. Komplexiteten hos en Turing -maskin bestäms till stor del av antalet tillstånd och intrikatet i tillståndsövergångarna.
6. Determinism/icke-determinism: Programmet kan vara deterministiskt (en unik övergång för varje statssymbolkombination) eller icke-deterministiska (flera möjliga övergångar). Icke-deterministiska maskiner kan utforska flera beräkningsvägar samtidigt.
Det är viktigt att komma ihåg att Turing -maskiner är abstrakta modeller för beräkning. Faktiska implementeringar kommer att variera, men dessa funktioner representerar de grundläggande konceptuella komponenterna i ett Turing -maskinprogram. De specifika detaljerna i ett program kommer att bero kraftigt på den specifika beräkningen som det är utformat för att utföra.
