„Die wichtigste Maschine, die nie gebaut wurde', Alan Turing und die Turing-Maschine

Berechnen ist ein vertrautes Konzept, das die meisten von uns intuitiv verstehen. Nehmen wir als Beispiel die Funktion f (x) = x + 3. Wenn x 3 ist, ist f (3) = 3 + 3. Die Antwort ist 6, ganz einfach. Offensichtlich ist diese Funktion berechenbar. Aber einige Funktionen sind nicht so einfach und die Bestimmung, ob sie berechnet werden können, ist nicht trivial, was bedeutet, dass sie möglicherweise nie zu einer endgültigen Antwort führen.

1928 schlugen die deutschen Mathematiker David Hilbert und Wilhelm Ackermann ein Problem namens Entscheidungsproblem („Entscheidungsproblem“) vor. Im Laufe der Zeit führte die von ihnen gestellte Frage zu einer formalen Definition der Berechenbarkeit, einer Definition, die es Mathematikern ermöglichen würde, eine Vielzahl neuer Fragen zu beantworten und den Grundstein für die theoretische Informatik zu legen.

Ein 23-jähriger Doktorand namens Alan Turing schlug diese Definition vor. Er schrieb 1936 eine bahnbrechende Arbeit, die nicht nur das Konzept der Informatik formalisierte, sondern auch bewies, dass mathematische Grundfragen die Wissensbasis für die Erfindung bildeten elektronischer Computer. Turings große Vision bestand darin, konkrete Antworten auf Rechenprobleme in Form einer abstrakten Maschine zu liefern, die später von seinem Doktorvater Alonzo Church Turing-Maschine genannt wurde.

Eine Turing-Maschine ist abstrakt, weil sie physisch nicht als greifbares Gerät existiert (und auch nicht existieren kann). Es handelt sich vielmehr um ein konzeptionelles Berechnungsmodell: Wenn diese Maschine eine Funktion berechnen kann, dann ist die Funktion berechenbar.

Als Alan Turing 1936 die Turing-Maschine erfand, schuf er auch die moderne Informatik.

Alan Turing und seine Turing-Maschine

Das funktioniert so: Die Turing-Maschine kann Symbole auf einem unendlich langen Band gemäß der Regeltabelle lesen und ändern. Das Band besteht aus „Zellen“, und jede Zelle kann nur ein Symbol speichern. Turingmaschinen verwenden Bandköpfe, um den Inhalt von Zellen zu lesen und neu zu schreiben. Jede Regel in der Regeltabelle bestimmt, was die Turing-Maschine basierend auf ihrem aktuellen Zustand und dem Symbol, das sie liest, tun soll. Eine Turing-Maschine kann abhängig davon, wo sie angehalten hat, in einen Endzustand (einen „Akzeptanzzustand“ oder einen „Ablehnungszustand“) eintreten und entscheiden, ob sie die Eingabe akzeptiert oder ablehnt. Oder eine Turing-Maschine bleibt in einer Endlosschleife stecken und hört nie auf, das Band zu lesen.

Der beste Weg, eine Turing-Maschine zu verstehen, besteht darin, über ein einfaches Beispiel wie dieses nachzudenken. Stellen wir uns vor, eine Turing-Maschine soll uns sagen, ob eine bestimmte Eingabe die Zahl Null ist. Wir geben die Nummer 0001 mit einem Leerzeichen (#) ein, was bedeutet, dass „#0001#“ der relevante Teil unseres Bandes ist.

Die Turing-Maschine startet in einem Anfangszustand, nennen wir ihn q0, liest die Zelle ganz links auf dem Band und findet einen leeren Bereich. Wenn im Zustand q0 das Vorzeichen # ist, lassen Sie es in der Regel unverändert, verschieben Sie dann eine Zelle nach rechts und ändern Sie den Maschinenzustand in q1. Nach diesem Schritt befindet sich die Maschine im Zustand q1 und ihr Kopf liest das zweite Symbol 0.

Jetzt suchen wir nach Regeln, die für diese Bedingungen gelten. Wir finden eine Regel, die besagt: „Behalten Sie Zustand q1 bei und bewegen Sie den Kopf eine Zelle nach rechts.“ Damit bleiben wir in derselben Position (im Zustand q1 ist der Wert immer noch 0), also bewegen wir uns weiter nach rechts, bis der Kopf erreicht ist schließlich wird eine andere Nummer 1 gelesen.

Als wir die Regeltabelle erneut konsultierten, fanden wir eine neue Regel: „Wenn 1 angetroffen wird, Übergang zu q2, dem Ablehnungszustand.“ Die Turing-Maschine stoppte den Betrieb und beantwortete die ursprüngliche Frage „Ist 0001 Null?“ ?" Antworten Sie mit „Nein“.

Wenn dagegen die Eingabe „#0000#“ lautet, trifft die Turing-Maschine nach all diesen Nullen auf #. Wenn wir die Regeltabelle konsultieren, finden wir eine Regel, die besagt, dass die Maschine in den Zustand q3 übergeht, einen „akzeptierenden“ Zustand. Die Maschine beantwortet nun die Frage „Ist ‚0000‘ Null?“ mit „Ja“.

Alan Turing half bei der Definition von Berechnungen, Algorithmen und Turing-Maschinen.

Beantwortung von Urteilsfragen mit abstrakten Maschinen

Turing nutzte seine abstrakte Maschine, um ein Rechenmodell zur Beantwortung des Entscheidungsproblems zu erstellen, das formal fragt: Gibt es bei einer gegebenen Reihe mathematischer Axiome einen mechanischen Prozess ( Das heißt, eine Reihe von Anweisungen (heute würden wir es einen Algorithmus nennen), die immer feststellen können, ob eine bestimmte Aussage wahr ist?

Angenommen, wir möchten einen Algorithmus finden, der uns sagt, ob die Position der Figuren in einem bestimmten Schachspiel machbar ist. Dabei sind die Axiome die Regeln, die vernünftige Schachzüge regeln. Können wir dorthin gelangen, indem wir einer endlichen Abfolge von Schritt-für-Schritt-Prozessen folgen? Obwohl die Analyse einiger Schachpositionen länger als unser Leben dauern kann, kann ein Algorithmus alle möglichen Positionen generieren und sie einzeln mit der Eingabe vergleichen. Solche Algorithmen gibt es im Schachspiel. Deshalb sagen wir, dass Schach „entscheidbar“ ist.

Allerdings verwendeten die amerikanischen Mathematiker Church und Turing 1936 unterschiedliche Methoden, um zu beweisen, dass „es keine allgemeine Methode gibt, die jedes Beispiel des Entscheidungsproblems lösen kann“, zum Beispiel einige Spiele wie John Conways Game of Das Leben ist unentscheidbar: Kein Algorithmus kann bestimmen, ob aus dem ursprünglichen Muster ein bestimmtes Muster hervorgeht.

Turing hat gezeigt, dass eine Funktion berechenbar ist, wenn es einen Algorithmus gibt, der die erforderliche Aufgabe ausführen kann. Gleichzeitig zeigte er auch, dass der Algorithmus ein Prozess ist, der durch eine Turing-Maschine definiert werden kann. Daher ist eine berechenbare Funktion eine Funktion, die von einer Turing-Maschine berechnet werden kann. Dies scheint ein umständlicher Weg zu sein, Berechenbarkeit zu definieren, aber es ist der beste, den wir haben.

Michael Sipser, ein theoretischer Informatiker am MIT, sagte: „Es ist nicht so, dass man es auf andere Weise definieren kann. Ich denke, die Leute sind sich im Allgemeinen einig, dass die Church-Turing-These vorschlägt, dass Algorithmen das informelle Konzept von „was“ sind Jedes vernünftige Berechnungsmodell kann dies tun. Andere Mathematiker haben verschiedene Berechnungsmodelle vorgeschlagen, die zwar oberflächlich betrachtet unterschiedlich sind, aber tatsächlich dasselbe tun: Sie können das tun, was eine Turing-Maschine tun kann, und umgekehrt.

Nur wenige Jahre nachdem der Philosoph, Logiker und Mathematiker Kurt Gödel zeigte, dass Mathematik unvollständig ist, zeigten Church und Turing mit diesem Arbeitsblatt auch, dass bestimmte Probleme in der Mathematik unentscheidbar sind. Egal wie komplex der Algorithmus ist, er kann uns nicht sagen, ob die Antwort Ja oder Nein lautet. Beide Ereignisse waren verheerende Schläge für Hilbert, der gehofft hatte, dass die Mathematik einfache, idealisierte Antworten liefern würde. Aber das ist nicht schlecht: Wenn es eine allgemeine Lösung des Entscheidungsproblems gäbe, würde dies bedeuten, dass alle Probleme in der Mathematik auf einfache mechanische Berechnungen reduziert werden könnten.

Universelle und probabilistische Turingmaschinen

Turingmaschinen beantworteten nicht nur diese grundlegenden Fragen, sondern beeinflussten auch direkt die Entwicklung moderner Computer durch eine Variante namens Universal Turing Machine. Es handelt sich um eine spezielle Turing-Maschine, die jede Eingabe von jeder anderen Turing-Maschine simulieren kann. Es könnte die Beschreibungen (sowie Regeln und Eingabebänder) anderer Turing-Maschinen lesen und deren Verhalten auf seinen eigenen Eingabebändern simulieren und dabei die gleiche Ausgabe wie die simulierte Maschine erzeugen, so wie heutige Computer jedes Programm lesen und ausführen können.

Im Jahr 1945 schlug der ungarisch-amerikanische Mathematiker, Informatiker und Physiker John von Neumann eine Computerarchitektur vor – die von Neumann-Architektur, die das Konzept einer universellen Turing-Maschine in reale Maschinen ermöglichte.

Wenn der theoretische Informatiker Sanjeev Arora von der Princeton University dieses Konzept lehrt, betont er das umfassendere philosophische Bild. Er sagte: „Es gibt zwei Konzepte von Universal: Das eine ist, dass es jede andere Turing-Maschine ausführen kann, aber das andere, größere Konzept ist, dass es jede beliebige Berechnung im Universum ausführen kann, die man sich in der klassischen Physik ausdenkt.“ Jeder physikalische Prozess kann mithilfe von Algorithmen modelliert oder simuliert werden, und Algorithmen können durch Turing-Maschinen simuliert werden.

Eine weitere bemerkenswerte und zunehmend nützliche Variante ist die probabilistische Turing-Maschine. Im Gegensatz zu herkömmlichen Turing-Maschinen, die auf jede Eingabe genau definierte Antworten haben, können probabilistische Turing-Maschinen mehrere Antworten auf der Grundlage von Wahrscheinlichkeiten geben. Dies bedeutet, dass es zu unterschiedlichen Zeitpunkten für dieselbe Eingabe unterschiedliche Ergebnisse liefern kann. Es ist auch überraschend, dass diese probabilistische Strategie für einige Probleme effektiver ist als ein rein deterministischer Ansatz. Das Konzept probabilistischer Turingmaschinen hat sich in Bereichen wie Optimierung und maschinellem Lernen als sehr nützlich erwiesen.

Diese abstrakten Maschinen sind vielleicht der beste Beweis dafür, dass das Stellen grundlegender Fragen zu den nützlichsten Dingen gehören kann, die ein Wissenschaftler tun kann.

Das obige ist der detaillierte Inhalt von„Die wichtigste Maschine, die nie gebaut wurde', Alan Turing und die Turing-Maschine. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!