Bisher war es für uns praktisch, auf die Erfahrung eines Programmierers zu verweisen, wenn es um Algorithmen, Programme, Interpreter, schrittweise Ausführung usw. ging. Dies ermöglichte es uns, die Details der Konstruktion bestimmter Algorithmen unter dem Vorwand zu ignorieren, dass der Leser sie leicht wiederherstellen würde (oder zumindest glauben würde, dass nicht jeder Leser in seinem Leben einen Pascal-Interpreter in Pascal geschrieben hätte).

In manchen Fällen reicht dies jedoch nicht aus. Lassen Sie uns zum Beispiel die algorithmische Unentscheidbarkeit eines Problems beweisen, dessen Definition nichts über Programme aussagt (in diesem Abschnitt werden wir zum Beispiel die Unentscheidbarkeit des Problems der Gleichheit von Wörtern in Halbgruppen beweisen, die durch definiert sind). Generatoren und Beziehungen). Normalerweise wird es so gemacht. Wir zeigen, dass sich das Stoppproblem auf dieses Problem reduziert. Dazu modellieren wir die Funktionsweise eines beliebigen Algorithmus im Hinblick auf das betrachtete Problem (was das bedeutet, wird aus dem folgenden Beispiel deutlich). Gleichzeitig ist es uns wichtig, dass die Definition des Algorithmus möglichst einfach ist.

Unser Plan ist also dieser. Wir werden eine ziemlich einfach definierbare Klasse von Maschinen beschreiben (sie kann auf verschiedene Arten ausgewählt werden; wir werden sogenannte Turing-Maschinen verwenden), dann erklären, dass jede berechenbare Funktion auf einer solchen Maschine berechnet werden kann, und dann zeigen, dass die Frage von Das Stoppen einer Turingmaschine lässt sich auf die Frage nach der Gleichheit von Wörtern in einer Halbgruppe reduzieren.

Ein weiterer Grund, warum einfache Rechenmodelle wichtig sind (es gibt viele verschiedene Arten von Turing-Maschinen, Adressmaschinen usw.), hängt mit der Theorie der Rechenkomplexität zusammen, für die wir uns zu interessieren beginnen Vorlaufzeit Programme. Diese Frage geht jedoch über die klassische Algorithmentheorie hinaus.

Turingmaschinen: Definition

Turing Maschine hat Unendlichkeit in beide Richtungen Band, unterteilt in Quadrate ( Zellen). Jede Zelle kann ein Symbol aus einer festen (für eine bestimmte Maschine) endlichen Menge namens enthalten Alphabet dieser Maschine. Eines der Zeichen des Alphabets wird hervorgehoben und als „Leerzeichen“ bezeichnet; es wird davon ausgegangen, dass zunächst das gesamte Band leer, also mit Leerzeichen gefüllt ist.

Eine Turing-Maschine kann den Inhalt eines Bandes mithilfe eines speziellen Lese- und Schreibgeräts ändern. Köpfe, die sich entlang des Bandes bewegt. Der Kopf befindet sich in jedem Moment in einer der Zellen. Машина Тьюринга получает от головки информацию о том, какой символ та видит, и в зависимости от этого (и от своего внутреннего состояния) решает, что делать, то есть какой символ записать в текущей ячейке и куда сдвинуться после этого (налево, направо или остаться vor Ort). Gleichzeitig ändert sich auch der interne Zustand der Maschine (wir gehen davon aus, dass die Maschine, das Band nicht mitgerechnet, über einen endlichen Speicher verfügt, also über eine endliche Anzahl interner Zustände). Wir müssen uns auch darüber einigen, wo wir mit der Arbeit beginnen und wann wir sie beenden.

Um eine Turingmaschine zu definieren, müssen Sie daher die folgenden Objekte angeben:

Die Übergangstabelle ist wie folgt aufgebaut: Für jedes Paar wird ein Tripel angegeben. Hier ist die Verschiebung eine der Zahlen -1 (nach links), 0 (an Ort und Stelle) und 1 (nach rechts). Somit ist die Übergangstabelle eine Funktion vom Typ S x A -> S x A x (-1,0,1), die für diejenigen Paare definiert ist, in denen der Zustand nicht endgültig ist.

Es bleibt noch das Verhalten der Turingmaschine zu beschreiben. In jedem Moment gibt es welche Aufbau, bestehend aus dem Inhalt des Bandes (formal gesehen ist der Inhalt des Bandes eine beliebige Abbildung Z -> A), der aktuellen Position des Kopfes (irgendeine ganze Zahl) und dem aktuellen Zustand der Maschine (Element S). Die Umwandlung der Konfiguration in die nächste erfolgt nach natürlichen Regeln: Wir schauen in der Tabelle nach, was für einen bestimmten Zustand und für ein bestimmtes Symbol getan werden muss, das heißt, wir ermitteln den neuen Zustand der Maschine und ändern ihn Symbol auf das angegebene Symbol und bewegen Sie dann den Kopf nach links oder rechts oder lassen Sie ihn an Ort und Stelle. Wenn der neue Zustand außerdem einer der endgültigen ist, endet der Betrieb der Maschine. Es bleibt abzustimmen, wie wir den Maschineneingang mit Informationen versorgen und was als Ergebnis ihrer Arbeit gilt. Wir gehen davon aus, dass das Alphabet der Maschine zusätzlich zum Leerzeichen die Zeichen 0 und 1 (und möglicherweise einige andere Zeichen) enthält. Die Eingabe und Ausgabe der Maschine sind endliche Folgen von Nullen und Einsen (Binärwörter). Das eingegebene Wort wird auf ein leeres Band geschrieben, der Kopf der Maschine wird in ihre erste Zelle gelegt, die Maschine wird in ihren Ausgangszustand gebracht und gestartet. Wenn die Maschine stoppt, ist das Ergebnis ein Binärwort, das von der Kopfposition aus nach rechts gelesen werden kann (bis ein anderes Zeichen als 0 und 1 erscheint).

Somit definiert jede Turing-Maschine eine Teilfunktion für Binärwörter. Es ist selbstverständlich, alle diese Funktionen aufzurufen berechenbar auf Turingmaschinen.

Turingmaschinen: Diskussion

Natürlich enthält unsere Definition viele spezifische Details, die geändert werden könnten. Beispielsweise kann ein Band nur in einer Richtung endlos sein. Sie können dem Auto zwei Bänder verleihen. Wir können davon ausgehen, dass die Maschine entweder ein neues Zeichen schreiben oder sich bewegen kann, aber nicht beides. Sie können das Alphabet einschränken, indem Sie beispielsweise berücksichtigen, dass es genau 10 Zeichen haben muss. Sie können verlangen, dass am Ende nichts außer dem Ergebnis der Arbeit auf dem Band steht (die restlichen Zellen müssen leer sein). Alle oben genannten und viele andere Änderungen ändern nichts an der Klasse der auf Turing-Maschinen berechenbaren Funktionen. Natürlich gibt es auch einige harmlose Änderungen. Wenn Sie beispielsweise einem Auto verbieten, nach links zu fahren, ändert sich die Situation radikal; im Grunde wird das Band unbrauchbar, da eine Rückkehr zu den alten Aufnahmen nicht mehr möglich ist.

Woher wissen Sie, welche Veränderungen harmlos sind und welche nicht? Offenbar sind hier zumindest ein wenig Erfahrungen in der praktischen Programmierung auf Turing-Maschinen erforderlich. Danach können Sie sich bereits ein Bild von den Fähigkeiten der Maschine machen, ohne das gesamte Programm schreiben zu müssen, sondern sich nur an einer ungefähren Beschreibung orientieren zu müssen. Als Beispiel beschreiben wir eine Maschine, die das Eingabewort verdoppelt (das Wort XX erzeugt, wenn die Eingabe das Wort X war).

Wenn die Maschine ein Leerzeichen sieht (das Eingabewort ist leer), funktioniert sie nicht mehr. Wenn nicht, merkt es sich das aktuelle Zeichen und setzt eine Markierung (im Alphabet gibt es neben den Zeichen 0 und 1 auch deren „markierte Varianten“ und ). Anschließend bewegt sie sich nach rechts zu einer leeren Zelle und schreibt dort eine Kopie des auswendig gelernten Symbols. Dann bewegt sie sich nach links, bis sie markiert ist; Nachdem er sich in das Zeichen vertieft hat, geht er zurück und erinnert sich an das nächste Zeichen und so weiter, bis er das gesamte Wort abgeschrieben hat.

Mit etwas Erfahrung können Sie hinter all diesen Phrasen spezifische Teile des Programms für die Turing-Maschine erkennen. Beispielsweise bedeuten die Worte „erinnert sich an das Symbol und bewegt sich nach rechts“, dass es zwei Gruppen von Zuständen gibt, eine für die Situation, in der eine Null gespeichert wird, die andere, wenn eine Eins gespeichert wird, und innerhalb jeder Gruppe die Bewegung zur rechts ist auf die erste leere Zelle programmiert.

Mit etwas mehr Erfahrung können Sie verstehen, dass in dieser Beschreibung ein Fehler vorliegt; es gibt keinen Mechanismus zum Stoppen, wenn das gesamte Wort kopiert wird, da sich die Kopien der Zeichen nicht von den Zeichen des Originalworts unterscheiden. Es ist auch klar, wie der Fehler behoben werden kann: Sie müssen Sonderzeichen und Kopien schreiben und im letzten Schritt alle Markierungen löschen.

77 . Zeigen Sie, dass die Umkehrfunktion, die ein Wort rückwärts dreht, durch eine Turingmaschine berechenbar ist.

Ein weiteres Beispiel für informelles Denken: Lassen Sie uns erklären, warum es möglich ist, keine weiteren Zeichen außer 0, 1 und dem Leerzeichen zu verwenden. Es sei eine Maschine mit einem großen Alphabet von N Zeichen. Lassen Sie uns eine neue Maschine bauen, die den Betrieb der alten Maschine simuliert, aber jede Zelle der alten Maschine entspricht einem Block von k Zellen der neuen Maschine. Die Blockgröße (die Zahl k) wird so festgelegt, dass innerhalb des Blocks alle Zeichen eines großen Alphabets mit Nullen und Einsen kodiert werden können. Die ursprünglichen Zeichen 0 , 1 und Leerzeichen werden als 0 gefolgt von (k-1) Leerzeichen, 1 gefolgt von (k-1) Leerzeichen und einer Gruppe von k Leerzeichen codiert. Zuerst müssen Sie die Buchstaben des Eingabeworts um einen Abstand k verschieben, was ohne zusätzliche Symbole möglich ist (wenn Sie den äußeren Buchstaben erreichen, verschieben Sie ihn weg, und wenn Sie den nächsten erreichen, verschieben Sie ihn und den äußersten eins usw.); Sie müssen nur verstehen, dass Sie das Ende eines Wortes als eine Position identifizieren können, auf die mehr als k Leerzeichen folgen. Offensichtlich müssen wir in diesem Prozess eine begrenzte Menge an Informationen im Speicher speichern, also ist dies möglich. Danach ist es bereits möglich, den Betrieb der ursprünglichen Maschine Schritt für Schritt zu simulieren, und hierfür ist auch ein endlicher Speicher (d. h. eine endliche Anzahl von Zuständen) ausreichend, da nur eine kleine Nachbarschaft des Kopfes der simulierten Maschine vorhanden ist uns wichtig. Schließlich müssen wir das Ergebnis wieder komprimieren.

Zum Abschluss der Diskussion präsentieren wir das oben versprochene Argument zugunsten der Tatsache, dass jede berechenbare Funktion auf einer Turing-Maschine berechenbar ist. Es soll eine Funktion geben, die eine Person berechnen kann. Dabei muss er natürlich Stift und Papier verwenden, da Menge an Informationen Die Menge, die er „in seinem Kopf“ speichern kann, ist begrenzt. Wir gehen davon aus, dass er auf einzelnen Blättern schreibt. Zusätzlich zum aktuellen Blatt befindet sich rechts ein Stapel Papiere und links ein Stapel; Nachdem Sie damit fertig sind, können Sie das aktuelle Blatt in einen beliebigen Stapel legen und den nächsten vom anderen Stapel nehmen. Ein Mann hat einen Bleistift und einen Radiergummi. Da sehr kleine Buchstaben nicht sichtbar sind, ist die Anzahl der klar unterscheidbaren Zustände des Blattes endlich, und wir können davon ausgehen, dass zu jedem Zeitpunkt ein Buchstabe aus einem endlichen (wenn auch sehr großen) Alphabet auf das Blatt geschrieben wird. Ein Mensch hat auch ein endliches Gedächtnis, daher ist sein Zustand ein Element einer endlichen Menge. In diesem Fall können Sie eine Tabelle erstellen, in der aufgeschrieben wird, wie seine Arbeit an einem Blatt mit einem bestimmten Inhalt, beginnend in einem bestimmten Zustand, enden wird (was auf dem Blatt steht, in welchem ​​Zustand sich die Person befinden wird). und aus welchem ​​Paket das nächste Blatt entnommen wird). Es ist jetzt klar, dass menschliche Handlungen genau dem Betrieb einer Turing-Maschine mit einem großen (aber endlichen) Alphabet und einer großen (aber endlichen) Anzahl interner Zustände entsprechen.

Einführung

Im Jahr 1936 schlug Alan Turing einen abstrakten universellen Executor vor, um das Konzept eines Algorithmus zu verdeutlichen. 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 Turing-Maschine genannt.

Der Zweck dieser Kursarbeit besteht darin, ein Programm zu erstellen, das eine Turing-Maschine in der funktionalen Programmiersprache Haskell implementiert. Als Beispiel implementieren wir eine Turing-Maschine, die eine Dezimalzahl mit 2 multiplizieren soll.

Um dieses Ziel zu erreichen, müssen folgende Aufgaben gelöst werden: die Funktionsprinzipien der Turing-Maschine und ihre Struktur studieren, algorithmisch unlösbare Probleme berücksichtigen, eine Datenstruktur auswählen, die implementierten Funktionen beschreiben und auch Beispiele für das Programm geben .

Grundlegende Bestimmungen der Turingmaschine

Die Turing-Maschine erhielt ihren Namen vom englischen Mathematiker Alan Turing, der 1937 eine Methode zur formalen Spezifikation von Algorithmen mithilfe einer abstrakten Maschine vorschlug. Der Kern der Arbeit besteht aus Folgendem. Es gibt ein potenziell unendliches Band, das in Zellen unterteilt ist, von denen jede ein Zeichen aus einem endlichen Alphabet enthalten kann. Eine Turing-Maschine verfügt über einen Lese-/Schreibkopf, mit dem Sie ein Zeichen in der aktuellen Zelle lesen, ein Zeichen in eine Zelle schreiben und den Kopf nach links oder rechts zu einer benachbarten Zelle bewegen können. Die Maschine arbeitet diskret in Zyklen und befindet sich bei jedem Zyklus in einem der möglichen Zustände, von denen es eine endliche Anzahl gibt. Für jedes Paar (Zustand, beobachtetes Symbol) wird ein Tripel definiert (geschriebenes Zeichen, Kopfbewegung, neuer Zustand). Bevor der Betrieb beginnt, befindet sich die Turing-Maschine im Ausgangszustand und der Lese-/Schreibkopf scannt die nicht leere Zelle ganz links auf dem Band. Während die Maschine also das nächste Symbol überprüft, schreibt sie ein neues Symbol (vielleicht dasselbe), bewegt den Kopf nach links, nach rechts oder bleibt an Ort und Stelle und geht in einen neuen Zustand über oder bleibt im gleichen Zustand.

Eine Turing-Maschine besteht aus drei Teilen: einem Band, einem Lesekopf (Schreibkopf) und einem Logikgerät, wie in Abbildung 1 deutlich dargestellt.

Das Band fungiert als externer Speicher. Es gilt als unbegrenzt (unendlich). Dies allein weist darauf hin, dass es sich bei der Turing-Maschine um ein Modellgerät handelt, da kein reales Gerät über einen unendlichen Speicher verfügen kann.

Abbildung 1 – Schaltung einer Turingmaschine

Eine Turingmaschine arbeitet in einem beliebigen endlichen Alphabet A = (_, a1…an) – dieses Alphabet wird extern genannt. Es enthält ein Sonderzeichen – _, das als Leerzeichen bezeichnet wird. Wenn Sie es an eine beliebige Zelle senden, wird das zuvor dort vorhandene Zeichen gelöscht und die Zelle bleibt leer. In jede Bandzelle kann nur ein Zeichen geschrieben werden. Die auf dem Band gespeicherten Informationen werden durch eine endliche Folge externer Buchstaben des Alphabets mit Ausnahme des Leerzeichens dargestellt.

Der Kopf befindet sich immer über einer der Bandzellen. Die Arbeit erfolgt in Zyklen (Schritten). Das vom Kopf ausgeführte Befehlssystem ist äußerst einfach: Bei jedem Taktzyklus ersetzt er das Vorzeichen in der beobachteten Zelle ai durch das Vorzeichen aj. In diesem Fall sind Kombinationen möglich:

1) aj = ai – bedeutet, dass sich das Vorzeichen in der beobachteten Zelle nicht geändert hat;

2) ai ? _, aj = _ - das in der Zelle gespeicherte Zeichen wird durch ein leeres ersetzt, d.h. gelöscht;

3) ai = _, aj ? _ - ein leeres Zeichen wird durch ein nicht leeres (mit der Nummer j im Alphabet) ersetzt, d. h. ein Schild wird eingefügt;

4) ai ? aj ? _ – entspricht dem Ersetzen eines Zeichens durch ein anderes.

Somit implementiert die Turing-Maschine ein System äußerst einfacher Informationsverarbeitungsbefehle. Dieses System von Verarbeitungsbefehlen wird auch durch ein äußerst einfaches Befehlssystem zum Bewegen des Bandes ergänzt: eine Zelle nach links, eine Zelle nach rechts und an Ort und Stelle bleiben, d. h. Durch die Befehlsausführung kann sich die Adresse der überwachten Zelle entweder auf 1 ändern oder unverändert bleiben.

Obwohl jedoch die tatsächliche Bewegung des Bandes stattfindet, wird normalerweise die Bewegung des Kopfes relativ zum betrachteten Abschnitt berücksichtigt. Aus diesem Grund wird der Befehl zum Verschieben des Bandes nach links mit R (Rechts) bezeichnet, das Verschieben nach rechts mit L (Links) und kein Verschieben mit S (Stopp). Wir werden speziell über die Bewegung des Kopfes sprechen und R, L und S als Befehle für seine Bewegung betrachten.

Der elementare Charakter dieser Befehle bedeutet, dass, wenn es notwendig ist, auf den Inhalt einer bestimmten Zelle zuzugreifen, dieser nur durch eine Kette einzelner Verschiebungen um eine Zelle gefunden werden kann. Dies verlängert natürlich den Verarbeitungsprozess erheblich, ermöglicht aber den Verzicht auf die Nummerierung von Zellen und die Verwendung von Befehlen zum Aufrufen der Adresse, d.h. reduziert die Anzahl wirklich elementarer Schritte, was aus theoretischer Sicht wichtig ist.

Die Verarbeitung von Informationen und die Ausgabe von Befehlen zum Schreiben eines Zeichens sowie zum Verschieben des Bandes in einer Turing-Maschine erfolgt durch ein logisches Gerät (LU). Die LU kann sich in einem der Zustände befinden, die eine endliche Menge bilden und mit Q =(q1...qm, q0) bezeichnet werden, wobei der Zustand q0 dem Abschluss der Arbeit entspricht und q1 der Anfangszustand ist . Q bildet zusammen mit den Zeichen R, L, S das interne Alphabet der Maschine. Die LU verfügt über zwei Eingangskanäle (ai, qi) und drei Ausgangskanäle (ai+1, qi+1, Di+1). Das LU-Diagramm einer Turing-Maschine ist in Abbildung 2 dargestellt.

Abbildung 2 – LU-Diagramm einer Turingmaschine

Es ist notwendig, die Schaltung wie folgt zu verstehen: Im Zyklus i wird ein Vorzeichen der aktuell betrachteten Zelle (ai) an einen Eingang der LU geliefert, und ein Vorzeichen, das den Zustand der LU im Moment angibt (qi), wird zugeführt zum anderen Eingang. Abhängig von der empfangenen Kombination von Zeichen (ai, qi) und den vorhandenen Verarbeitungsregeln generiert und sendet die LU ein neues Zeichen (ai+1) über den ersten Ausgabekanal an die beobachtete Zelle, gibt einen Befehl zum Bewegen des Kopfes aus (Di +1 von R, L und S) und gibt außerdem einen Befehl zum Übergang in den nächsten Zustand (qi+1). Somit ist der elementare Schritt (Zyklus) des Betriebs einer Turing-Maschine wie folgt: Der Kopf liest ein Symbol aus der überwachten Zelle und führt abhängig von seinem Zustand und dem gelesenen Symbol einen Befehl aus, der angibt, welches Symbol geschrieben werden soll ( oder löschen) und welche Bewegung ausgeführt werden soll. Gleichzeitig geht der Kopf in einen neuen Zustand über. Das Betriebsdiagramm einer solchen Maschine ist in Abbildung 3 dargestellt.

Abbildung 3 – Diagramm der Funktionsweise einer Turingmaschine

Dieses Diagramm spiegelt die Aufteilung des Speichers in externe und interne wider. Das Äußere wird, wie bereits erwähnt, in Form eines Endlosbandes dargestellt – es dient zur Speicherung von Informationen, die in den Symbolen des äußeren Alphabets kodiert sind. Der interne Speicher wird durch zwei Zellen zum Speichern des nächsten Befehls während des aktuellen Taktzyklus dargestellt: Der nächste Zustand (qi+1) wird von der LU nach Q übertragen und gespeichert, und der Schiebebefehl (Di+1) wird in D gespeichert . Von Q gelangt über die Rückmeldeleitung qi+1 in die LU, und von D wird der Befehl an den Aktuator gesendet, der das Band bei Bedarf um eine Position nach rechts oder links bewegt.

Die allgemeine Regel, nach der eine Turing-Maschine arbeitet, kann durch die folgende Notation dargestellt werden: qi aj > qi" aj" Dk, d. h. Nachdem der Kopf im Qi-Zustand das Symbol aj betrachtet hat, wird das Symbol aj in die Zelle geschrieben, der Kopf geht in den Qi-Zustand über und das Band macht eine Bewegung Dk. Für jede Kombination qi aj gibt es genau eine Transformationsregel (nur für q0 gibt es keine Regeln, da die Maschine stoppt, sobald sie in diesen Zustand gelangt). Dies bedeutet, dass der logische Block eine Funktion implementiert, die jedes Paar von Eingangssignalen qi aj mit einem und nur einem Tripel von Ausgangssignalen qi „aj“ Dk verknüpft – sie wird als logische Funktion der Maschine bezeichnet und normalerweise in der Form dargestellt eine Tabelle (Funktionsdiagramm der Maschine), deren Spalten durch Zustandssymbole gekennzeichnet sind und deren Zeilen Zeichen des äußeren Alphabets sind. Wenn es n Zeichen des externen Alphabets gibt und die Anzahl der LU-Zustände m beträgt, beträgt die Gesamtzahl der Transformationsregeln offensichtlich n×m.

Eine bestimmte Turing-Maschine wird durch Aufzählung der Elemente der Mengen A und Q sowie der logischen Funktion, die die LU implementiert, spezifiziert, d. h. eine Reihe von Transformationsregeln. Es ist klar, dass es unendlich viele verschiedene Mengen A, Q und logische Funktionen geben kann, d.h. und es gibt auch unendlich viele Turingmaschinen.

Es ist auch notwendig, das Konzept der Maschinenkonfiguration einzuführen, d. h. Zustandssätze aller Bandzellen, LU-Zustände und Kopfposition. Es ist klar, dass die Maschinenkonfiguration beliebig viele Zeichen aus dem externen Alphabet und nur ein Zeichen aus dem internen enthalten kann.

Vor Beginn der Arbeit wird ein Anfangswort a endlicher Länge im Alphabet A auf ein leeres Band geschrieben; Der Kopf wird über dem ersten Zeichen des Wortes a installiert, die LU wird in den Zustand q1 übertragen (d. h. die Anfangskonfiguration sieht aus wie q1a). Da in jeder Konfiguration nur eine Transformationsregel implementiert ist, bestimmt die anfängliche Konfiguration eindeutig alle nachfolgenden Operationen der Maschine, d. h. den gesamten Konfigurationsablauf bis zur Betriebsbeendigung.

Abhängig von der Erstkonfiguration sind zwei Szenarien möglich:

1) nach einer endlichen Anzahl von Zyklen stoppt die Maschine beim Stoppbefehl; in diesem Fall erscheint die endgültige Konfiguration, die den Ausgabeinformationen entspricht, auf dem Band;

2) Es gibt kein Anhalten.

Im ersten Fall sagen sie, dass diese Maschine auf die ursprünglichen Informationen anwendbar ist, im zweiten Fall nicht. Der gesamte Satz von Eingabekonfigurationen, unter denen die Maschine ein Ergebnis liefert, bildet eine Klasse von zu lösenden Problemen. Offensichtlich macht es keinen Sinn, eine Turingmaschine für ein Problem zu verwenden, das nicht zur Klasse der lösbaren Probleme gehört.

Es gibt eine Turing-Hypothese: Wenn ein Vorgang genau definiert und mechanischer Natur ist, kann man vernünftigerweise davon ausgehen, dass es eine Turing-Maschine gibt, die ihn ausführen kann. Es kann nicht bewiesen werden, da es die lose Definition des Konzepts eines Algorithmus mit der strengen Definition einer Turingmaschine verbindet. Diese Vermutung kann widerlegt werden, wenn man ein Beispiel für einen Algorithmus nennen kann, der nicht mit einer Turing-Funktionsschaltung implementiert werden kann. Alle bisher bekannten Algorithmen können jedoch mithilfe von Turing-Funktionsschaltkreisen spezifiziert werden.

Simulator zum Erlernen des Universal Performers

Was ist das?

Der Turing-Maschinensimulator ist ein Trainingsmodell eines universellen Executors (abstrakte Rechenmaschine), der 1936 von A. Turing vorgeschlagen wurde, um das Konzept eines Algorithmus zu verdeutlichen. Nach Turings These kann jeder Algorithmus als Programm für eine Turing-Maschine geschrieben werden. Es ist erwiesen, dass die Turing-Maschine in ihren Fähigkeiten der Post-Maschine und normalen Markov-Algorithmen entspricht.

Eine Turingmaschine besteht aus einem Schlitten (Lese- und Schreibkopf) und einem in Zellen unterteilten Endlosband. Jede Zelle des Bandes kann ein Zeichen aus einem Alphabet A=(a 0 ,a 1 ,…,a N ) enthalten. Jedes Alphabet enthält ein Leerzeichen, das als 0 oder Λ bezeichnet wird. Bei der Eingabe von Befehlen wird das Leerzeichen durch einen Unterstrich „_“ ersetzt.

Eine Turingmaschine ist ein Automat, der von einer Tabelle gesteuert wird. Die Zeilen in der Tabelle entsprechen den Zeichen des ausgewählten Alphabets A und die Spalten entsprechen den Zuständen der Maschine Q=(q 0 ,q 1 ,…,q M ) . Zu Beginn ihres Betriebs befindet sich die Turingmaschine im Zustand q 1 . Zustand q 0 ist der Endzustand: Sobald er erreicht ist, beendet die Maschine ihren Betrieb.

In jeder Zelle der Tabelle, die einem Symbol a i und einem Zustand q j entspricht, gibt es einen Befehl, der aus drei Teilen besteht:

1. Zeichen aus dem Alphabet A;
2. Bewegungsrichtung: > (rechts),
3. Neuzustand der Maschine

Nachricht

1. Falina I.N. Das Thema „Turingmaschine“ im Schulinformatikkurs (inf.1september.ru).
2. Mayer R.V. Post- und Turing-Maschinen (komp-model.narod.ru).
3. Pilshchikov V.N., Abramov V.G., Vylitok A.A., Goryachaya I.V. Turingmaschine und Markov-Algorithmen. Problemlösung, M.: MSU, 2006.
4. Bekman I.N. Informatik. Vorlesung 7. Algorithmen (profbeckman.narod.ru)
5. Solowjew A. Diskrete Mathematik ohne Formeln (lib.rus.ec)
6. Ershov S.S. Elemente der Algorithmentheorie, Tscheljabinsk, SUSU Publishing Center, 2009.
7. Varpakhovsky F.L. Elemente der Theorie der Algorithmen, M: Prosveshchenie, 1970.
8. Vereshchagin N.K., Shen A. Berechnete Funktionen, M: MTsNMO, 1999.

Was tun dagegen?

Am oberen Rand des Programms befindet sich ein Editorfeld, in dem Sie den Problemzustand in freier Form eingeben können.

Das Menüband bewegt sich mithilfe der Schaltflächen links und rechts davon nach links und rechts. Durch Doppelklicken (oder Rechtsklick) auf eine Multifunktionsleistenzelle können Sie deren Inhalt ändern.

Verwendung des Menüs Schleife Sie können den Zustand des Bandes im internen Puffer speichern und das Band aus dem Puffer wiederherstellen.

Auf dem Feld Alphabet Die Zeichen des ausgewählten Alphabets werden angegeben. Den eingegebenen Zeichen wird automatisch ein Leerzeichen hinzugefügt.

Das Programm wird in die Tabelle unten im Fenster eingegeben. Die erste Spalte enthält alphabetische Zeichen und wird automatisch ausgefüllt. Die erste Zeile listet alle möglichen Zustände auf. Mit den Schaltflächen oberhalb der Tabelle können Sie Tabellenspalten (Statusspalten) hinzufügen und entfernen.

Wenn Sie einen Befehl in eine Tabellenzelle eingeben, müssen Sie zunächst ein neues Zeichen, dann die Richtung des Übergangs und die Statusnummer eingeben. Wenn ein Zeichen weggelassen wird, bleibt es standardmäßig unverändert. Wenn die Statusnummer weggelassen wird, ändert sich der Status der Maschine standardmäßig nicht.

Direkt im Feld Ein Kommentar Sie können zur Lösung Freiformkommentare eingeben. Meistens erklärt es, was jeder Zustand einer Turing-Maschine bedeutet.

Das Programm kann kontinuierlich (F9) oder schrittweise (F8) ausgeführt werden. Der Befehl, der nun ausgeführt wird, ist grün hinterlegt. Die Ausführungsgeschwindigkeit ist über das Menü einstellbar Geschwindigkeit.

Turingmaschinenprobleme können in Dateien gespeichert werden. Gespeichert werden Aufgabenzustand, Alphabet, Programm, Kommentare und der Ausgangszustand des Bandes. Wenn eine Aufgabe aus einer Datei geladen und in der Datei gespeichert wird, wird der Bandstatus automatisch gepuffert.

Wenn Sie einen Fehler bemerken oder Anregungen, Kommentare, Beschwerden, Wünsche oder Stellungnahmen haben, schreiben Sie uns.

Technische Anforderungen

Das Programm läuft unter den Betriebssystemen der Linie Windows auf jedem modernen Computer.

Lizenz

Das Programm ist für die nichtkommerzielle Nutzung kostenlos. Der Quellcode des Programms wird nicht weitergegeben.

Das Programm kommt“ wie es ist", das heißt, der Autor übernimmt keine Verantwortung für alle möglichen Folgen seiner Verwendung, einschließlich moralischer und materieller Verluste, Geräteversagen, körperlicher und geistiger Verletzungen.

Wenn Sie das Programm auf anderen Websites veröffentlichen, ist ein Link zur Originalquelle erforderlich.

1. 1) Veröffentlichung von Materialien in jeglicher Form, einschließlich der Veröffentlichung von Materialien auf anderen Websites;
2. 2) Verteilung unvollständiger oder veränderter Materialien;
3. 3) Aufnahme von Materialien in Sammlungen auf beliebigen Medien;
4. 4) Erzielung kommerzieller Vorteile aus dem Verkauf oder der sonstigen Verwendung von Materialien.

Durch das Herunterladen von Materialien akzeptieren Sie die Bedingungen dieser Lizenzvereinbarung.

Herunterladen

Nach dem Entpacken des Archivs ist das Programm funktionsfähig und erfordert keine zusätzlichen Installationen.

1. Beschreibung der Turingmaschine. 3

1.1 Eigenschaften der Turingmaschine als Algorithmus. 5

2. Komplexität von Algorithmen. 7

2.1 Komplexität der Probleme... 9

3. Turingmaschine und algorithmisch unlösbare Probleme. 12

Abschluss. 16

Referenzen.. 18

Einführung

Eine Turingmaschine ist ein sehr einfaches Rechengerät. Es besteht aus einem Band von unendlicher Länge, das in Zellen unterteilt ist, und einem Kopf, der sich entlang des Bandes bewegt und Zeichen lesen und schreiben kann. Außerdem hat eine Turing-Maschine eine Eigenschaft wie einen Zustand, der als ganze Zahl von Null bis zu einem Maximalwert ausgedrückt werden kann. Je nach Zustand kann eine Turing-Maschine eine von drei Aktionen ausführen: ein Symbol in eine Zelle schreiben, eine Zelle nach rechts oder links verschieben und den internen Zustand festlegen.

Der Aufbau einer Turing-Maschine ist äußerst einfach, sie kann jedoch nahezu jedes Programm ausführen. Um all diese Aktionen durchzuführen, wird eine spezielle Regeltabelle bereitgestellt, die angibt, was für verschiedene Kombinationen aktueller Zustände und vom Band gelesener Symbole zu tun ist.

1947 erweiterte Alan Turing die Definition, um eine „universelle Turing-Maschine“ zu beschreiben. Später wurde zur Lösung bestimmter Problemklassen eine Variation davon eingeführt, die es ermöglichte, nicht eine, sondern mehrere Aufgaben auszuführen.

1. Beschreibung der Turingmaschine

Der Hintergrund der Entstehung dieser Arbeit hängt mit der Formulierung ungelöster mathematischer Probleme durch David Hilbert auf dem Internationalen Mathematikerkongress in Paris im Jahr 1900 zusammen. Eine davon war die Aufgabe, die Konsistenz des Axiomensystems der gewöhnlichen Arithmetik zu beweisen, die Hilbert später als „Entscheidbarkeitsproblem“ präzisierte – die Suche nach einer allgemeinen Methode zur Bestimmung der Erfüllbarkeit einer gegebenen Aussage in der Sprache der formalen Logik.

Turings Aufsatz gab genau die Antwort auf dieses Problem – Hilberts zweites Problem erwies sich als unlösbar. Aber die Bedeutung von Turings Aufsatz ging weit über das Problem hinaus, für das er geschrieben wurde.

Hier ist eine Beschreibung dieser Arbeit von John Hopcroft: „Bei der Arbeit an Hilberts Problem musste Turing das eigentliche Konzept einer Methode klar definieren. Ausgehend von der intuitiven Idee einer Methode als einer Art Algorithmus, d.h. ein Verfahren, das mechanisch ohne kreatives Eingreifen durchgeführt werden kann“, zeigte er, wie diese Idee in Form eines detaillierten Modells des Berechnungsprozesses verkörpert werden könnte. Das resultierende Berechnungsmodell, in dem jeder Algorithmus in eine Sequenz zerlegt wurde aus einfachen, elementaren Schritten war das logische Konstrukt, das später Turing-Maschine genannt wurde.

Eine Turing-Maschine ist eine Erweiterung des Finite-State-Machine-Modells, eine Erweiterung, die einen potenziell unendlichen Speicher mit der Fähigkeit umfasst, sich von der aktuell betrachteten Zelle zu ihrem linken oder rechten Nachbarn zu bewegen (bewegen).

Formal kann eine Turingmaschine wie folgt beschrieben werden. Gegeben sei:

eine endliche Menge von Zuständen – Q, in denen sich eine Turing-Maschine befinden kann;

endliche Menge von Bandsymbolen – Г;

Funktion δ (Übergangsfunktion oder Programm), die durch Abbildung eines Paares aus dem kartesischen Produkt Q x Г (die Maschine befindet sich im Zustand qi und betrachtet das Symbol gi) in ein Tripel des kartesischen Produkts Q x Г x (L) angegeben wird ,R) (die Maschine geht in den Zustand qi, ersetzt das gi-Symbol durch das gj-Symbol und bewegt sich um ein Bandsymbol nach links oder rechts) – Q x Г-->Q x Г x (L,R)

ein Zeichen von Г-->е (leer);

die Teilmenge Σ є Г - -> ist als Teilmenge der Eingabesymbole des Bandes definiert und е є (Г - Σ);

einer der Zustände – q0 є Q ist der Anfangszustand der Maschine.

Das zu lösende Problem wird spezifiziert, indem eine endliche Anzahl von Symbolen aus der Menge Σ є Г – Si є Σ auf Band aufgezeichnet wird:

eS1S2S3S4... ... ...Sne

Danach wird die Maschine in den Ausgangszustand überführt und der Kopf am äußersten linken nichtleeren Symbol (q0,w) installiert –, danach gemäß der angegebenen Übergangsfunktion (qi,Si) - ->(qj, Sk, L oder R) beginnt die Maschine, angezeigte Symbole zu ersetzen, den Kopf nach rechts oder links zu bewegen und in andere durch die Übergangsfunktionen vorgeschriebene Zustände zu wechseln.

Die Maschine stoppt, wenn die Übergangsfunktion für das Paar (qi,Si) nicht definiert ist.

Alan Turing schlug vor, dass jeder Algorithmus im intuitiven Sinne des Wortes durch eine äquivalente Turing-Maschine dargestellt werden kann. Diese Annahme ist als Church-Turing-These bekannt. Jeder Computer kann eine Turing-Maschine simulieren (Vorgänge zum Umschreiben von Zellen, Vergleichen und Verschieben zu einer anderen benachbarten Zelle unter Berücksichtigung von Zustandsänderungen der Maschine). Folglich kann er Algorithmen in jedem Formalismus modellieren, und aus dieser These folgt, dass alle Computer (unabhängig von Leistung, Architektur usw.) hinsichtlich der grundlegenden Fähigkeit, algorithmische Probleme zu lösen, gleichwertig sind.

1.1 Eigenschaften der Turingmaschine als Algorithmus

Am Beispiel der Turingmaschine lassen sich die Eigenschaften von Algorithmen gut erkennen. Bitten Sie die Schüler zu zeigen, dass eine Turing-Maschine alle Eigenschaften eines Algorithmus besitzt.

Diskretion. Eine Turingmaschine kann erst nach Abschluss jedes Schritts zum (k + 1)-ten Schritt übergehen, da jeder Schritt bestimmt, wie der (k + 1)-te Schritt aussehen wird.

Klarheit. Bei jedem Schritt wird ein Symbol aus dem Alphabet in die Zelle geschrieben, der Automat macht eine Bewegung (L, P, N) und die Turingmaschine geht in einen der beschriebenen Zustände.

Determinismus. Jede Zelle der Turing-Maschinentabelle enthält nur eine Option für eine Aktion. Bei jedem Schritt ist das Ergebnis eindeutig bestimmt, daher ist die Reihenfolge der Schritte zur Lösung des Problems eindeutig bestimmt, d.h. Wenn einer Turing-Maschine das gleiche Eingabewort gegeben wird, ist das Ausgabewort jedes Mal dasselbe.

Produktivität. Inhaltlich sind die Ergebnisse jedes Schrittes und der gesamten Schrittfolge eindeutig bestimmt; eine korrekt geschriebene Turingmaschine wird daher in endlich vielen Schritten in den Zustand q0 gelangen, d. h. In einer endlichen Anzahl von Schritten wird die Antwort auf die Problemfrage erhalten.

Massencharakter. Jede Turingmaschine ist über alle zulässigen Wörter aus dem Alphabet definiert, dies ist die Eigenschaft des Massencharakters. Jede Turingmaschine ist darauf ausgelegt, eine Klasse von Problemen zu lösen, d. h. Für jedes Problem wird eine eigene (neue) Turingmaschine geschrieben.

2. Komplexität von Algorithmen

Die Komplexität des Algorithmus wird durch die zu seiner Ausführung erforderliche Rechenleistung bestimmt. Die Rechenkomplexität eines Algorithmus wird häufig anhand von zwei Parametern gemessen: T (Zeitkomplexität) und S (Raumkomplexität oder Speicherbedarf). Sowohl T als auch S werden normalerweise als Funktionen von n dargestellt, wobei n die Größe der Eingabedaten ist. (Es gibt andere Möglichkeiten, Komplexität zu messen: die Anzahl der Zufallsbits, die Breite des Kommunikationskanals, die Datenmenge usw.)

Typischerweise wird die Rechenkomplexität eines Algorithmus mit der „Big O“-Notation ausgedrückt, das heißt, sie wird durch die Größenordnung der Rechenkomplexität beschrieben. Dies ist einfach der Term in der Entwicklung der Komplexitätsfunktion, der mit zunehmendem n am schnellsten wächst; alle Terme niedrigerer Ordnung werden ignoriert. Wenn beispielsweise die Zeitkomplexität eines bestimmten Algorithmus 4n2+7n+12 beträgt, liegt die Rechenkomplexität in der Größenordnung von n2, geschrieben als O(n2).

Die so gemessene Zeitkomplexität ist unabhängig von der Implementierung. Sie müssen weder die genauen Ausführungszeiten verschiedener Anweisungen kennen, noch die Anzahl der Bits, die zur Darstellung verschiedener Variablen verwendet werden, noch nicht einmal die Geschwindigkeit des Prozessors. Ein Computer mag 50 Prozent schneller sein als ein anderer, und ein dritter hat vielleicht einen doppelt so breiten Datenbus, aber die Komplexität des Algorithmus, gemessen an einer Größenordnung, wird sich nicht ändern. Das ist kein Betrug; wenn man mit Algorithmen arbeitet, die so komplex sind wie die in diesem Buch beschriebenen, kann im Vergleich zur Größenordnung der Komplexität alles andere vernachlässigt werden (bis zu einem konstanten Faktor).

Mit dieser Notation können Sie sehen, wie sich die Größe der Eingabedaten auf den Zeit- und Speicherbedarf auswirkt. Wenn beispielsweise T = O(n), dann verdoppelt eine Verdoppelung der Eingabedaten die Ausführungszeit des Algorithmus. Wenn T=O(2n), dann verdoppelt das Hinzufügen eines Bits zu den Eingabedaten die Ausführungszeit des Algorithmus.

Typischerweise werden Algorithmen nach ihrer zeitlichen oder räumlichen Komplexität klassifiziert. Ein Algorithmus heißt konstant, wenn seine Komplexität nicht von n: 0(1) abhängt. Ein Algorithmus ist linear, wenn seine Zeitkomplexität O(n) ist. Algorithmen können quadratisch, kubisch usw. sein. Alle diese Algorithmen sind polynomial, ihre Komplexität beträgt O(m), wobei m eine Konstante ist. Algorithmen mit polynomialer Zeitkomplexität werden polynomiale Zeitalgorithmen genannt

Algorithmen, deren Komplexität gleich O(tf(n)) ist, wobei t eine Konstante größer als 1 und f(n) eine Polynomfunktion von n ist, werden als exponentiell bezeichnet. Die Teilmenge exponentieller Algorithmen mit der Komplexität O(cf(n)), wobei c eine Konstante ist und f(n) schneller als eine Konstante, aber langsamer als eine lineare Funktion zunimmt, wird Superpolynom genannt.

Im Idealfall möchte ein Kryptograf behaupten, dass der beste Algorithmus zum Knacken eines entworfenen Verschlüsselungsalgorithmus eine exponentielle Zeitkomplexität aufweist. In der Praxis lauten die stärksten Aussagen, die angesichts des aktuellen Stands der rechnerischen Komplexitätstheorie gemacht werden können, der Form „Alle bekannten Angriffsalgorithmen für ein bestimmtes Kryptosystem haben eine superpolynomielle Zeitkomplexität.“ Das heißt, die uns bekannten Angriffsalgorithmen weisen eine superpolynomielle Zeitkomplexität auf, es ist jedoch noch nicht möglich zu beweisen, dass ein Angriffsalgorithmus mit polynomialer Zeitkomplexität nicht entdeckt werden kann. Die Entwicklung der Theorie der rechnerischen Komplexität könnte es eines Tages ermöglichen, Algorithmen zu erstellen, bei denen die Existenz von Algorithmen mit einer polynomialen Öffnungszeit mit mathematischer Genauigkeit ausgeschlossen werden kann.

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.

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: Unbegrenztes Band. Es ist in beide Richtungen unendlich und in Zellen unterteilt. 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: 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. 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. 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. 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. Massencharakter. Jedes Gerät wird über die im Alphabet enthaltenen gültigen Wörter definiert. Turingmaschinenfunktionen Das Lösen von Algorithmen erfordert häufig die Implementierung einer Funktion. 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 endgültigen 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 Alphabet eines Turing-Geräts, das mit Binärzahlen arbeitet, 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 eine Abfolge der folgenden Aktionen ausführt: Schreiben eines Symbols des externen Alphabets an eine Position, auch an eine leere, und Ersetzen des darin befindlichen Elements es, einschließlich eines leeren. Einen Zellenschritt nach links oder rechts verschieben. Ändern Sie Ihren inneren Zustand. Beim Schreiben von Programmen für jedes Zeichen- oder Positionspaar ist es daher notwendig, drei Parameter genau zu beschreiben: ai – ein Element aus dem ausgewählten Alphabet A, die Richtung der Wagenverschiebung („←“ nach links, „→“ nach rechts, „Punkt“ – keine Bewegung) und qk – neuer Zustand des Geräts. Beispielsweise hat Befehl 1 „←“ q2 die Bedeutung „Ersetzen Sie das Zeichen durch 1, bewegen Sie den Schlittenkopf eine Schrittzelle nach links und.“ Machen Sie einen Übergang zum Zustand q2“.