Phenquestions
Die Turingmaschine ist das zentrale theoretische Konstrukt der Informatik computer. Die Turingmaschine ist ein abstraktes mathematisches Rechenmodell. Der Einsatz von Turing-Maschinen hilft zu erklären, was Rechnen ist, indem die sogenannten „berechenbaren Funktionen“ abgegrenzt werden.”
Alan Turings frühe Forschungen zur Logik konzentrierten sich auf ein berühmtes ungelöstes Problem, das als Entscheidungsproblem bekannt ist. Das Entscheidungsproblem (grob übersetzt aus dem Deutschen als Entscheidungsproblem) wurde 1928 vom Philosophen und Mathematiker David Hilbert vorgeschlagen. Das Problem fragte, ob es einen Algorithmus gibt, der jede Aussage in einer formalen Sprache entscheiden würde.
Eine formale Sprache ist ein System von Axiomen und Inferenzregeln, wie sie in der Arithmetik oder der Logik erster Ordnung vorkommen. Die Axiome können beliebige Symbole sein, und die Inferenzregeln können eine beliebige Liste von Regeln zum Manipulieren dieser Symbole sein. „Jede Aussage entscheiden“ bedeutete entweder auszugeben, ob die Aussage wahr/falsch war oder auszugeben, ob die Aussage ableitbar/nicht ableitbar war. Der Vollständigkeitssatz von Kurt Gödel hat bewiesen, dass ein auf Gültigkeit entscheidender Algorithmus äquivalent zu einem effektiven Verfahren ist, der auf Ableitbarkeit entscheidet. Alan Turings Aufsatz „On Computable Numbers, with an Application to the Entscheidungsproblem“ von 1936 bewies das negative Ergebnis, dass es unmöglich war, jede Aussage in einem formalen System algorithmisch zu entscheiden.
Alan Turing
Um ein negatives Ergebnis für das Entscheidungsproblem zu beweisen, musste Turing den Begriff eines Algorithmus formalisieren. Turings Formalisierung eines Algorithmus war ein mathematisches Rechenmodell, das später als Turing-Maschine bekannt wurde. Eine Turingmaschine hat eine endliche Menge von Zuständen, in denen sich die Maschine befinden kann. Die Turing-Maschine hat ein unendlich langes Band, das in Quadrate unterteilt ist. Auf jedem Quadrat des Bandes befindet sich ein Symbol, das aus einer endlichen Menge von Symbolen gezogen wurde. Zu jedem Zeitpunkt der Berechnung liest die Turing-Maschine das Symbol auf einem Quadrat des Bandes. Die Turing-Maschine kann dieses Symbol durch ein anderes Symbol ersetzen und sich entweder auf das rechte oder das linke Feld bewegen. Die Aktion der Turing-Maschine wird automatisch durch den Zustand der Maschine bestimmt. Nachdem das Ersetzungssymbol und die Bewegung auf ein anderes Quadrat stattgefunden haben, kann die Turing-Maschine in einen anderen Zustand übergehen. Jeder unterschiedliche Zustand hat andere Regeln, wie Symbole ersetzt werden und in welche Richtung sie sich bewegen sollen.
Eine seltene physische Implementierung des Turing-Maschinen-Designs (ohne ein unendliches Band)
Die kanonische Formulierung der Turingmaschine besteht normalerweise aus einem binären Alphabet aus ausschließlich 0en und 1s. Diese Formulierung entspricht der Intuition moderner Computerprogrammierer, da alle modernen Computer Binärdateien verwenden. Tatsächlich sind Turing-Maschinen neutral in Bezug auf die Größe des Symbolalphabets. Eine Turing-Maschine kann auch jedes beliebige Symbol verwenden, egal ob es sich um Zahlen oder eine andere Art von Alphabet wie Bildsymbole oder das lateinische Alphabet handelt. Jede Formulierung jedes möglichen endlichen Alphabets ist nachweislich auf eine binäre Turingmaschine reduzierbar.
Turing-Maschinen gehen davon aus, dass unendlich viel Speicher zur Verfügung steht. Keine wirklich physikalisch instanziierte Maschine kann diese Anforderung erfüllen, eine Turing-Maschine zu sein. Eine Turingmaschine geht auch davon aus, dass eine potenziell unendliche Zeit für die Berechnung der Funktion aufgewendet werden kann. Diese Annahmen wurden getroffen, um die umfangreichste Klasse möglicher Funktionen für Turings Definition berechenbarer Funktionen zu generieren. Berechenbare Turing-Funktionen sind alle Funktionen, die von einer Turing-Maschine berechnet werden können. Viele dieser berechenbaren Funktionen sind möglicherweise von keinem physisch instanziierten Computer berechenbar, da sie zu viel Zeit oder Speicher benötigen.
Die Church-Turing-These behauptet die Äquivalenz von berechenbaren Funktionen und Funktionen, die von einer Turing-Maschine berechnet werden können. Dies bedeutet, dass alle Funktionen, die von Turing-Maschinen nicht berechenbar sind, mit keiner anderen Methode berechnet werden können. David Hilbert hatte eine positive Antwort auf das Entscheidungsproblem erwartet, was bedeuten würde, dass alle Probleme berechenbar sind. Turings Ergebnis hat zur Entdeckung vieler unberechenbarer Probleme geführt.
Das bekannteste unberechenbare Problem ist das Halteproblem. Das Halting Problem ist das Problem, einen Algorithmus zu erstellen, der im allgemeinen Fall entscheiden kann, ob ein Computerprogramm mit seiner Eingabe anhält oder ewig weiterläuft. Es gibt zwar spezielle Fälle, in denen das Halting-Problem gelöst werden kann, es kann jedoch nicht für jedes Computerprogramm mit jeder Eingabe gelöst werden. Dieses Ergebnis hatte wichtige Konsequenzen für die Computerprogrammierung, da Computerprogrammierer sich der Möglichkeit von Endlosschleifen und der Unmöglichkeit, alle Endlosschleifen vor der Ausführung ihrer Programme zu erkennen, bewusst sein müssen.
Eine weitere Implikation der Turingmaschine ist die Möglichkeit universeller Turingmaschinen. Implizit in Turings Design ist das Konzept, das Programm, das die Daten modifiziert, neben den Daten, die es modifiziert, zu speichern storing. Dies deutete auf die Möglichkeit universeller und umprogrammierbarer Computer hin. Moderne Computer sind typischerweise universelle Turing-Maschinen in dem Sinne, dass sie so programmiert werden können, dass sie jeden Algorithmus ausführen. Dadurch wurde die Notwendigkeit unterschiedlicher Hardware für jedes potenzielle Computerprogramm beseitigt und die Unterscheidung zwischen Hardware und Software eingeführt.
Das Modell der Turing-Maschine führte direkt zur Erfindung von Computern, aber es ist nicht dieselbe Blaupause, die für die Entwicklung moderner Computer verwendet wird. Die von Neumann-Architektur, die als Blaupause für moderne Computer verwendet wird, verwendet das gespeicherte Programmkonzept, das im Turing-Maschinen-Modell implizit ist, unterscheidet sich jedoch in mehreren wichtigen Punkten vom Rest des Turing-Maschinen-Modells. Die größten Unterschiede bestehen darin, dass die von Neumann-Architektur keinen Lese-Schreib-Kopf verwendet, sondern mehrere Register, Direktzugriffsspeicher, Datenbusse, einen kleinen Satz grundlegender Maschinenbefehle und mehrere Bit-Verarbeitungsfunktionen enthält. Die von Neumann-Architektur lässt auch explizit spezialisierte Ein- und Ausgabegeräte wie Tastaturen und Monitore zu.
Das Turing-Maschinen-Modell war das erste mathematische Modell der Berechnung. Es führte direkt zur Erfindung von physischen Computern. Physische Computer verfügen über dieselben Fähigkeiten wie Turing-Maschinen, vorausgesetzt, dass der Speicher und die Zeitbeschränkungen für die tatsächliche Berechnung begrenzt sind. Die Turing-Formulierung spielt immer noch eine zentrale Rolle in der Untersuchung der Berechnungen. Informatiker sind immer noch aktiv an der Erforschung beteiligt, ob bestimmte Funktionen von Turing-Maschinen berechenbar sind.
