Welche genaue Beziehung besteht zwischen Programmiersprachen und Turing-Maschinen?

Ich weiß nicht viel über Yacc, Bison, Flex oder Lex und bitte korrigiere mich, wenn ich falsch liege, aber eine Programmiersprache ist auch eine Turing-Maschine und eine Turing-Maschine ist als Tupel definiert $(Q, \Gamma, b, \Sigma, \delta, q_0, F)$ wo $Q$, $\Gamma$, $b \in \Gamma$, $\Sigma \subseteq \Gamma \smallsetminus \{ b \}$ als Eingabe, $\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{ L, R, N \}$ als Übergangsfunktion wo $L$ = Anzahl der Schritte nach links, $R$ = Anzahl der Schritte rechts, $N$ = "Standby", $q_0 \in Q$ ist der Ausgangszustand und $F \subseteq Q$ ist die Menge der Endzustände.

Wie ähnlich ist die Implementierung einer Programmiersprache der Implementierung einer Turing-Maschine? Kann man sagen, dass bei der Implementierung einer Programmiersprache eine Turing-Maschine wie die oben genannte definiert wird? Wenn ja, warum können wir nicht einfach ein Modell verwenden, das der Definition einer Turing-Maschine ähnelt, wenn eine Programmiersprache definiert ist? Stattdessen scheint etwas anderes wie BNF der Standard zu sein.

Vielleicht verstehe ich die Frage falsch, aber es scheint, als ob der Vergleich zwischen Turing-Maschinen und Programmiersprachen etwas verwirrend ist.

Die Definition und Methode zur Definition einer Turingmaschine bilden eine Programmiersprache. Turingmaschinen repräsentieren Programme in dieser Sprache.

Sprachsyntax und -semantik (z. B. in BNF) können eine Programmiersprache darstellen, und Artefakte, die diese syntaktischen und semantischen Einschränkungen erfüllen, sind Programme in dieser Sprache.

Es ist also nicht wirklich präzise (IMHO; natürlich können wir darüber nachdenken, was TMs auf unterschiedliche Weise tun, und bei einigen dieser Betrachtungsweisen von TMs könnte man sich einzelne TMs als definierende Programmiersprachen vorstellen. In der Tat ein klassisch konstruiertes universelles Turing Die Maschine definiert eine sehr klare Programmiersprache, dh Darstellungen von Turing-Maschinen als Zeichenfolgen, um die Implementierung einer Programmiersprache mit der Implementierung einer Turing-Maschine zu vergleichen. Das Implementieren einer Programmiersprache beinhaltet das Definieren der Spielregeln, ähnlich wie Turing die Spielregeln definiert hat (oder wer auch immer es war, was auch immer), als er definierte, was es für etwas bedeutet, eine Turing-Maschine zu sein.

Das "Implementieren" einer Programmiersprache und das Definieren von Turing-Maschinen ist eine sehr schwierige Aufgabe. Das Schreiben von Programmen in einer Sprache und das Definieren bestimmter Turing-Maschinen ist ebenfalls eine schwierige Aufgabe. Aber es handelt sich um ganz andere Aktivitäten (außer in Ausnahmefällen, in denen Sie eine Turing-Maschine als Dolmetscher schreiben. In diesem Fall ist es möglicherweise sinnvoll, über das Entwerfen einer Programmiersprache über das Schreiben eines TM zu sprechen ... aber ich ' Ich bin mir nicht sicher, ob du danach gesucht hast.

Das Turing-Maschinenmodell ist ein theoretisches Modell dessen, worum es beim "Rechnen" geht. Als theoretisches Modell wurde es so entworfen, dass es einfach zu manipulieren und zu beweisen ist, insbesondere um zu untersuchen, was berechnet werden kann oder nicht. Es dient auch als einfaches Modell, um die für eine Berechnung erforderliche Zeit oder den Platzbedarf (Speicher) zu diskutieren (und zu beweisen). Der Schwerpunkt liegt auf Einfachheit (insbesondere bei der Verwendung nur grundlegender mathematischer Konzepte).

Im Gegensatz dazu soll eine Programmiersprache das Schreiben (und Lesen!) Durch Menschen erleichtern, häufig auch so, dass die Konzepte ihres Anwendungsbereichs direkt behandelt werden. Beispielsweise verarbeitet eine Sprache wie Perl Operationen an Zeichenfolgen, selbst komplexe Dinge wie die Suche nach Mustern, direkt. SQL ist darauf zugeschnitten, relationale Datenbanken zu bearbeiten, Abfragen mit bestimmten Einschränkungen nach Daten zu suchen und die Datenbank zu bearbeiten. Und so weiter.

Die Church-Turing-These besagt, dass alles, was in einem sinnvollen Sinne berechnet werden kann, von einer Turing-Maschine berechnet werden kann. Dies ist das Endergebnis eines jahrzehntelangen Rauschens bei der Entwicklung von Rechenmodellen, die sich alle als gleichwertig herausstellten. Theoretisch sind sie also äquivalent (soweit die Definition der Sprache und ihre Implementierung sowie die Maschine, auf der sie ausgeführt wird, korrekt sind). Aber wie das Sprichwort sagt, sind Theorie und Praxis in Theorie dasselbe; in der Praxis sind sie sehr unterschiedlich. Eine Turing-Maschine aufzuschreiben, um selbst einfache Aufgaben zu erledigen, ist eine Menge mühsamer Arbeit, und das könnte nur eine einfache Zeile in Ihrer bevorzugten Programmiersprache sein.

Es wird angenommen, dass alle (allgemeinen) Programmiersprachen der Turing-Maschine entsprechen. (Laut der Church-Turing-These werden sie nicht mehr berechnen, und normalerweise ist klar, wie man ein TM in Ihrer Lieblingssprache simuliert). Das bedeutet nicht, dass das Programmieren einer Turing-Maschine eine praktische Sache ist. Weit davon entfernt. Um wirklich programmieren zu können, werden bessere Sprachen entwickelt. Tatsächlich entwickeln sich diese Sprachen im Laufe der Zeit, wenn wir lernen, welche Funktionen die Verwendung von Programmiersprachen vereinfachen oder weniger fehleranfällig machen.

Trotzdem ist die Turing-Maschine in der Nähe. Es dient als Maßstab für die Definition von Komplexität und Berechenbarkeit.

(hinzugefügt.) Wie in den Kommentaren erwähnt, ist nicht jede Programmiersprache so konzipiert, dass sie Turing-fähig ist. Einige befassen sich mit bestimmten Aufgaben wie regulären Ausdrücken. Andererseits gibt es mächtige exotische Sprachen, die so disgniert sind, dass das Programmieren praktisch unmöglich wird. Zum Spass.

Eine Programmiersprache ist ein sorgfältig konstruiertes Äquivalent einer Universal Turing Machine.

nette Frage, aber du überdenkst das. sich in den Symbolen verlieren. Lassen Sie uns alles auf einfache, grundlegende Weise betrachten. Eine Programmiersprache ist in ASCII oder sagt nur 0/1 Bits für Zeichen. Stellen Sie sich nun vor, das TM hat 0/1 Bits, um es zu vereinfachen, oder sagen Sie ASCII als Eingabezeichen.

Die Schlüsselrealisierung und Analogie besteht darin, dass die TM-Statustabelle gleichzeitig den Eingabezeichensatz liest und die Programmiersprache / Programmcodierung enthält.

Dies kann realisiert werden, indem einfache TMs und ihre Statustabellen erstellt oder untersucht werden, um grundlegende Berechnungen zu berechnen, z. B. Summen oder was auch immer. Ein weiterer sehr nützlicher Ansatz ist das Spielen mit TM-Simulatoren. [3]

All dies wäre viel offensichtlicher, wenn sie in einigen Klassen CS mit echten TM-Compilern unterrichten würden, die ein beliebiges Programm ( Quellcode ) in eine TM-Statustabelle (ähnlich wie Objektcode) kompilieren würden . Leider glaubt derzeit niemand, dass dies nützlich ist. [1] ^{(Bitte stimmen Sie ab, um wieder zu öffnen, wenn Sie nicht einverstanden sind! =)}

Wenn Sie jedoch mit TM-Simulatoren spielen, können Sie diese grundlegende Intuition aufbauen. [2] ist derzeit möglicherweise das fortschrittlichste auf der Welt.

[1] /cs/2916/is-there-a-compiler-from-high-level-language-to-turing-machine

[2] TM-Compiler in Ruby mit Beispiel für Quell- / Objektcode und Ausgabe (für ein Nonhalting$a+b=b+a$ kommutativer Additionsgesetzprüfer)

[3] /cs/10379/top-turing-machine-simulators-on-the-web