Was ist eine Turing-Maschine?

StackOverflow https://stackoverflow.com/questions/236000

Frage

Was ist eine Turing-Maschine und warum machen die Leute halten Sie es erwähnen?Meine IBM-PC ist alles, was ich zu tun meine Berechnung!Warum jemand sich mit diesen Maschinen?

War es hilfreich?

Lösung

Der Grund, dass Turing-Maschinen sind eine große Sache hat sich mit dem Studium der klassischen Informatik oder Theory of Computation Art Dinge zu tun. Es ist im Grunde über die allgemeinen Eigenschaften eines Computers zu analysieren, wie es die theoretische Fähigkeiten und Grenzen ein Computer hat, als auch, was wir meinen, wenn wir über „Berechnen“ etwas reden.

Ein Beispiel für etwas, das man untersuchen könnte mit Turingmaschinen ist das Halteproblem . Während dieses Problem so etwas wie eine akademische Übung ist, hat es leicht greifbar realen Auswirkungen. Warum schreiben Sie nicht einen Debugger, die einfach sagen, werden Sie, ob Ihr Programm keine Endlosschleifen enthält? Das Halteproblem fest, dass dieses Problem für den allgemeinen Fall zu lösen ist nicht möglich.

Die Studie von Turingmaschinen eignet sich auch Sprache Grammatiken und Klassen davon zu studieren, die in die Entwicklung Programmiersprache führt. Der Begriff „reguläre Ausdrücke“ kommt zustande, weil sie eine regelmäßige Grammatik , und die Untersuchung dieser Grammatiken (Teil der Theorie der Berechnung) wird Ihnen sagen, mehr über genau das, was Arten von Problemen können reguläre Ausdrücke lösen und was sie nicht können. Zum Beispiel wird eine traditionelle Syntax für reguläre Ausdrücke nicht möglich sein, das folgende Problem zu lösen: Parsen einer bestimmte Anzahl N von ‚a‘ Zeichen in der Eingabe, und dann die gleiche Anzahl N von char ‚b‘ analysiert

.

Wenn Sie in einem guten Text über diese Art der Sache interessiert sind, überprüfen Einführung in der Theorie der Berechnung von Michael Sipser. Es ist gut.

Andere Tipps

Die Turing-Maschine ist eine theoretische Rechenmaschine von Alan Turing erfand als idealisiertes Modell für mathematische Berechnung zu dienen, im Grunde seiner einfache Form von Computern, sein von einer Band zusammengesetzt (ein Band aus Papier ), einen Kopf , welche die Symbole lesen kann, ein neues Symbol an Ort und Stelle schreiben, und dann nach links oder rechts bewegen.

Die Turing Maschine gesagt wird in einem bestimmten Zustand sein, und dann wird ein Programm ist eine Liste von Transitionen , einen aktuellen Zustand und ein Symbol unter dem Kopf, was auf dem Band geschrieben werden soll, was der nächste Zustand sein würde, und wo soll der Kopf bewegen.

Hier ist eine Grund Turing-Maschine , implementiert in JavaScript ...

Und eine Skizze:

Turingmaschine

  

Meine IBM PC ist alles, was ich brauche, um meine Berechnung zu tun!

Etwas, das andere nicht darauf hingewiesen: Der IBM PC ist eine Turing-Maschine. Genauer gesagt, ist es in dem Sinne, es entspricht, dass alles, was Ihr PC tun kann, kann eine Turing-Maschine eine Turing-Maschine tun, und alles tun, Ihren PC kann.

Insbesondere wird eine Turing-Maschine ist ein Modell der Berechnung , die vollständig den Begriff der Berechenbarkeit erfaßt, bei einfacher über die Vernunft, ohne all die spezifischen Details Ihres PCs Architektur.

Die (allgemein akzeptierte) „Church-Turing-These“ behauptet, dass jedes Gerät oder Modell der Berechnung ist nicht mächtiger als eine Turing-Maschine. So sind viele theoretischen Probleme (zB Klassen wie P und NP, der Begriff des „Polynomialzeit-Algorithmus“, und so weiter) formal im Sinne einer Turing-Maschine angegeben, obwohl natürlich können sie auf andere Modelle angepasst werden, wie Gut. (Zum Beispiel, manchmal kann es zweckmäßig sein, die Berechnung zu denken, in Bezug auf dem Lambda-Kalkül, oder kombinatorischer Logik, oder was auch immer ... sie sind alle gleichwertig an der Macht zu ihnen und zu Ihrem IBM PC als auch.)

Also los geht: Leute über Turing-Maschinen sprechen, weil es sich um eine präzise und voll spezifizierte Art und Weise zu sagen, was ein „Computer“ ist, ohne jedes Detail der CPU-Architektur zu beschreiben ist, seine Einschränkungen, und so weiter <. / p>

Es gibt tatsächlich Beispiele von Turing-Maschinen in der Natur.Insbesondere die Ribosom, übersetzt die RNA in Proteine, implementiert eine Turing-Maschine.

Zunächst einige Hintergrundinformationen:

  1. RNA besteht aus einer Zeichenfolge Nukleotide ("Grundlagen") definieren die Buchstaben des genetischen Alphabets.
  2. Es sind 4 Basen in der RNA alphabet - A, C, G, U.
  3. Basen sind direktional:von Konvention den enden sind sogenannte fünf-prime-und drei -prime - (5', 3')
  4. Eine Basis in einem RNA-string anziehen können, eine Basis auf einem anderen RNA-string in "anti-parallele komplementäre Paare", wo Eine klebt an U-und C-sticks bis G.
  5. Die Basen werden in Gruppen zusammengefasst von 3 in form von "codon" (Wörter).
  6. Es gibt 64 mögliche Kombinationen für den codons (4^3).
  7. jedes codon kann die übereinstimmung mit einer "anti-codon".zum Beispiel AUG <-> UAC
  8. es gibt spezielle carrier-Moleküle ("tRNA"), die insbesondere anticodons und befestigt werden bestimmte Aminosäuren (Proteine).

Der Betrieb des Ribosoms ist einfach:

  1. Transkription initiiert, um ein "start codon" definiert, das "Lesen Rahmen"
  2. Transkription immer geht in die 5'->3' Richtung
  3. das codon unter der reading frame ist abgestimmt mit einem spezifischen tRNA mit einer bestimmten Aminosäure
  4. das start-codon immer codiert Aminosäure Methionin.
  5. die neue Aminosäure wird an die wachsende protein
  6. die Rahmen dann weiter 3 Basen zum nächsten codon, und das protein wird kontinuierlich erweitert
  7. nach der Begegnung mit einem "stop" - codon, übersetzung beendet wird, kein Aminosäure befestigt ist, und das Ribosom distanziert sich von der mRNA.

Wie Sie sehen können, ist dies eine sehr einfache Turing-Maschine, führt die komplexe operation - die Natur selbst!

Eine Turing-Maschine ist eine theoretische Maschine, die verwendet werden kann, über die Grenzen des Computers an der Vernunft. Einfach gesagt, es ist ein imaginärer Computer mit unendlichen Speichern.

Wir kümmern uns um Turing-Maschinen, weil sie uns helfen, entdecken, was unmöglich ist, mit echten Computern (wie Ihr IBM PC) zu erreichen. Wenn es unmöglich ist, für eine Turing Maschine eine bestimmte Berechnung auszuführen (wie die Entscheidung des Halting Problem ), dann liegt es nahe, dass es für den IBM-PC die gleiche Berechnung auszuführen unmöglich ist.

Warum sollten Menschen, die Design-Flugzeuge über die Wright-Brüder kümmern, oder die Wissenschaft hinter dem „Lift“, die Starrflügler kann fliegen?

Alan Turing gilt als Vater der modernen Computing gelobt. Die Turing-Maschine ist der Vorläufer aller modernen Computer.

Die Theorie der Berechenbarkeit war meine härteste Klasse in der Schule, aber ich bin froh, dass ich es brauchte. Es hat mich über die Dinge denken, ich würde nie, oder denken über die Dinge in einer Weise, die ich nie haben würde, und das sind gute Dinge haben.

Eine Turing-Maschine ist eine abstrakte Maschine, die Berechnung.

Aus Wikipedia:

  

Turing-Maschinen sind einfach abstraktes Symbol-Manipulatoren, die trotz ihrer Einfachheit, kann die Logik eines Computeralgorithmus zu simulieren angepasst werden. Sie wurden im Jahr 1936 von Alan Turing beschrieben. Turing-Maschinen sind nicht als praktische Computing-Technologie gedacht, sondern ein Gedankenexperiment über die Grenzen der mechanischen Berechnung. So wurden sie nicht tatsächlich gebaut. Das Studium ihrer abstrakten Eigenschaften liefert viele Einblicke in die Informatik und Komplexitätstheorie.

     

Eine Turing-Maschine, die andere Turing-Maschine zu simulieren, ist in der Lage ist eine universelle Turing-Maschine (UTM oder einfach eine universelle Maschine) genannt. Eine mathematisch orientierte Definition mit einer ähnlichen „universal“ Natur wurde von Alonzo Church, deren Arbeit auf Lambda-Kalkül verflochten mit Turings in einer formalen Theorie der Berechnung als die Church-Turing-These bekannt ist, eingeführt. Die These besagt, dass Turing-Maschinen in der Tat des informellen Begriff wirksamer Methode in der Logik und Mathematik erfassen, und bieten eine genaue Definition eines Algorithmus oder ‚mechanischer Verfahren‘.

Turing Maschine ist eine abstrakte Maschine, die auf einer Sequenz von Daten arbeiten kann, und kann seinen eigenen Zustand sowie die Daten ändern, während Betrieb, nach einiger Logik.

Dies ist ein Konzept, das die Basis von Algorithmen, gespeicherte Programme und Berechnung in der Regel bildet. Es bietet gute Einblicke und Abstraktionen, wenn Sie mit Algorithmen, Staaten, Daten handeln usw.

Stoff zum Nachdenken, für die meisten.

Neben dem Wikipedia-Eintrag, könnten Sie das Buch abholen wollen Die Kommentierte Turing von Charles Petzold. Untertitel „Eine Führung durch Alan Turings Historische Buch über Berechenbarkeit und der Turing-Maschine“, enthält es die komplette Papier, gebrochen in Stücke mit viel Diskurs über das Thema, eine historische Perspektive mit.

Turing-Maschine ist auf einem Algorithmus äquivalent. Es stoppt, wenn es eine Zeichenfolge annimmt, ablehnt oder tritt in eine Endlosschleife, wenn die Zeichenfolge nicht akzeptiert.

Band dient als Speicher, Übergangsregeln fungieren als 'if then else' Bedingungen

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top