Sagen wir vor langer Zeit ... Aber tatsächlich wurden vor der Entwicklung der Turing-Maschine Maschinen geschaffen, um verschiedene Aktionen auszuführen. Zum Beispiel musst du den Logarithmus nehmen, nuka, aber lass uns eine Maschine vernieten, die die Zahl liest und den Logarithmus nimmt. Oder Sie brauchen, sagen wir, zwei Zahlen zum Addieren - hier ist eine Maschine zum Addieren von zwei Zahlen. Und auch jetzt gibt es solche Maschinen, zum Beispiel Taschenrechner. Was können Sie machen? Addiere, subtrahiere, multipliziere und konstruiere - sogar den Kosinus oder Sinus. Es stellt sich heraus, dass diese dummen Maschinen, abgesehen von den darin aufgezeichneten Aktionen, nichts ausführen können und können.

Es wäre also sehr interessant, eine solche Maschine zu entwickeln, die keine Zahlen und keine Symbole, sondern einen Algorithmus liest und diesen ausführt, dh eine programmierbare Maschine erstellt. Dies hat Turing getan (ich werde sagen, dass es neben Turing noch viele solcher Abstraktionen gibt). Und er hat ein Modell eines solchen Autos entwickelt. Es stellte sich heraus, dass Sie zum Ausführen komplexer Algorithmen nur einen Schlitten, ein endloses Band und die Möglichkeit benötigen, die auf dem Band aufgezeichneten Werte zu ändern und sich darauf zu bewegen. Es stellt sich heraus, dass diese Abstraktion tatsächlich in eine echte Maschine umgewandelt werden kann, die einzige, mit der Einschränkung, dass wir der Maschine kein Endlosband liefern können, aber wir können ein sehr langes Band herstellen;)

Rückzug. Über die Funktionsweise der Turingmaschine braucht man eigentlich gar nicht zu reden, sie ist wie gesagt sehr leicht zu finden. Daher gehen wir davon aus, dass Sie bereits wissen, wie es funktioniert.

Nun, die Turing-Maschine führt einige einfache Algorithmen aus, das ist unbestreitbar. Aber was ist mit den kniffligen? Und wie organisiert man zum Beispiel einen Zyklus mit MT? Oder wie findet man Verzweigungen heraus? Es stellt sich heraus, dass es Theoreme gibt, die beweisen, dass MT Schleifen und Verzweigungen ausführen kann, was uns sagt, dass es mit einem sehr einfachen Mechanismus möglich ist, Programme aus einfachen Blöcken wie Verzweigungen und Schleifen zusammenzusetzen, was bedeutet, dass alles, was programmiert werden kann, möglich ist programmiert werden. Und hier sollte es theoretisch eine Erklärung geben, dass es auch nicht berechenbare Funktionen und damit unlösbare Probleme gibt und diese Probleme mit Hilfe von MT nicht gelöst werden können. So.

Aber niemand hat etwas Cooleres erfunden als eine Turing-Maschine, daher können alle Programmiersprachen, die wir heute verwenden, nicht mehr als eine Turing-Maschine programmieren. Daraus entstand das Konzept der Turing-Vollständigkeit, was bedeutet, dass eine Sprache (oder etwas anderes) Turing-vollständig ist, wenn sie alle Algorithmen schreiben kann, die auf einer Turing-Maschine laufen. Und Sie können beweisen, dass eine Sprache Turing-vollständig ist, indem Sie einen Emulator einer Turing-Maschine darin schreiben. Das sind die Kuchen.

Aus mathematischer Sicht ist Post Quatsch, aber es ist klar, wofür wir eine Turing-Maschine brauchten. Nun, eigentlich ist es ein interessantes Rätsel, Algorithmen für diese Maschine zu schreiben. Ich glaube diejenigen, die sagen, dass er nach der Programmierung von exp (x) auf einer Turing-Maschine wirklich verstanden hat, was ein Algorithmus ist. Habe es noch nicht ausprobiert, aber es ist eine interessante Herausforderung.

Eine Turingmaschine ist eine Sammlung der folgenden Objekte

• 1) äußeres Alphabet A = (a 0, a 1,…, a n);
• 2) das innere Alphabet Q = (q 1, q 2,…, q m) ist eine Menge von Zuständen;
• 3) eine Reihe von Steuerzeichen (P, L, S)
• 4) ein in beide Richtungen unendliches Band, das in Zellen unterteilt ist, in die zu jedem diskreten Zeitpunkt nur ein Zeichen aus dem Alphabet A geschrieben werden kann;
• 5) ein Steuergerät, das sich in einem von vielen Zuständen befinden kann

Das Symbol für eine leere Zelle ist der äußere Alphabetbuchstabe a 0.

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

Das Steuergerät kann sich entlang des Bandes nach links und rechts bewegen, die Buchstaben des Alphabets A lesen und in die Zellen des Bandes schreiben. Das Steuergerät arbeitet nach den folgenden Befehlen:

q i a j> a p X q k

Der Eintrag bedeutet folgendes: Wenn sich das Steuergerät im Zustand qi befindet und der Buchstabe aj in die beobachtete Zelle geschrieben wird, dann wird (1) ap statt aj in die Zelle geschrieben, (2) die Maschine geht zur nächsten rechte Zelle von der gerade angesehenen Zelle, wenn X = P, oder die nächste linke Zelle anzeigen, wenn X = L, oder weiterhin die gleiche Zelle des Bandes überwachen, wenn X = C, (3) das Kontrollgerät geht in den Zustand q k.

Da der Betrieb der Maschine durch die Bedingung vollständig durch ihren Zustand q zu einem bestimmten Zeitpunkt und den Inhalt der zu diesem Zeitpunkt überwachten Zelle bestimmt wird, gibt es für jede mögliche Konfiguration q i a j genau eine Regel. Nur für den Endzustand, in dem das Auto anhält, gibt es keine Regeln. Daher enthält ein Turingmaschinenprogramm mit externem Alphabet A = (a0, a1,…, an) und internem Q = (q1, q2,…, qm) höchstens 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 das Bild des Bandes der Maschine mit den darauf gebildeten Informationen zu Beginn des k-ten Schrittes (oder ein Wort im Alphabet A, das am Anfang des k-ten auf das Band geschrieben wurde). Schritt), die angibt, welche Zelle in diesem Schritt betrachtet wird und in welchem ​​Zustand sich das Auto befindet. Nur Endkonfigurationen machen Sinn, d.h. solche, bei denen alle Zellen des Bandes mit Ausnahme einer endlichen Zahl leer sind. Eine Konfiguration wird als endgültig bezeichnet, wenn der Zustand der Maschine endgültig ist.

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

Wir werden sagen, dass ein nicht leeres Wort b im Alphabet A (a 0) = (a 1, ..., an) von der Maschine in der Standardposition wahrgenommen wird, wenn es in aufeinanderfolgenden Zellen des Bandes geschrieben wird, alle anderen Zellen sind leer, und die Maschine betrachtet die Zelle ganz links oder ganz rechts von denen, in denen das Wort b steht. Die Standardposition wird als Anfangs- (End-)Position 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 Turingmaschine in den Endzustand überführt, dann gilt sie für b, ansonsten gilt sie nicht für b (die Maschine läuft auf unbestimmte Zeit)

Betrachten wir ein Beispiel:

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

q 1 0 > 1 L q 2;

q 1 1 > 0 C q 2;

q 2 0 > 0 P q 0;

q 2 1 > 1 C q 1;

Dieses Programm kann mit einer Tabelle geschrieben werden

Im ersten Schritt wird der folgende Befehl ausgeführt: q 1 0> 1 Л q 2 (das Steuergerät befindet sich im Zustand q1 und der Buchstabe 0 wird in die beobachtete Zelle geschrieben, 1 wird in die Zelle anstelle von 0 geschrieben, die Kopf nach links verschoben, das Steuergerät geht in den Zustand q2) in Als Ergebnis entsteht an der Maschine folgende Konfiguration:

Schließlich wird nach Ausführung des Befehls q 2 0> 0 P q 0 die Konfiguration erstellt

Diese Konfiguration ist endgültig, da sich die Maschine im Stoppzustand q 0 befand.

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

Die resultierende Folge von Konfigurationen kann kürzer geschrieben werden (der Inhalt der beobachteten Zelle wird rechts vom 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 Regel (Algorithmus) zur Transformation von Wörtern des Alphabets A Q, d.h. Konfigurationen. Um eine Turing-Maschine zu definieren, müssen Sie also ihr externes und internes Alphabet sowie ein Programm angeben und angeben, welches der Symbole eine leere Zelle und den Endzustand bezeichnet.

Die Turing-Maschine ist eine der faszinierendsten und aufregendsten intellektuellen Entdeckungen des 20. Jahrhunderts. Es ist ein einfaches und nützliches abstraktes Berechnungsmodell (Computer und digital), das allgemein genug ist, um jede Computeraufgabe zu implementieren. Dank seiner einfachen Beschreibung und mathematischen Analyse bildet es das Fundament der theoretischen Informatik. Diese Forschung führte zu einem tieferen Verständnis von digitalen Computern und der Infinitesimalrechnung, einschließlich der Erkenntnis, dass es einige Rechenprobleme gibt, die auf Computern allgemeiner Benutzer nicht gelöst werden können.

Alan Turing versuchte, das primitivste Modell eines mechanischen Geräts zu beschreiben, das die gleichen grundlegenden Fähigkeiten wie ein Computer aufweisen sollte. Turing beschrieb die Maschine erstmals 1936 in einem Artikel "On Computable Numbers with an application to the problem of solvability", der in den Proceedings of the London Mathematical Society erschien.

Eine Turingmaschine ist ein Rechengerä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 Zeichen trägt - "0" oder "1". Der Mechanismus dient dazu, sowohl als Ein- und Ausstiegsmittel als auch als Arbeitsspeicher zum Speichern der Ergebnisse von Zwischenstufen von Berechnungen zu dienen. Woraus das Gerät besteht Jede dieser Maschinen besteht aus zwei Komponenten: Unbegrenztes Band. Es ist in beide Richtungen unendlich und in Zellen unterteilt. Automatisches maschinengesteuertes Programm, Kopfscanner zum Lesen und Schreiben von Daten. Es kann jederzeit in einem von vielen Staaten sein.

Jede Maschine verbindet zwei endliche Datenreihen: das Alphabet der eingehenden Symbole A = (a0, a1, ..., am) und das Alphabet der Zustände 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 wird als Anfangszustand bezeichnet - die Maschine beginnt mit ihren Berechnungen, indem sie in ihr am Anfang steht. Das Eingabewort befindet sich auf dem Band, ein Buchstabe hintereinander an jeder Position. Auf beiden Seiten davon befinden sich nur leere Zellen.

So funktioniert der Mechanismus

Eine Turing-Maschine unterscheidet sich grundlegend von Computergeräten - ihr Speichergerät hat ein endloses Band, während ein solches Gerät bei digitalen Geräten einen Streifen einer bestimmten Länge hat. Jede Aufgabenklasse wird von nur einer gebauten Turingmaschine gelöst. Probleme anderer Art beinhalten das Schreiben eines neuen Algorithmus. Die Steuervorrichtung kann sich in einem Zustand in jede Richtung entlang des Bandes bewegen. Es schreibt in die Zellen und liest die Zeichen des endgültigen Alphabets. Während der Bewegung wird ein leeres Element ausgewählt, das Positionen füllt, die keine Eingabedaten enthalten. Der Turing-Maschinen-Algorithmus definiert die Übergangsregeln für das Steuergerät. Sie stellen dem Schreib-Lese-Kopf folgende Parameter ein: Schreiben eines neuen Zeichens in eine Zelle, Wechseln in einen neuen Zustand, Bewegen nach links oder rechts entlang des Bandes.

Eigenschaften des Mechanismus

Die Turing-Maschine hat wie andere Computersysteme ihre inhärenten Eigenschaften, die den Eigenschaften von Algorithmen ähneln: Diskretion. Die digitale Maschine geht erst zum nächsten Schritt n + 1 über, nachdem der vorherige abgeschlossen ist. Jede abgeschlossene Stufe bezeichnet das, was n + 1 sein wird. Verständlichkeit. Das Gerät führt nur eine Aktion für dieselbe Zelle aus. Es schreibt ein Zeichen aus dem Alphabet und macht eine Bewegung: nach links oder rechts. Determinismus. Jede Position im Mechanismus entspricht einer einzelnen Option zur Durchführung eines bestimmten Schemas, und in jeder Phase sind die Aktionen und die Reihenfolge ihrer Umsetzung eindeutig. Wirksamkeit. Das genaue Ergebnis jeder Stufe wird von der Turing-Maschine bestimmt. Das Programm führt den Algorithmus aus und geht in endlich vielen Schritten in den Zustand q0 über. Masse Charakter. Jedes Gerät ist über gültige alphabetische Wörter definiert. Turing-Maschinenfunktionen Das Lösen von Algorithmen erfordert oft die Implementierung einer Funktion. Je nach Möglichkeit, die Kette zur Berechnung zu schreiben, wird die Funktion algorithmisch entscheidbar oder unentscheidbar genannt. Als Menge natürlicher oder rationaler Zahlen, Wörter in einem endlichen Alphabet N für eine Maschine, betrachten wir eine Folge einer Menge B - Wörter im Rahmen eines binären Codealphabets B = (0.1). Außerdem berücksichtigt das Berechnungsergebnis den "undefinierten" Wert, der auftritt, wenn der Algorithmus "hängt". Für die Implementierung der Funktion ist es wichtig, dass eine formale Sprache in einem endlichen Alphabet existiert und das Problem der Erkennung korrekter Beschreibungen lösbar ist.

Geräteprogramm

Programme für den Turing-Mechanismus werden mit Tabellen formatiert, in denen die erste Zeile und Spalte Symbole des externen Alphabets und die Werte möglicher interner Zustände des Automaten enthalten - das interne Alphabet. Tabellendaten sind Befehle, die von einer Turing-Maschine wahrgenommen werden. Die Problemlösung ist wie folgt: Der vom Kopf gelesene Buchstabe in der Zelle, über der er sich gerade befindet, und der interne Zustand des Kopfes der Maschine bestimmen, welcher der Befehle ausgeführt werden muss. Insbesondere befindet sich ein solcher Befehl am Schnittpunkt der Symbole des externen und internen Alphabets, die sich in der Tabelle befinden.

Computerkomponenten

Um eine Turingmaschine zur Lösung eines bestimmten Problems zu bauen, müssen die folgenden Parameter dafür bestimmt werden. Externes Alphabet. Dies ist eine endliche Menge von Symbolen, die mit dem Zeichen A bezeichnet werden und deren Bestandteile mit Buchstaben bezeichnet 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 ununterbrochene Reihe von Buchstabensymbolen, die auf einem Band aufgezeichnet sind, wird als Wort bezeichnet. Ein Automat ist ein Gerät, das ohne menschliches Zutun funktioniert. In einer Turingmaschine hat sie mehrere verschiedene Zustände zur Lösung von Problemen und bewegt sich unter bestimmten Bedingungen von einer Position in eine andere. Die Sammlung solcher Wagenzustände ist das interne Alphabet. Es hat eine Buchstabennotation der Form Q = (q1, q2 ...). Eine dieser Positionen - q1 - sollte die erste sein, dh das Programm startet. Ein weiteres notwendiges Element ist der Zustand q0, der endgültig ist, dh der das Programm beendet und das Gerät in die Stoppposition bringt.

Sprungtabelle.

Diese Komponente ist ein Algorithmus für das Verhalten des Gerätewagens, abhängig vom Zustand der Maschine und dem Wert des gerade gelesenen Zeichens.

Algorithmus für den Automaten

Während des Betriebs wird der Schlitten des Turing-Geräts von einem Programm gesteuert, das bei jedem Schritt die folgende Sequenz durchführt: Schreiben eines externen Alphabetsymbols an eine Position, einschließlich eines leeren, Ersetzen eines Elements darin, einschließlich eines leeren. Verschieben Sie einen Zellenschritt nach links oder rechts. Ändern Sie Ihren inneren Zustand. Beim Schreiben von Programmen für jedes Zeichenpaar oder jede Position müssen daher drei Parameter genau beschrieben werden: ai - ein Element aus dem ausgewählten Alphabet A, die Richtung der Wagenverschiebung ("←" nach links, "→" nach nach rechts, "Punkt" - keine Bewegung) und qk - neuer Zustand des Geräts Zum Beispiel hat Befehl 1 "←" q2 den Wert "Ersetze das Zeichen durch 1, bewege den Schlittenkopf einen Zellenschritt nach links und mache die Übergang in den Zustand q2".

Wir lösen oft Probleme unterschiedlicher Komplexität: alltägliche, mathematische usw. Manche sind leicht zu lösen, manche müssen wir viel nachdenken, für manche finden wir nie eine Lösung.

Im allgemeinen Fall kann die Lösung des Problems (falls vorhanden) durch eine endliche Anzahl von Elementaraktionen beschrieben werden.

Zum Beispiel eine quadratische Gleichung lösen:

1. Bringen Sie die Gleichung in die kanonische Form \ (a x ^ 2 + b x + c = 0 \)
2. Wenn \ (a = 0 \), dann ist dies eine lineare Gleichung mit der Lösung \ (x = \ frac (-c) (b) \). Das Problem ist gelöst worden. Fahren Sie andernfalls mit Schritt 3 fort.
3. Berechnen Sie die Diskriminante \ (D = b ^ 2-4 a c \)
4. Berechnen Sie die Lösungen der Gleichung \ (x_ (1,2) = \ frac (-b \ pm \ sqrt (D)) (2 a) \)... Das Problem ist gelöst worden.

Sie können das folgende intuitive Konzept des Algorithmus einführen:

Der Algorithmus ist ein Satz von Anweisungen, der die Reihenfolge der Aktionen des Executors beschreibt, um das Ergebnis der Lösung des Problems in einer endlichen Anzahl von Aktionen für einen beliebigen Satz von Anfangsdaten zu erzielen.

Dies ist natürlich keine strenge Definition, aber es beschreibt die Essenz des Konzepts eines Algorithmus.

Algorithmen werden basierend auf einem bestimmten . kompiliert Künstler, und sollte dementsprechend in einer Sprache verfasst sein, die der ausübende Künstler verstehen kann.

Der Ausführende des Algorithmus kann eine Person oder ein Computer oder eine andere Maschine, beispielsweise ein Webstuhl, sein.

Die folgenden Eigenschaften der Algorithmen werden hervorgehoben:

Die Diskretion des Algorithmus sollte eine bestimmte Abfolge einzelner, klar definierter Schritte (Aktionen) sein. Jede dieser Aktionen muss zeitlich begrenzt sein. Determinismus bei jedem Schritt des Algorithmus, der nächste Schritt wird eindeutig durch den aktuellen Zustand des Systems bestimmt. Infolgedessen gibt der Algorithmus bei denselben Ausgangsdaten jedes Mal die gleichen Ergebnisse zurück, egal wie oft er ausgeführt wird. Verständlichkeit Der Algorithmus sollte in einer für den Ausführenden verständlichen Sprache formuliert sein. Bei einem Computer darf der Algorithmus nur solche Anweisungen verwenden, die dem Computer bekannt sind und deren Ergebnis genau definiert ist. Endlichkeit Der Algorithmus muss in einer endlichen Anzahl von Schritten abgeschlossen werden. Die Massivität des Algorithmus sollte auf verschiedene Sätze von Eingabedaten anwendbar sein. Mit anderen Worten, der Algorithmus muss zum Lösen geeignet sein Klasse Aufgaben. Zurück zum quadratischen Beispiel: Der Algorithmus eignet sich zum Lösen von von allen quadratische Gleichungen, nicht nur eine oder mehrere. Die Wirksamkeit des Algorithmus muss mit einem bestimmten Ergebnis enden. Sagen wir, indem man ein Problem löst oder herausfindet, dass es keine Lösungen gibt. Wenn der Algorithmus nicht zu einem Ergebnis führt, ist nicht klar, warum er überhaupt benötigt wird.

Nicht jeder Weg, ein Problem zu lösen, ist ein Algorithmus. Nehmen wir an, der Algorithmus impliziert keine Wahl. Zum Beispiel sind die meisten Rezepte keine Algorithmen, weil sie Phrasen wie „Salz nach Geschmack“ verwenden. Dadurch wird die Forderung des Determinismus verletzt.

Nicht für jedes Problem, für das es eine Lösung gibt, gibt es auch einen Lösungsalgorithmus. So ist beispielsweise das Problem der Bilderkennung noch weitgehend ungelöst und schon gar nicht mit einem rigorosen Algorithmus. Die Verwendung neuronaler Netze führt jedoch zu recht guten Ergebnissen.

Normalerweise gibt es Mengen für den Algorithmus zulässig Eingabedaten. Es wäre seltsam zu versuchen, den Gleichungslösungsalgorithmus auf das Kochen von Abendessen anzuwenden oder umgekehrt.

Darüber hinaus ist auch die Menge möglicher Handlungen des Darstellers begrenzt, da, wenn irgendwelche Handlungen erlaubt wären, darunter auch „inakzeptabel“ sein müssten.

Strenge Algorithmusdefinition

Die Definition des obigen Algorithmus ist nicht streng. Dies schafft einige Schwierigkeiten. Insbesondere ist es mit einer solchen Definition unmöglich, rigoros zu beweisen, ob eine gegebene Klasse von Problemen durch einen Algorithmus lösbar ist.

Es stellt sich heraus, dass es eine Klasse gibt algorithmisch unlösbare Probleme- Probleme, für die es unmöglich ist, einen Lösungsalgorithmus zusammenzustellen. Um jedoch die algorithmische Unentscheidbarkeit rigoros zu beweisen, müssen Sie zunächst eine rigorose Definition des Algorithmus haben.

In den 20-30er Jahren des 20. Jahrhunderts arbeiteten verschiedene Mathematiker an dem Problem einer strengen Definition des Algorithmus, insbesondere Alan Turing, Emil Leon Post, Andrei Andreevich Markov, Andrei Nikolaevich Kolmogorov, Alonzo Church und andere. Ihre Arbeit führte schließlich zur Entstehung und Entwicklung der Theorie der Algorithmen, der Theorie der Infinitesimalrechnung und verschiedener Ansätze der Infinitesimalrechnung und übrigens der Programmierung im Allgemeinen. Eines der Ergebnisse ihrer Arbeit war die Entstehung mehrerer strenger Definitionen des Algorithmus, die auf unterschiedliche Weise eingeführt wurden, aber einander gleichwertig sind.

Wir werden ausführlich auf die Definition von Turing eingehen und die äquivalenten Definitionen von Post, Church und Markov oberflächlich analysieren.

Turing Maschine

Um eine formale Definition eines Algorithmus einzuführen, entwickelte und beschrieb Turing eine abstrakte Rechenmaschine, die als Turing-Rechenmaschine oder einfach als Turing-Maschine bezeichnet wird.

Alan Turing (1912-1954)

Ein englischer Mathematiker, Logiker, Kryptograf, möglicherweise der erste „Hacker“ der Welt, stand an der Spitze der Informatik und der Theorie der künstlichen Intelligenz. Er trug maßgeblich zum Sieg der Alliierten im Zweiten Weltkrieg bei.

Die Eingabedaten für die Turingmaschine sind die Wörter zusammengestellt mit Hilfe eines bestimmten Alphabet, das heißt die Menge Zeichen.

Das Ergebnis der Arbeit der Turingmaschine sind auch Worte.

Das Wort, auf das der Algorithmus angewendet wird, heißt Eingang... Das Wort, das von der Arbeit kommt Wochenende.

Die Menge der Wörter, auf die der Algorithmus angewendet wird, heißt der Umfang des Algorithmus.

Streng genommen ist es unmöglich zu beweisen, dass irgendein Objekt in Form von Wörtern dargestellt werden kann, die in einem Alphabet zusammengesetzt sind - dazu bräuchten wir eine strenge Definition des Objekts. Sie können jedoch überprüfen, ob jeder zufällige Algorithmus, der mit Objekten funktioniert, so umgewandelt werden kann, dass er mit Wörtern funktioniert, ohne das Wesen des Algorithmus zu ändern.

Beschreibung der Turingmaschine

Die Turing-Maschine enthält ein in beide Richtungen unbegrenztes Band, das in Zellen unterteilt ist, und ein Steuergerät (auch bekannt als Lese-/Schreibkopf, oder einfach Maschine), die sich in einem von vielen Staaten befinden kann. Die Anzahl der möglichen Zustände des Steuergeräts ist endlich und genau vorgegeben.

Das Steuergerät kann sich entlang des Bandes nach links und rechts bewegen, Zeichen eines endlichen Alphabets lesen und in Zellen schreiben. Es wird ein spezielles Leerzeichen mit der Bezeichnung \ (a_0 \) oder \ (\ Lambda \) zugewiesen, das alle Zellen des Bandes ausfüllt, außer denen (endliche Zahl), auf die die Eingabedaten geschrieben werden.

Der Controller arbeitet nach Übergangsregeln, die den von einer bestimmten Turingmaschine implementierten Algorithmus darstellen. Jede Übergangsregel weist die Maschine abhängig vom aktuellen Zustand und dem in der aktuellen Zelle beobachteten Symbol an, ein neues Symbol in diese Zelle zu schreiben, in einen neuen Zustand zu wechseln und eine Zelle nach links oder rechts zu verschieben. Einige Zustände der Turing-Maschine können als Terminal markiert werden, und der Übergang zu einem von ihnen bedeutet das Ende der Arbeit, den Stopp des Algorithmus.

Obwohl die Turing-Maschine ein abstraktes Konzept ist, reicht es, sich eine solche Maschine einfach vorzustellen (wenn auch mit einem endlichen Band), und es gibt sogar Demo-Maschinen wie diese:

Es ist praktisch, den Algorithmus für eine Turing-Maschine in Form einer Tabelle darzustellen: Die Spalten der Tabelle entsprechen dem aktuellen (beobachteten) Symbol auf dem Band, die Zeilen entsprechen dem aktuellen Zustand der Maschine und die Zellen enthalten der von der Maschine auszuführende Befehl.

Der Befehl wiederum kann folgenden Aufbau haben:

\ [a_k \ left \ lbrace \ begin (Matrix) L \\ N \\ R \ end (Matrix) \ right \ rbrace q_m \]

Zuerst kommt das Alphabetsymbol, das in die aktuelle Zelle \ (a_k\) geschrieben werden muss, dann ist die Bewegung der Maschine nach links (L), nach rechts (P) oder nirgendwo (an Ort und Stelle bleiben, H) angegeben. Am Ende wird ein neuer Zustand angezeigt, in den der Automat \(q_m\) gehen soll.

Die Tabellenzelle wird durch das aktuelle Symbol \ (a_i \) und den aktuellen Zustand der Maschine \ (q_j \) eindeutig definiert.

Lassen Sie uns zustimmen, dass zu Beginn der Arbeit die Turing-Maschine in ist Ausgangszustand, bezeichnet mit \ (q_1 \), und beim Übergang zu Zustand stoppen\ (q_0 \) der Algorithmus ist abgeschlossen und die Maschine stoppt.

Beispiel

Lassen Sie uns einen Algorithmus für eine Turingmaschine zusammenstellen, der 1 zum Eingabewort addiert, das eine Dezimalzahl ist.

Deskriptiv lässt sich der Algorithmus dann wie folgt formulieren:

1. Bewegen Sie sich nach rechts und suchen Sie den Anfang des Eingabeworts
2. Gehen Sie nach rechts und suchen Sie das Ende des Eingabeworts
3. Addiere eins zum aktuellen Bit des Eingangsworts. Wenn eine Zahl von 0 bis 8 vorhanden ist, beenden Sie. Andernfalls schreiben Sie 0, gehen nach links und kehren zu Schritt 3 zurück.

Schreiben wir diesen Algorithmus in Form einer Tabelle. Das Alphabet besteht aus Zahlen von 0 bis 9 und einem Leerzeichen \ (\Lambda\). Wir benötigen auch 4 Zustände des Automaten, den Stoppzustand zählend, entsprechend den Schritten in der Beschreibung des Algorithmus.

Vereinbaren wir, dass der Anfangszustand \ (1 \) die Suche nach dem Anfang des Eingabewortes ist, \ (2 \) die Suche nach dem Ende des Eingabewortes, \ (3 \) die Addition von 1.

\ (_ (q_j) \ umgekehrter Schrägstrich ^ (a_i) \)	Λ	0	1	2	3	4	5	6	7	8	9
1	ΛП1	0H2	1H2	2H2	3H2	4H2	5H2	6H2	7H2	8H2	9H2
2	3	0P2	1P2	2P2	3P2	4P2	5P2	6P2	7P2	8P2	9P2
3	1H0	1H0	2H0	3H0	4H0	5H0	6H0	7H0	8H0	9H0	0L3

Lassen Sie uns die Funktionsweise dieses Algorithmus anhand eines Beispiels verfolgen. Die erste Zeile entspricht dem Band, die zweite gibt die Position der Maschine und ihren aktuellen Zustand an.

	1	9	9
1

Im Zustand 1 befindet sich der Automat über einer leeren Zelle. Der entsprechende Befehl aus der Tabelle „ΛП1“, dh die Zelle leer lassen, nach rechts gehen und im Zustand 1 bleiben:

	1	9	9
	1

Nun überwacht der Automat den Wert „1“. Entsprechender Befehl „1H2“, d. h. „1“ in Zelle lassen, nicht bewegen und in den Zustand „2“ wechseln:

	1	9	9
	2

Im Zustand „2“ beobachtet die Maschine den Wert „1“. Der entsprechende Befehl „1P2“, also „1“ verlassen, nach rechts gehen und im Zustand „2“ bleiben:

Die Situation wiederholt sich:

Nun führt die Maschine im Zustand 3 und unter Beachtung des Symbols „9“ den Befehl „0L3“ aus:

	1	9	0
		3

Die Situation wiederholt sich:

Zustand „0“ - Stoppzustand. Der Algorithmus ist abgeschlossen.

Formale Beschreibung

Mathematisch lässt sich eine Turingmaschine wie folgt beschreiben:

Turing-Maschine (MT)

Dies ist ein System der Form \ (\ (A, a_0, Q, q_1, q_0, T, \tau\) \), wo

• \ (A \) - eine endliche Menge von Symbolen des Alphabets MT
• \ (a_0 \ in A \) - leeres Alphabetzeichen
• \ (Q \) ist eine endliche Menge von Zuständen von MT
• \ (q_1 \ in Q \) - Anfangszustand von MT
• \ (q_0 \ in Q \) - Endzustand von MT (Stoppzustand)
• \ (T = \ (A, P, H \) \) ist die Menge der Verschiebungen MT
• \ (\ tau \) - MT-Programm, d. h. eine Funktion, die die Abbildung spezifiziert \ (\tau: A \ mal Q \ Backslash \ (q_0 \) \ rightarrow A \ mal T \ mal Q \)

Der Schlüssel in der Theorie der Algorithmen ist Turings Abschlussarbeit.

Locker formuliert ist Turings These wie folgt formuliert:

Turings These Für jedes algorithmisch lösbare Problem gibt es eine Turingmaschine, die dieses Problem löst. andernfalls gibt es für jeden Algorithmus eine äquivalente Turingmaschine.

Turings These erlaubt es uns, über Algorithmen zu sprechen, die einen ziemlich einfachen mathematischen Apparat verwenden. Außerdem ist die Turingmaschine selbst Universalantrieb, und die bloße Möglichkeit, eine solche imaginäre Maschine zu schaffen, ist zu einem Grund geworden, über die Schaffung einer universellen Computertechnologie zu sprechen.

Alternative Algorithmus-Definitionen

Neben der Turing-Maschine gibt es mehrere unabhängige Definitionen, die der Turing-Definition entsprechen.

Insbesondere die Definition durch die Post-Maschine, durch den Lambda-Kalkül der Kirche, den normalen Markov-Algorithmus.

Betrachten wir diese Methoden.

Postautomat

Ein Jahr nach Turing schlug der amerikanische Mathematiker Emile Leon Post unabhängig eine andere abstrakte universelle Rechenmaschine vor, die im Vergleich zur Turing-Maschine etwas vereinfacht ist.

Der Automat der Post arbeitet mit einem zweistelligen Alphabet, und der interne Zustand des Automaten wird ersetzt durch Programmzeile.

Ansonsten ähnelt die Post-Maschine der Turing-Maschine: Es gibt einen Automaten und es gibt ein endloses Band mit Zellen.

Die Post Machine kann folgende Befehle ausführen:

1. Schreiben Sie 1, gehen Sie zur i-ten Zeile des Programms
2. Schreiben Sie 0, gehen Sie zur i-ten Zeile des Programms
3. Nach links verschieben, zur i-ten Zeile des Programms gehen
4. Nach rechts verschieben, zur i-ten Zeile des Programms gehen
5. Bedingter Sprung: Wenn in der beobachteten Zelle 0 ist, gehe zur i-ten Zeile des Programms, andernfalls gehe zur j-ten Zeile des Programms.
6. Halt.

Die Post-Maschine hat auch mehrere verbotene Befehle:

1. In Zelle 1 schreiben, wenn bereits 1 vorhanden ist.
2. Schreiben in Zelle 0, wenn bereits 0 vorhanden ist.

Solche Ereignisse führen zu einem Absturz.

Um Programme für die Postmaschine zu schreiben, können Sie die folgende Notation verwenden:

1. ∨ i - schreibe 1, gehe zur i-ten Zeile des Programms
2. × i - schreibe 0, gehe zur i-ten Zeile des Programms
3. ← i - linke Verschiebung ausführen, zur i-ten Zeile des Programms gehen
4. → i - schieben Sie nach rechts, gehen Sie zur i-ten Zeile des Programms
5. ? ich; j - Bedingter Sprung: Wenn in der beobachteten Zelle 0 ist, gehe zur i-ten Zeile des Programms, andernfalls - gehe zur j-ten Zeile des Programms.
6. ! - halt.

Beispielprogramm:

1. → 2 2.? 1; 3 3. × 4 4. ← 5 5.!

Dieses Programm löscht das erste Etikett (1) rechts von der Startposition der Maschine und stoppt die Maschine in der Zelle links davon.

Im Großen und Ganzen ist das Auto von Post der Vorgänger Imperativ Programmiersprachen, zum Beispiel C, Fortran usw.

Die Post-Maschine entspricht der Turing-Maschine. Mit anderen Worten, Sie können für jedes Programm für eine Turing-Maschine ein entsprechendes Programm für eine Post-Maschine schreiben und umgekehrt.

Eine der wichtigen Konsequenzen dieser Äquivalenz ist, dass Jedes Alphabet kann auf Binärcode reduziert werden.

Ähnlich wie Turings Abschlussarbeit gibt es auch Posts Abschlussarbeit.

Posts These kann jeder Algorithmus in Form einer Postmaschine dargestellt werden.

Normaler Markov-Algorithmus

Die normalen Markov-Algorithmen wurden entwickelt, um auf Wörter in verschiedenen Alphabeten angewendet zu werden.

Die Definition eines normalen Algorithmus besteht aus zwei Teilen:

1. Alphabet Algorithmus
2. Schemata Algorithmus

Der Algorithmus selbst wird angewendet auf Wörter, d. h. Zeichenfolgen Alphabet.

Das Schema eines normalen Algorithmus heißt endliche geordnete Menge sogenannter Substitutionsformeln, von denen jeder sein kann einfach oder der endgültige... Ausdrücke der Form \ (L \ bis D \) werden einfache Substitutionsformeln genannt, wobei \ (L \) und \ (D \) zwei beliebige Wörter sind, die aus dem Alphabet des Algorithmus zusammengesetzt sind (genannt links bzw. rechts Seiten der Substitutionsformel). In ähnlicher Weise sind endgültige Substitutionsformeln Ausdrücke der Form \ (L \ bis \ cdot D \), wobei \ (L \) und \ (D \) zwei beliebige Wörter sind, die aus dem Alphabet des Algorithmus zusammengesetzt sind.

Es wird davon ausgegangen, dass die Hilfszeichen \ (\ bis \) und \ (\ bis \ cdot \) nicht zum Alphabet des Algorithmus gehören.

Der Vorgang der Anwendung des normalen Algorithmus auf ein beliebiges Wort \ (V \) ist die folgende Abfolge von Aktionen:

1. Sei \ (V "\) das Wort, das im vorherigen Schritt des Algorithmus erhalten wurde (oder das ursprüngliche Wort, wenn der aktuelle Schritt der erste ist).
2. Wenn es keine Substitution zwischen den Substitutionsformeln gibt, deren linke Seite in \ (V "\) enthalten wäre, dann wird die Arbeit des Algorithmus als abgeschlossen betrachtet, und das Ergebnis dieser Arbeit ist das Wort \ (V" \ ).
3. Andernfalls wird unter den Substitutionsformeln, deren linke Seite in \ (V "\) enthalten ist, die allererste ausgewählt.
4. Von allen möglichen Darstellungen des Wortes \ (V "\) in der Form \ (RLS \) (wobei \ (R \) ein Präfix und \ (L \) ein Suffix ist), wird eine so gewählt, dass \ ( R \) ist die kürzeste, gefolgt von der Substitution \ (V "= RDS \).
5. Wenn die Substitutionsformel endlich war, wird der Algorithmus mit dem Ergebnis \ (V "\) abgeschlossen. Andernfalls gehe zu Schritt 1 (dem nächsten Schritt).

Jeder normale Algorithmus entspricht einer Turing-Maschine und umgekehrt - jede Turing-Maschine entspricht einem normalen Algorithmus.

Ein Analogon von Turings These für normale Algorithmen heißt üblicherweise das Prinzip der Normalisierung.

Beispiel

Dieser Algorithmus wandelt Binärzahlen in „Einsen“ um (wobei der Datensatz einer nicht-negativen ganzen Zahl N eine Folge von N Sticks ist). Zum Beispiel wird die Binärzahl 101 in 5 Sticks umgewandelt: |||||.

Alphabet: (0, 1, |) Regeln:

1. 1 → 0|
2. |0 → 0||
3. 0 -> (leerer String)

Originalzeile: 101 Ausführung:

1. 0|00|
2. 00||0|
3. 00|0|||
4. 000|||||
5. 00|||||
6. 0|||||
7. |||||

Rekursive Funktionen

Ein einer Turingmaschine äquivalentes System kann auf der Grundlage mathematischer Funktionen aufgebaut werden. Dazu müssen wir folgende Funktionsklassen einführen:

• primitive rekursive Funktionen
• allgemeine rekursive Funktionen
• teilweise rekursive Funktionen

Die letztere Klasse fällt mit der Klasse der Turing-berechenbaren Funktionen zusammen (dh Funktionen, die durch Konstruktion eines Algorithmus für eine Turing-Maschine berechnet werden können).

Die Definition eines Algorithmus durch rekursive Funktionen ist in der Tat das Herzstück des Lambda-Kalküls, und auf dieser Grundlage ist der Ansatz aufgebaut funktionale Programmierung.

Primitive rekursive Funktionen

Die Klasse der primitiven rekursiven Funktionen enthält Basisfunktionen und alle aus den Basisfunktionen abgeleiteten Funktionen mit Hilfe der Operatoren Auswechslungen und primitive Rekursion.

Zu den Grundfunktionen gehören:

• Die Nullfunktion \ (O () = 0 \) ist eine Funktion ohne Argumente, die immer \ (0 \) zurückgibt.
• Die Folgefunktion \ (S (x) = x + 1 \) ist eine Funktion, die jeder natürlichen Zahl \ (x \) die folgende Zahl \ (x + 1 \) zuordnet
• Funktionen \ (I_n ^ m (x_1, \ ldots, x_n) = x_m \), wobei \ (0

Um die restlichen Klassenfunktionen zu konstruieren, werden die Operatoren verwendet:

• Auswechslungen. Für die Funktion \ (f \) aus \ (m \) Variablen und \ (m \) Funktionen \ (g_1, \ ldots, g_m \) aus \ (n \) Variablen jeweils das Substitutionsergebnis \ (g_k \) in \ ( f \) ist eine Funktion \ (h (x_1, \ ldots, x_n) = f (g_1 (x_1, \ ldots, x_n), \ ldots, g_m (x_1, \ ldots, x_n)) \) aus \ (n \) Variablen.
• Primitive Rekursion. Sei \ (f (x_1, \ ldots, x_n) \) eine Funktion von \ (n \) Variablen und \ (g (x_1, \ ldots, x_ (n + 2)) \) eine Funktion von \ (n + 2 \) Variablen. Dann ist das Ergebnis der Anwendung des primitiven Rekursionsoperators auf die Funktionen \ (f \) und \ (g \) eine Funktion \ (h \) von \ (n + 1 \) Variable der Form: \ [h (x_1, \ ldots, x_n, 0) = f (x_1, \ ldots, x_n) \] \ [h (x_1, \ ldots, x_n, y + 1) = g (x_1, \ ldots, x_n, y, h (x_1, \ ldots, x_n, y)) \]

Teilweise rekursive Funktionen

Die Klasse der teilrekursiven Funktionen umfasst primitive rekursive Funktionen und zusätzlich alle Funktionen, die aus primitiven rekursiven Funktionen mit dem Argumentminimierungsoperator erhalten werden:

Operator zur Argumentminimierung

Sei \ (f \) eine Funktion von \ (n \) Variablen \ (x_i \ in \ mathbb (N) \). Das Ergebnis der Anwendung des Argumentminimierungsoperators auf die Funktion \ (f \) ist dann die Funktion \ (h \) des Arguments \ (n-1 \), definiert als:

\ [h (x_1, \ ldots, x_ (n-1)) = \ min y, \] wo \ Das heißt, \ (h \) gibt den Minimalwert des letzten Arguments an die Funktion \ (f \) zurück, bei dem \ (f \) null ist.

Während primitiv rekursive Funktionen immer berechenbar sind, können teilweise rekursive Funktionen für einige Argumentwerte nicht definiert werden.

Genauer gesagt sollten teilweise rekursive Funktionen als "teilweise definierte rekursive Funktionen" bezeichnet werden, da sie nur auf einem Bruchteil der möglichen Argumentwerte definiert sind.

Allgemeine rekursive Funktionen

Allgemeine rekursive Funktionen sind eine Unterklasse aller teilrekursiven Funktionen, die für jeden Argumentwert definiert sind. Das Problem der Bestimmung, ob eine gegebene partiell rekursive Funktion allgemein rekursiv ist, ist algorithmisch unentscheidbar... Damit sind wir beim Thema Berechenbarkeitstheorie und dem Halteproblem.

Berechenbarkeitstheorie und das Halteproblem

Unsere Vorstellungskraft lässt im Allgemeinen die Existenz unlösbarer Probleme zu, dh Probleme, für die es unmöglich ist, einen Algorithmus zu erstellen.

Die Berechenbarkeitstheorie beschäftigt sich mit solchen Problemen.

Beispiele für algorithmisch unlösbare Probleme sind Stopp Problem und Schlupferkennungsproblem... Betrachten wir sie genauer.

Stoppproblem Basierend auf der Beschreibung von Algorithmus A und den Eingabedaten \ (x \) ist es notwendig herauszufinden, ob der Algorithmus \ (A \) auf den Eingabedaten \ (x \) stoppt.

Das Halteproblem ist algorithmisch unlösbar. Lass es uns beweisen.

\ (\Delta\)

Es gebe einen universellen Algorithmus, der das Halteproblem löst. Betrachten Sie dann eine Klasse von Algorithmen, die Texte verarbeitet, die Algorithmen beschreiben.

Aufgrund der Existenz eines universellen Algorithmus zur Lösung des Halteproblems gibt es einen Algorithmus, der bestimmt, ob ein Algorithmus aus der genannten Klasse bei seinem eigenen Text stoppt oder nicht. Bezeichnen wir einen solchen Algorithmus mit \(B\).

Konstruieren wir den Algorithmus \ (C \), dessen Eingabedaten der Text des Algorithmus \ (A \) ist, der seinen eigenen Text verarbeitet:

1. Führe den Algorithmus \ (B \) über \ (A \) aus.
2. Wenn der Algorithmus \ (B \) festgestellt hat, dass \ (A \) bei seinem Text stoppt, fahren Sie mit Schritt 1 fort. Andernfalls fahren Sie mit Schritt 3 fort.
3. Ende des Algorithmus \ (C \).

Nachdem wir versucht haben, den \ (C \)-Algorithmus auf den \ (C \)-Algorithmus anzuwenden, kommen wir zu einem offensichtlichen Widerspruch: Wenn \ (C \) bei seinem eigenen Text aufhört, dann kann er nicht aufhören und umgekehrt. Daher gibt es keinen \(B\)-Algorithmus. \ (\ nicht \ Delta \)

Eine allgemeinere Formulierung des Halteproblems ist das Problem der Schraffierbarkeit.

Problem der Schlüpfbarkeitserkennung

Lassen Sie ein bestimmtes Alphabet, Wörter (Formeln) dieses Alphabets und ein System von formalen Transformationen über die Wörter dieses Alphabets definieren (d. h. ein logischer Kalkül wird aufgebaut)

Gibt es im Rahmen dieses logischen Kalküls für zwei beliebige Wörter \ (R \) und \ (S \) eine deduktive Kette, die von \ (R \) nach \ (S \) führt?

1936 bewies Alonzo Church das Theorem von Church.

Theorem von Church Das Problem der Anerkennung der Deduzierbarkeit ist algorithmisch unlösbar.

Church verwendete den Formalismus des Lambda-Kalküls, um dies zu beweisen. 1937 bewies Turing unabhängig von ihm den gleichen Satz unter Verwendung des Turing-Maschinen-Formalismus.

Da alle Definitionen von Algorithmen zueinander äquivalent sind, gibt es ein System von Begriffen, das keiner bestimmten Definition eines Algorithmus zugeordnet ist und mit dem Begriff operiert berechenbare Funktion.

Berechenbare Funktion Eine Funktion, die von einem Algorithmus berechnet werden kann.

Es gibt Probleme, bei denen die Beziehung zwischen Eingabe- und Ausgabedaten nicht mit einem Algorithmus beschrieben werden kann. Solche Funktionen sind unberechenbar.

Ein Beispiel für eine unberechenbare Funktion

Nehmen Sie die Funktion \ (h (n) \) definiert für \ (\ für alle n \ in \ mathbb (N) \) wie folgt:

\ [h (n) = \ begin (cases) 1, & \ text (wenn in) \ pi \ text (es gibt eine Folge von genau) n \ text (9-k) \\ 0, & \ text (sonst ) \ Ende (Fälle) \]

Wir können den Wert \ (1 \) für diese Funktion erhalten, aber um den Wert \ (0 \) zu erhalten, müssen wir die unendliche Dezimalentwicklung von \ (\ pi \) überprüfen, was in endlicher Zeit offensichtlich unmöglich ist . Diese Funktion ist somit nicht berechenbar.

Ausdruck nach den 1920er Jahren Rechenmaschine bezieht sich auf jede Maschine, die Arbeit verrichtet hat menschlicher Computer, insbesondere für diejenigen, die nach den effektiven Methoden der Church-Turing-These entwickelt wurden. Diese These lautet: „Jeder Algorithmus kann in Form einer geeigneten Turingmaschine oder einer partiell rekursiven Definition spezifiziert werden, und die Klasse der berechenbaren Funktionen fällt mit der Klasse der partiell rekursiven Funktionen und mit der Klasse der auf Turingmaschinen berechenbaren Funktionen zusammen ." Mit anderen Worten, die Church-Turing-These ist als Hypothese über die Natur mechanischer Rechengeräte wie elektronischer Computer definiert. Alle möglichen Berechnungen können auf einem Computer durchgeführt werden, sofern genügend Zeit und Speicherplatz vorhanden sind.

Die Mechanismen, die beim Rechnen mit Unendlichkeiten arbeiten, wurden als analoger Typ bekannt. Werte in solchen Mechanismen wurden durch kontinuierliche Zahlenwerte dargestellt, zum Beispiel der Drehwinkel einer Welle oder die elektrische Potenzialdifferenz.

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 verwendeten vor der Erfindung des RAM-Bausteins eine Vielzahl von Prozessoren oder Relais.

Name Rechenmaschine seit den 1940er Jahren wurde es durch das Konzept verdrängt Computer... Diese Computer waren in der Lage, die Berechnungen durchzuführen, die Angestellte früher machten. Ab wann Werte nicht mehr von physikalischen Eigenschaften abhängig waren (wie bei analogen Maschinen), konnte ein logischer Computer auf Basis digitaler Hardware alles, was man beschreiben konnte. rein mechanisches System .

Turing-Maschinen wurden entwickelt, um formal mathematisch zu definieren, was bei Einschränkungen der Rechenleistung berechnet werden kann. 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 ist, solange es eine Turing-Maschine gibt, die die Näherung einer Zahl berechnen kann. Darüber hinaus kann die Turing-Maschine logische Operatoren wie AND, OR, XOR, NOT und If-Then-Else interpretieren, um zu bestimmen, ob