Turing Machine -Programme, obwohl sie konzeptionell einfach sind, können je nach Aufgabe, für die sie ausgeführt wurden, mehrere gängige Funktionen aufweisen. Diese Funktionen sind nicht unbedingt in * jedem * Turing -Maschinenprogramm vorhanden, treten jedoch häufig auf:
1. Zustandsübergänge: Dies ist der grundlegende Baustein. Das Programm bestimmt, wie sich die Maschine zwischen den Zuständen basierend auf dem aktuellen Zustand und dem aus dem Band gelesenen Symbol übergeht. Diese Übergänge beinhalten oft:
* Ein Symbol lesen: Die Maschine liest das Symbol unter dem Kopf.
* ein Symbol schreiben: Die Maschine schreibt ein neues Symbol in das Band und überschreibt das vorherige.
* den Kopf bewegen: Die Maschine bewegt den Kopf eine Position nach links oder rechts.
* Status ändern: Die Maschine übergeht in einen neuen Zustand.
2. Zustände: Diese repräsentieren verschiedene Berechnungsstadien. Gemeinsame Zustände umfassen:
* Startzustand: Der Anfangszustand der Maschine.
* Zustand akzeptieren (s): Zustand (en), die auf eine erfolgreiche Berechnung hinweisen. Das Erreichen eines Annahmezustands hält die Maschine an.
* Status ablehnen (en): Zustand (en), die eine erfolglose Berechnung hinweisen (z. B. war die Eingabe nicht in der Sprache, die der TM erkennt).
* Zwischenzustände: Zustände, die verschiedene Schritte im Algorithmus darstellen. Diese sind für komplexe Berechnungen von entscheidender Bedeutung.
3. Bandmanipulation: Wichtige Teile des Programms umfassen das Manipulieren des Bandes:
* Markierung: Verwenden von speziellen Symbolen, um Positionen auf dem Band zu markieren, um häufig den Fortschritt oder die Zwischenergebnisse zu verfolgen.
* Zählen: Verwenden von Sequenzen von Symbolen zur Darstellung von Zahlen oder Mengen.
* Suche: Bewegen Sie den Kopf hin und her, um nach bestimmten Symbolen oder Mustern zu suchen.
* Kopieren: Duplizierende Abschnitte des Bandes.
4. Schleifen und Unterprogramme (implizit): Während Turing-Maschinen keine expliziten Schleifen oder Unterroutinen auf die gleiche Weise wie Programmiersprachen auf höherer Ebene haben, kann ihr Verhalten sie effektiv durch sorgfältig gestaltete staatliche Übergänge implementieren. Die Maschine kann wiederholt eine Reihe von Zuständen durchführen, um einen bestimmten Betrieb auszuführen, eine Schleife nachzuahmen oder zu einem bestimmten Satz von Zuständen zu übergehen, um eine Untertaskente durchzuführen, bevor er zum Hauptberechnungsfluss zurückkehrt.
5. Finite -Status -Kontrolle: Die Anzahl der Staaten ist immer endlich und spiegelt die endliche Natur des Programms selbst wider. Die Komplexität einer Turing -Maschine wird größtenteils durch die Anzahl der Zustände und die Komplexität der Zustandsübergänge bestimmt.
6. Determinismus/Nichtdeterminismus: Das Programm kann deterministisch sein (ein einzigartiger Übergang für jede Zustandsymbolkombination) oder nicht deterministisch (mehrere mögliche Übergänge). Nichtdeterministische Maschinen können mehrere Berechnungspfade gleichzeitig untersuchen.
Es ist wichtig, sich daran zu erinnern, dass Turing -Maschinen abstrakte Berechnungsmodelle sind. Die tatsächlichen Implementierungen variieren jedoch, diese Merkmale stellen jedoch die konzeptionellen Komponenten eines Turing Machine -Programms dar. Die spezifischen Details eines Programms hängen stark von der spezifischen Berechnung ab, für die es ausgeführt werden soll.
