Welche Arten von Turingmaschinen gibt es? Beschreibung der Turingmaschine. Turingmaschine, die auf einem halbunendlichen Band läuft

Die Turing-Maschine ist eine der faszinierendsten und aufregendsten intellektuellen Entdeckungen des 20. Jahrhunderts. Es handelt sich um ein einfaches und nützliches abstraktes Computermodell (Computer und Digital), das allgemein genug ist, um jede Computeraufgabe zu implementieren. Dank seiner einfachen Beschreibung und mathematischen Analyse bildet es die Grundlage der theoretischen Informatik. Diese Forschung führte zu einem besseren Verständnis des digitalen Rechnens und der Analysis, einschließlich der Erkenntnis, dass es einige Computerprobleme gab, die auf Großrechnern nicht gelöst werden konnten.

Was ist das und wer hat es geschaffen?

Alan Turing wollte das primitivste Modell eines mechanischen Geräts beschreiben, das die gleichen Grundfunktionen wie ein Computer hätte. Turing beschrieb die Maschine erstmals 1936 in einem Artikel „Über berechenbare Zahlen mit einer Anwendung auf das Lösbarkeitsproblem“, der in den Proceedings der London Mathematical Society erschien.

Eine Turing-Maschine ist ein Computergerät, das aus einem Lese-/Schreibkopf (oder „Scanner“) besteht, durch den ein Papierband läuft. Das Band ist in Quadrate unterteilt, von denen jedes ein einzelnes Symbol trägt – „0“ oder „1“. Der Zweck des Mechanismus besteht darin, dass er sowohl als Eingabe- und Ausgabemittel als auch als Arbeitsspeicher zum Speichern der Ergebnisse von Zwischenstufen der Berechnungen fungiert.

Woraus besteht das Gerät?

Jede dieser Maschinen besteht aus zwei Komponenten:

1. Unbegrenztes Futter. Es ist in beide Richtungen unendlich und in Zellen unterteilt.
2. Automatisch - gesteuertes Programm, Scannerkopf zum Lesen und Schreiben von Daten. Es kann sich jederzeit in einem von vielen Zuständen befinden.

Jede Maschine verbindet zwei endliche Datenreihen: ein Alphabet eingehender Symbole A = (a0, a1, ..., am) und ein Alphabet von Zuständen Q = (q0, q1, ..., qp). Der Zustand q0 heißt passiv. Es wird angenommen, dass das Gerät seine Arbeit beendet, wenn es darauf trifft. Der Zustand q1 heißt initial – die Maschine beginnt mit ihren Berechnungen, während sie sich in ihr befindet. Das eingegebene Wort befindet sich auf dem Band, ein Buchstabe hintereinander an jeder Position. Auf beiden Seiten davon gibt es nur leere Zellen.

Wie der Mechanismus funktioniert

Eine Turing-Maschine unterscheidet sich grundlegend von Computergeräten: Ihr Speichergerät verfügt über ein Endlosband, während bei digitalen Geräten ein solches Gerät über einen Streifen einer bestimmten Länge verfügt. Jede Aufgabenklasse wird von nur einer gebauten Turingmaschine gelöst. Probleme anderer Art erfordern das Schreiben eines neuen Algorithmus.

Da sich das Steuergerät in einem Zustand befindet, kann es sich entlang des Bandes in jede Richtung bewegen. Es schreibt die Zeichen eines endlichen Alphabets in Zellen und liest sie aus. Beim Verschieben wird ein leeres Element zugewiesen und füllt Positionen, die keine Eingabedaten enthalten. Der Turing-Maschinen-Algorithmus bestimmt die Übergangsregeln für das Steuergerät. Sie stellen dem Lese-/Schreibkopf die folgenden Parameter ein: Schreiben eines neuen Zeichens in eine Zelle, Übergang in einen neuen Zustand, Bewegung nach links oder rechts entlang des Bandes.

Eigenschaften des Mechanismus

Die Turing-Maschine verfügt wie andere Computersysteme über inhärente Merkmale, die den Eigenschaften von Algorithmen ähneln:

1. Diskretion. Die digitale Maschine geht erst zum nächsten Schritt n+1 über, nachdem der vorherige abgeschlossen ist. Jeder ausgeführte Schritt weist zu, was n+1 sein wird.
2. Klarheit. Das Gerät führt nur eine Aktion für eine Zelle aus. Es gibt ein Zeichen aus dem Alphabet ein und führt eine Bewegung aus: nach links oder rechts.
3. Determinismus. Jede Position im Mechanismus entspricht einer einzelnen Option zur Ausführung eines bestimmten Schemas, und in jeder Phase sind die Aktionen und die Reihenfolge ihrer Ausführung eindeutig.
4. Produktivität. Das genaue Ergebnis für jede Stufe wird von einer Turingmaschine ermittelt. Das Programm führt den Algorithmus aus und geht in einer endlichen Anzahl von Schritten zum Zustand q0.
5. Massencharakter. Jedes Gerät wird über die im Alphabet enthaltenen gültigen Wörter definiert.

Funktionen einer Turingmaschine

Bei der Lösung von Algorithmen ist häufig eine Funktionsimplementierung erforderlich. Abhängig von der Möglichkeit, eine Kette zur Berechnung zu schreiben, wird eine Funktion als algorithmisch lösbar oder unentscheidbar bezeichnet. Als Menge natürlicher oder rationaler Zahlen, Wörter in einem endlichen Alphabet N für die Maschine, wird die Folge der Menge B betrachtet – Wörter innerhalb des Binärcode-Alphabets B = (0,1). Außerdem berücksichtigt das Berechnungsergebnis den „undefinierten“ Wert, der auftritt, wenn der Algorithmus einfriert. Zur Umsetzung der Funktion ist es wichtig, im finalen Alphabet über eine formale Sprache zu verfügen und das Problem der Erkennung korrekter Beschreibungen zu lösen.

Geräteprogramm

Programme für den Turing-Mechanismus werden in Tabellen formatiert, in denen die erste Zeile und Spalte Symbole des externen Alphabets und die Werte möglicher interner Zustände des Automaten – das interne Alphabet – enthalten. Tabellendaten sind die Befehle, die eine Turing-Maschine akzeptiert. Die Problemlösung erfolgt auf diese Weise: Der vom Kopf gelesene Buchstabe in der Zelle, über der er sich gerade befindet, und der interne Zustand des Maschinenkopfes bestimmen, welcher Befehl ausgeführt werden muss. Dieser spezielle Befehl befindet sich am Schnittpunkt der externen und internen Alphabetsymbole in der Tabelle.

Komponenten für Berechnungen

Um eine Turing-Maschine zur Lösung eines bestimmten Problems zu bauen, müssen Sie die folgenden Parameter dafür definieren.

Externes Alphabet. Dies ist eine bestimmte endliche Menge von Symbolen, die mit dem Zeichen A bezeichnet werden und deren Bestandteile Buchstaben genannt werden. Einer davon – a0 – muss leer sein. Das Turing-Gerätealphabet für Binärzahlen sieht beispielsweise so aus: A = (0, 1, a0).

Eine auf Tonband aufgezeichnete fortlaufende Kette von Buchstaben und Symbolen wird als Wort bezeichnet.

Ein automatisches Gerät ist ein Gerät, das ohne menschliches Eingreifen funktioniert. In einer Turingmaschine verfügt sie über mehrere verschiedene Zustände zur Lösung von Problemen und bewegt sich unter bestimmten Bedingungen von einer Position in eine andere. Die Menge solcher Wagenzustände ist das interne Alphabet. Es hat eine Buchstabenbezeichnung der Form Q=(q1, q2...). Eine dieser Positionen – q1 – muss die erste sein, also diejenige, die das Programm startet. Ein weiteres notwendiges Element ist der q0-Zustand, der Endzustand, also derjenige, der das Programm beendet und das Gerät in die Stoppposition bringt.

Übergangstabelle. Bei dieser Komponente handelt es sich um einen Algorithmus für das Verhalten des Gerätewagens in Abhängigkeit vom aktuellen Zustand der Maschine und dem Wert des gelesenen Symbols.

Algorithmus für die Maschine

Während des Betriebs wird der Schlitten des Turing-Geräts von einem Programm gesteuert, das bei jedem Schritt die folgende Abfolge von Aktionen ausführt:

1. Schreiben eines Zeichens eines externen Alphabets an eine Position, einschließlich einer leeren, und Ersetzen des darin enthaltenen Elements, einschließlich eines leeren.
2. Einen Zellenschritt nach links oder rechts verschieben.
3. Ändern Sie Ihren inneren Zustand.

Beim Schreiben von Programmen für jedes Zeichen- oder Positionspaar ist es daher erforderlich, drei Parameter genau zu beschreiben: a i – ein Element aus dem ausgewählten Alphabet A, die Richtung der Wagenverschiebung („←“ nach links, „→“ nach rechts, „Punkt“ – keine Bewegung) und q k – neuer Zustand des Geräts. Beispielsweise hat Befehl 1 „←“ q 2 die Bedeutung „Ersetzen Sie das Zeichen durch 1, bewegen Sie den Wagenkopf einen Zellenschritt nach links und.“ Machen Sie einen Übergang zum Zustand q 2“.

Turingmaschine: Beispiele

Beispiel 1. Die Aufgabe besteht darin, einen Algorithmus zu konstruieren, der der letzten Ziffer einer bestimmten Zahl auf einem Band eins hinzufügt. Eingabedaten – ein Wort – Ziffern einer ganzzahligen Dezimalzahl, geschrieben in aufeinanderfolgende Zellen auf Band. Zunächst befindet sich das Gerät gegenüber dem Symbol ganz rechts – der Ziffer der Zahl.

Lösung. Wenn die letzte Ziffer eine 9 ist, muss sie durch eine 0 ersetzt und dann eins zum vorherigen Zeichen hinzugefügt werden. Das Programm in diesem Fall für ein bestimmtes Turing-Gerät kann wie folgt geschrieben werden:

Hier ist q 1 der Zustand der Ziffernänderung, q 0 ist Stopp. Wenn die Maschine in q 1 ein Element aus der Zeile 0..8 fixiert, ersetzt sie es jeweils durch eines von 1..9 und wechselt dann in den Zustand q 0, d. h. das Gerät stoppt. Wenn der Wagen die Zahl 9 fixiert, ersetzt er sie durch 0, bewegt sich dann nach links und stoppt im Zustand q 1. Diese Bewegung wird fortgesetzt, bis das Gerät eine Zahl kleiner als 9 registriert. Wenn alle Zeichen gleich 9 sind, werden sie durch Nullen ersetzt, eine 0 wird an die Stelle des höchsten Elements geschrieben, der Schlitten bewegt sich nach links und eine 1 wird beschrieben eine leere Zelle. Der nächste Schritt ist der Übergang in den Zustand q 0 – Stopp.

Beispiel 2. Es wird eine Reihe von Symbolen angegeben, die öffnende und schließende Klammern darstellen. Es ist erforderlich, ein Turing-Gerät zu bauen, das ein Paar gegenseitiger Klammern entfernt, d. h. Elemente, die in einer Reihe angeordnet sind – „()“. Zum Beispiel die Anfangsdaten: „) (() (()“, die Antwort sollte lauten: „) . . ((“. Lösung: Der Mechanismus, der sich in q 1 befindet, analysiert das Element ganz links in der Zeile.

Zustand q 1: Wenn das Symbol „(“ angetroffen wird, dann nach rechts verschieben und zur Position q 2 gehen; wenn „a 0“ definiert ist, dann stoppen.

Zustand q 2: Die Klammer „(“ wird auf das Vorhandensein einer Paarung analysiert; wenn eine Übereinstimmung vorliegt, sollte das Ergebnis „)“ lauten. Wenn das Element gepaart ist, führen Sie einen Wagenrücklauf nach links durch und fahren Sie mit q 3 fort.

Zustand q 3: Löschen Sie zuerst das Symbol „(“ und dann „)“ und gehen Sie zu q 1.

Nach den 1920er Jahren der Ausdruck Rechenmaschine bezieht sich auf alle Maschinen, die Arbeiten ausgeführt haben Mensch-Computer, insbesondere solche, die nach den effizienten Methoden der Church-Turing-These entwickelt wurden. Diese These wird wie folgt formuliert: „Jeder Algorithmus kann in Form einer entsprechenden Turing-Maschine oder einer teilweise rekursiven Definition spezifiziert werden, und die Klasse der berechenbaren Funktionen stimmt mit der Klasse der teilweise rekursiven Funktionen und mit der Klasse der auf Turing-Maschinen berechenbaren Funktionen überein.“ .“ Auf andere Weise wird die Church-Turing-These als eine Hypothese über die Natur mechanischer Rechengeräte, beispielsweise elektronischer Computer, definiert. Jede mögliche Berechnung kann auf einem Computer durchgeführt werden, sofern dieser über genügend Zeit und Speicherplatz verfügt.

Mechanismen, die Berechnungen mit Unendlichkeiten durchführen, wurden als analoge Mechanismen bezeichnet. Werte in solchen Mechanismen wurden durch kontinuierliche numerische Größen dargestellt, beispielsweise der Drehwinkel einer Welle oder die Differenz des elektrischen Potentials.

Im Gegensatz zu analogen Maschinen hatten digitale Maschinen die Fähigkeit, den Zustand eines numerischen Werts darzustellen und jede Ziffer separat zu speichern. Digitale Maschinen nutzten vor der Erfindung des Direktzugriffsspeichers verschiedene Prozessoren oder Relais.

Name Rechenmaschine seit den 1940er Jahren begann es durch das Konzept ersetzt zu werden Computer. Diese Computer waren in der Lage, Berechnungen durchzuführen, die zuvor von Sachbearbeitern durchgeführt wurden. Da Werte nicht mehr von physikalischen Eigenschaften abhingen (wie bei analogen Maschinen), war ein logischer Computer auf Basis digitaler Hardware in der Lage, alles zu tun, was beschrieben werden konnte rein mechanisches System .

Turingmaschinen wurden entwickelt, um formal mathematisch zu definieren, was berechnet werden kann, vorbehaltlich Einschränkungen bei der Rechenleistung. Wenn eine Turing-Maschine eine Aufgabe erledigen kann, gilt die Aufgabe als Turing-berechenbar. Turing konzentrierte sich hauptsächlich auf die Entwicklung einer Maschine, die bestimmen konnte, was berechnet werden konnte. Turing kam zu dem Schluss, dass dieser Wert abzählbar sei, solange es eine Turing-Maschine gebe, die eine Annäherung an eine Zahl berechnen könne. Darüber hinaus kann eine Turing-Maschine logische Operatoren wie AND, OR, XOR, NOT und If-Then-Else interpretieren, um zu bestimmen, ob

Eine Turingmaschine ist eine Sammlung der folgenden Objekte

• 1) externes Alphabet A=(a 0 , a 1 , …, a n );
• 2) internes Alphabet Q=(q 1, q 2,…, q m) – Zustandsmenge;
• 3) eine Reihe von Steuerzeichen (P, L, S)
• 4) ein in beide Richtungen unendliches Band, unterteilt in Zellen, in die zu jedem diskreten Zeitpunkt jeweils nur ein Zeichen aus dem Alphabet A geschrieben werden kann;
• 5) ein Steuergerät, das in einem von vielen Zuständen sein kann

Das Symbol einer leeren Zelle ist der Buchstabe des externen Alphabets a 0 .

Unter den Zuständen gibt es den Anfangszustand q 1, in dem die Maschine zu arbeiten beginnt, und den Endzustand (oder Stoppzustand) q 0, in dem die Maschine einmal stoppt.

Das Steuergerät kann sich entlang des Bandes nach links und rechts bewegen und die Buchstaben A lesen und in die Zellen des Bandes schreiben. Das Steuergerät arbeitet gemäß Befehlen, die die folgende Form haben

q i a j > a p X q k

Aufzeichnung bedeutet Folgendes: Wenn sich das Steuergerät im Zustand q i befindet und der Buchstabe a j in die angezeigte Zelle geschrieben ist, wird (1) ein p anstelle eines j in die Zelle geschrieben, (2) die Maschine fährt mit der Überprüfung des nächsten fort Um die rechte Zelle von der gerade betrachteten Zelle aus anzuzeigen, wenn k.

Da der Betrieb der Maschine vereinbarungsgemäß vollständig durch ihren Zustand q zu einem bestimmten Zeitpunkt und den Inhalt a der gerade betrachteten Zelle bestimmt wird, gibt es für jede mögliche Konfiguration q i a j genau eine Regel. Es gibt keine Regeln nur für den Endzustand, in dem das Auto einmal stehen bleibt. Daher enthält ein Turing-Maschinenprogramm mit externem Alphabet A=(a0, a1, …, an) und internem Q=(q1, q2,…, qm) nicht mehr als m (n+ 1) Anweisungen.

Ein Wort im Alphabet A oder im Alphabet Q oder im Alphabet A Q ist eine beliebige Buchstabenfolge des entsprechenden Alphabets. Mit der k-ten Konfiguration meinen wir ein Bild eines Maschinenbandes mit darauf angesammelten Informationen zu Beginn des k-ten Schritts (oder ein Wort im Alphabet A, das zu Beginn des k-ten Schritts auf das Band geschrieben wurde). , die angibt, welche Zelle in diesem Schritt angezeigt wird und in welchem ​​Zustand sich das Fahrzeug befindet. Nur endliche Konfigurationen sind sinnvoll, d.h. solche, bei denen alle Zellen des Bandes, mit der möglichen Ausnahme einer endlichen Anzahl, leer sind. Eine Konfiguration wird als final bezeichnet, wenn der Zustand, in dem sich die Maschine befindet, final ist.

Wenn wir eine nicht-endgültige Konfiguration einer Turing-Maschine als Anfangskonfiguration wählen, besteht die Aufgabe der Maschine darin, die Anfangskonfiguration sequentiell (Schritt für Schritt) gemäß dem Programm der Maschine umzuwandeln, bis die endgültige Konfiguration erreicht ist. Danach gilt die Arbeit der Turing-Maschine als beendet und das Ergebnis der Arbeit gilt als die endgültig erreichte Konfiguration.

Wir werden sagen, dass ein nicht leeres Wort b im Alphabet A (a 0) = (a 1, ..., a n) von der Maschine an einer Standardposition wahrgenommen wird, wenn es in aufeinanderfolgende Zellen des Bandes geschrieben wird, alle Die anderen Zellen sind leer, und die Maschine sieht sich die Zelle ganz links oder die Zelle ganz rechts an, in der das Wort b steht. Die Standardposition wird als initial (endgültig) bezeichnet, wenn sich die Maschine, die das Wort in der Standardposition wahrnimmt, im Anfangszustand q 1 (bzw. im Stoppzustand q 0) befindet.

Wenn die Verarbeitung des Wortes b die Turing-Maschine in den Endzustand bringt, gilt sie als auf b anwendbar, andernfalls ist sie auf b nicht anwendbar (die Maschine läuft auf unbestimmte Zeit).

Schauen wir uns ein Beispiel an:

Gegeben sei eine Turingmaschine mit einem externen Alphabet A = (0, 1) (hier ist 0 das Symbol einer leeren Zelle), einem Alphabet interner Zustände Q = (q 0 , q 1 , q 2 ) und mit dem folgenden Funktionsdiagramm (Programm):

q 1 0 > 1 L q 2 ;

q 1 1 > 0 С q 2 ;

q 2 0 > 0 П q 0 ;

q 2 1 > 1 С q 1 ;

Dieses Programm kann mithilfe einer Tabelle geschrieben werden

Im ersten Schritt ist der Befehl gültig: q 1 0 > 1 L q 2 (das Steuergerät befindet sich im Zustand q1, und der Buchstabe 0 wird in die überwachte Zelle geschrieben, 1 wird in die Zelle geschrieben statt 0, der Der Kopf bewegt sich nach links, das Steuergerät geht in den Zustand q2) über. Dadurch entsteht auf der Maschine folgende Konfiguration:

Abschließend wird nach Ausführung des Befehls q 2 0 > 0 П q 0 die Konfiguration erstellt

Diese Konfiguration ist endgültig, da sich die Maschine in einem gestoppten Zustand q 0 befindet.

Somit wird das ursprüngliche Wort 110 von der Maschine in Wort 101 verarbeitet.

Die resultierende Folge von Konfigurationen kann kürzer geschrieben werden (der Inhalt der überwachten Zelle wird rechts neben dem Zustand geschrieben, in dem sich die Maschine gerade befindet):

11q 1 0 => 1 q 2 11 => 1q 1 11 => 1q 2 01 => 10q 0 1

Eine Turingmaschine ist nichts anderes als eine bestimmte Regel (Algorithmus) zur Transformation von Wörtern des Alphabets A Q, d. h. Konfigurationen. Um eine Turing-Maschine zu definieren, müssen Sie daher ihre externen und internen Alphabete sowie ein Programm angeben und angeben, welche Symbole eine leere Zelle und den Endzustand anzeigen.

Im Jahr 1936 schlug Alan Turing vor, das Konzept eines Algorithmus zu klären abstrakter Universaldarsteller. Seine Abstraktheit liegt darin, dass es sich um ein logisches Rechenkonstrukt und nicht um eine reale Rechenmaschine handelt. Der Begriff „Universalkünstler“ bedeutet, dass ein bestimmter Künstler jeden anderen Künstler imitieren kann. Beispielsweise können Operationen, die von realen Computern ausgeführt werden, auf einem Universal Executor simuliert werden. Anschließend wurde das von Turing erfundene Computerdesign genannt Turing Maschine.
Darüber hinaus wird davon ausgegangen, dass ein Universal Executor in der Lage sein muss, die Existenz oder Nichtexistenz eines Algorithmus für eine bestimmte Aufgabe nachzuweisen.

Was ist eine Turingmaschine?

Eine Turingmaschine besteht aus einem in beide Richtungen unendlichen, in Zellen unterteilten Band und einem Automaten (Kopf), der von einem Programm gesteuert wird.
Programme für Turing-Maschinen werden in Form einer Tabelle geschrieben, wobei die erste Spalte und Zeile die Buchstaben des externen Alphabets und die möglichen internen Zustände der Maschine (das interne Alphabet) enthalten. Der Inhalt der Tabelle stellt die Anweisungen für die Turingmaschine dar. Der Buchstabe, den der Kopf in der Zelle liest (über der er sich gerade befindet) und der interne Zustand des Kopfes bestimmen, welcher Befehl ausgeführt werden soll. Der Befehl wird durch die Schnittmenge der Zeichen des externen und internen Alphabets in der Tabelle bestimmt.

Um eine bestimmte Turing-Maschine zu definieren, müssen Sie die folgenden Komponenten dafür beschreiben:

• Externes Alphabet. Eine endliche Menge (zum Beispiel A), deren Elemente Buchstaben (Symbole) genannt werden. Einer der Buchstaben dieses Alphabets (z. B. eine 0) muss ein Nullzeichen sein.
• Internes Alphabet. Eine endliche Menge von Zuständen des Kopfes (Automaten). Einer der Zustände (z. B. q 1) muss der erste sein (Start des Programms). Ein weiterer Zustand (q 0) muss endgültig sein (Programm beenden) – der Stoppzustand.
• Übergangstabelle. Beschreibung des Verhaltens der Maschine (Kopf) in Abhängigkeit vom Zustand und dem gelesenen Symbol.

Ein Turing-Maschinenautomat kann während seines Betriebs die folgenden Aktionen ausführen:

• Schreiben Sie ein Zeichen eines externen Alphabets in eine Zelle (einschließlich einer leeren) und ersetzen Sie das Zeichen darin (einschließlich einer leeren).
• Eine Zelle nach links oder rechts verschieben.
• Ändere deinen inneren Zustand.

Ein Befehl für eine Turing-Maschine ist genau eine spezifische Kombination dieser drei Komponenten: Anweisungen, welches Symbol in die Zelle geschrieben werden soll (über der der Automat steht), wohin er sich bewegen und in welchen Zustand er wechseln soll. Obwohl der Befehl möglicherweise nicht alle Komponenten enthält (z. B. das Symbol nicht ändern, nicht verschieben oder den internen Status nicht ändern).

Ein Beispiel für eine Turingmaschine

Nehmen wir an, auf einem Band befindet sich ein Wort, das aus den Symbolen #, $, 1 und 0 besteht. Sie müssen alle #- und $-Symbole durch Nullen ersetzen. Im Moment des Starts befindet sich der Kopf über dem ersten Buchstaben des Wortes von links. Das Programm endet, wenn sich der Kopf über dem Leerzeichen nach dem am weitesten rechts stehenden Buchstaben des Wortes befindet.
Notiz: Die Länge des Wortes und die Reihenfolge der Zeichen spielen keine Rolle. Die Abbildung zeigt ein Beispiel für den Ablauf der Befehlsausführung für einen konkreten Fall. Befindet sich auf dem Band ein anderes Wort, ist die Reihenfolge der Befehlsausführung unterschiedlich. Trotzdem ist dieses Programm für die Turing-Maschine (in der Abbildung - die Tabelle links) auf alle Wörter des beschriebenen externen Alphabets anwendbar (die Eigenschaft der Anwendbarkeit des Algorithmus auf alle ähnlichen Probleme - Massencharakter) wird beobachtet.

Sie können das Programm komplizieren. Nehmen wir an, der Kopf befindet sich nicht unbedingt über dem ersten, sondern über jedem Zeichen des Wortes. Dann könnte das Programm für eine bestimmte Turing-Maschine so aussehen (oder es könnte anders sein):

Dabei wird der Kopf nach links verschoben, bis er sich über dem leeren Symbol befindet. Danach geht die Maschine in den Zustand q 2 (dessen Befehle mit den Befehlen q 1 des vorherigen Programms übereinstimmen).

Eine der wichtigsten Fragen in der modernen Informatik ist, ob es einen formalen Darsteller gibt, mit dem man jeden formalen Darsteller nachahmen kann. Die Antwort auf diese Frage erhielten fast gleichzeitig zwei herausragende Wissenschaftler – A. Turing und E. Post. Die von ihnen vorgeschlagenen Künstler unterschieden sich voneinander, aber es stellte sich heraus, dass sie sich gegenseitig und vor allem die Arbeit jedes offiziellen Künstlers nachahmen konnten.

Was ist ein formeller Testamentsvollstrecker? Was bedeutet es – ein formaler Künstler imitiert die Arbeit eines anderen formalen Künstlers? Wenn Sie Computerspiele gespielt haben, gehorchen Objekte auf dem Bildschirm bedingungslos den Befehlen des Spielers. Jedes Objekt verfügt über einen Satz gültiger Befehle. Gleichzeitig ist der Computer selbst ein Performer, und zwar nicht virtuell, sondern real. Es stellt sich also heraus, dass ein formaler Künstler die Arbeit eines anderen formalen Künstlers imitiert.

Betrachten Sie den Betrieb einer Turingmaschine.

Eine Turingmaschine ist ein Endlosband, das in Zellen unterteilt ist, und einem Schlitten (Lese- und Druckgerät), der sich entlang des Bandes bewegt.

Somit wird die Turingmaschine formal durch zwei Alphabete beschrieben:

A=(a1, a2, a3, …, an) – externes Alphabet, das zum Aufzeichnen von Quelldaten verwendet wird

Q=(q1, q2, q3,…, qm) – internes Alphabet, beschreibt eine Reihe von Zuständen des Lese-Druckgeräts.

Jede Zelle des Bandes kann ein Zeichen aus dem externen Alphabet A = (a0,a1,…,an) enthalten (in unserem Fall A=(0, 1))

Die erlaubten Aktionen einer Turingmaschine sind:

1) Schreiben Sie ein beliebiges Symbol des externen Alphabets in eine Zelle des Bandes (das zuvor dort vorhandene Symbol wird überschrieben).

2) in eine benachbarte Zelle wechseln

3) Ändern Sie den Status in einen der Status, die durch das interne Alphabetsymbol Q angezeigt werden

Eine Turingmaschine ist ein Automat, der von einer Tabelle gesteuert wird.

Die Zeilen in der Tabelle entsprechen den Symbolen des ausgewählten Alphabets A und die Spalten entsprechen den Zuständen der Maschine Q = (q0,q1,…,qm). Zu Beginn des Betriebs befindet sich die Turingmaschine im Zustand q1. Zustand q0 ist der Endzustand; sobald er erreicht ist, beendet die Maschine ihren Betrieb.

Jede Zelle der Tabelle, die einem Symbol ai und einem Zustand qj entspricht, enthält einen Befehl, der aus drei Teilen besteht
· Zeichen aus dem Alphabet A
· Bewegungsrichtung: „>“ (rechts), „<» (влево) или «.» (на месте)
· Neuzustand der Maschine

In der obigen Tabelle ist das Alphabet A = (0, 1, _) (enthält 3 Zeichen) und das interne Alphabet Q = (q1, q2, q3, q4, q0), q0 ist der Zustand, der den Wagen zum Stoppen bringt.

Betrachten wir mehrere Lösungen für Probleme. Sie können die Turing-Maschine auf der Website im Abschnitt herunterladen.

Problem 1. Sei A=(0, 1, _). Auf dem Band enthalten die Zellen Zeichen aus dem Alphabet in der folgenden Reihenfolge: 0011011. Der Wagen befindet sich über dem ersten Zeichen. Es muss ein Programm erstellt werden, das 0 durch 1 und 1 durch 0 ersetzt und den Schlitten in seine ursprüngliche Position zurückbringt.

Definieren wir nun die Beförderungszustände. Ich nenne sie „den Wunsch, etwas zu tun“.

q1) Der Wagen soll nach rechts fahren: Wenn er 0 sieht, ändert er ihn in 1 und bleibt im q1-Zustand, wenn er 1 sieht, ändert er ihn in 0 und bleibt im q1-Zustand, wenn er _ sieht, it geht 1 Zelle zurück „will etwas anderes“, d. h. geht in den Zustand q2. Schreiben wir unsere Argumentation in die Darstellertabelle. Syntax siehe Programmhilfe)

q2) Beschreiben wir nun den „Wagenwunsch“ q2. Wir müssen zu unserer ursprünglichen Position zurückkehren. Um dies zu tun: Wenn wir 1 sehen, verlassen wir es und bleiben im Zustand q2 (mit dem gleichen Wunsch, das Ende der Symbolreihe zu erreichen); wenn wir 0 sehen, verlassen wir es und bewegen uns im Zustand q2 weiter nach links; wir sehen _ - bewegt sich um 1 Zelle nach rechts. Jetzt befinden Sie sich an der gewünschten Stelle in den Aufgabenbedingungen. Wir gehen zum Zustand q0.

Im Video können Sie das Programm in Aktion sehen:

Problem 2. Gegeben: eine endliche Folge von 0 und 1 (001101011101). Sie müssen nach dieser Sequenz durch eine leere Zelle geschrieben und in dieser Sequenz durch 0 ersetzt werden. Zum Beispiel:

Aus 001101011101 erhalten wir 000000000000 1111111.

Wie Sie sehen, wurden nach dieser Sequenz sieben Einheiten geschrieben, an deren Stellen Nullen stehen.

Beginnen wir mit der Diskussion. Lassen Sie uns feststellen, welche Zustände der Wagen benötigt und wie viele.

q1) sah 1 – korrigiere es auf Null und gehe in einen anderen Zustand q2 (ein neuer Zustand wird eingeführt, damit der Wagen nicht in einem Durchgang alle Einsen in Nullen ändert)

q2) Nichts ändern, zum Ende der Sequenz gehen

q3) Sobald der Wagen eine leere Zelle sieht, macht er einen Schritt nach rechts und zeichnet eine 1, wenn er eine 1 sieht, fährt er fort, um das Symbol am Ende zu unterschreiben. Sobald ich eine Einheit gezeichnet habe, gehen wir zu Zustand q4

q4) Wir gehen die geschriebenen Einheiten durch, ohne etwas zu ändern. Sobald wir eine leere Zelle erreichen, die die Sequenz von Einsen trennt, wechseln wir zu einem neuen Zustand q5

q5) In diesem Zustand gehen wir zum Anfang der Sequenz, ohne etwas zu ändern. Wir erreichen eine leere Zelle, drehen uns um und gehen zum Zustand q1

Der Wagen nimmt den Zustand q0 ein, wenn er im Zustand q1 bis zum Ende dieser Sequenz übergeht und auf eine leere Zelle trifft.

Wir erhalten das folgende Programm:

Im Video unten können Sie die Turing-Maschine in Aktion sehen.