Praktische Bedeutung von Turingmaschinen?

Ich bin Elektroingenieur und hatte vor 26 Jahren nur einen CS-Kurs am College. Ich bin jedoch auch ein begeisterter Mathematica-Benutzer.

Ich habe das Gefühl, dass Turingmaschinen in der Informatik sehr wichtig sind. Ist die Bedeutung nur in der Theorie der Informatik? Wenn es praktische Auswirkungen / Anwendungen gibt, welche sind dies?

Die Bedeutung von Turingmaschinen ist zweifach. Erstens waren Turing-Maschinen eines der ersten (wenn nicht das erste) theoretischen Modelle für Computer aus dem Jahr 1936. Zweitens wurde eine Menge theoretischer Informatik mit Blick auf Turing-Maschinen entwickelt, und daher sind viele der grundlegenden Ergebnisse vorhanden in der Sprache der Turingmaschinen. Ein Grund dafür ist, dass Turing-Maschinen einfach und damit analysierbar sind.

Turing-Maschinen sind jedoch kein praktisches Modell für das Rechnen. Als Ingenieur und Mathematica-Benutzer sollten sie Sie überhaupt nicht betreffen. Auch in der theoretischen Informatik werden die realistischeren RAM-Maschinen in den Bereichen Algorithmen und Datenstrukturen eingesetzt.

Tatsächlich sind Turing-Maschinen aus Sicht der Komplexitätstheorie polynomiell äquivalent zu vielen anderen Maschinenmodellen, und so können Komplexitätsklassen wie P und NP in Bezug auf diese Modelle äquivalent definiert werden. (Andere Komplexitätsklassen sind heikler.)

Turingmaschinen waren eines der frühen Modelle für die Berechnung, das heißt, sie wurden entwickelt, als die Berechnung selbst nicht sehr gut verstanden wurde (um 1940). Ich möchte mich auf zwei Aspekte konzentrieren, die (wohl) dazu geführt haben, dass sie damals das bevorzugte Modell waren, was dazu führte, dass sie das etablierteste und damit letztendlich auch das Standardmodell waren.

1. Einfachheit der Beweise
   Als theoretisches Modell haben Turing-Maschinen den Charme, "einfach" zu sein, da der aktuelle Maschinenzustand nur eine konstante Größe hat. Alle Informationen, die Sie zur Ermittlung des nächsten Maschinenzustands benötigen, sind ein Symbol und eine (Steuer-) Zustandsnummer. Die Änderung des Maschinenzustands ist ebenso gering und fügt nur die Bewegung des Maschinenkopfs hinzu. Das vereinfacht (formale) Beweise erheblich, insbesondere die Anzahl der zu unterscheidenden Fälle.

   Vergleichen Sie diesen Aspekt mit dem RAM-Modell (wenn es nicht in seiner minimalistischen Form verwendet wird): Die nächste Operation kann eine von mehreren Operationen sein, die auf beliebige (zwei) Register zugreifen können . Es gibt auch mehrere Kontrollstrukturen.

2. Laufzeit und Speicherplatznutzung
   Es gab (nur) zwei Hauptberechnungsmodelle, die fast gleichzeitig mit Turing Machines auftraten , nämlich Churchs -calculus und Kleenes -recursive Funktionen . Sie beantworteten die gleiche Frage, die Turing gestellt hatte - Hilberts Entscheidungsproblem -, ließen sich jedoch (wenn überhaupt) nicht so leicht zur Definition von Laufzeit und Speicherplatznutzung einsetzen. In gewissem Sinne sind sie zu abstrakt, um mit realistischeren Maschinenmodellen in Beziehung gesetzt zu werden.$\lambda$$\mu$

   Bei Turing-Maschinen lassen sich beide Begriffe jedoch leicht definieren (und waren, wenn ich mich recht erinnere, in Turings allererster Arbeit über sein Modell enthalten). Da Effizienzaspekte für die eigentliche Arbeit sehr wichtig waren, war dies ein klarer Vorteil von Turing-Maschinen.

So wurden Turingmaschinen als etablierte das Berechnungsmodell, das als Kombination aus historischen „Unfall“ und einige seiner wichtigsten Eigenschaften gesehen werden konnte. Dennoch wurden seitdem viele Modelle definiert und werden eifrig verwendet, insbesondere um die Mängel der Turing-Maschinen zu überwinden; Zum Beispiel sind sie mühsam, "zu programmieren" (dh zu definieren).

Mir sind keine direkten Anwendungen in der Praxis bekannt. Insbesondere die Rechenpraxis entwickelte sich parallel (und anfangs weitgehend unabhängig von) der Berechnungstheorie. Programmiersprachen wurden ohne formale Maschinenmodelle entwickelt. Es ist jedoch (im Nachhinein) klar, dass viele Fortschritte in der Rechenpraxis durch die Theorie ermöglicht wurden.

Denken Sie außerdem daran, dass der Wert, den ein theoretisches Konzept für die Praxis hatte, unter Berücksichtigung aller Nachkommen gemessen werden sollte, dh Nacharbeiten, Ergebnisse und neue Ideen, die durch dieses Konzept ermöglicht wurden. Und in dieser Hinsicht ist zu sagen, dass das Konzept der Turing-Maschinen (unter anderem) die Welt revolutioniert hat.

Die einzige vernünftigerweise praktische Anwendung, die ich mir vorstellen kann (in dem Sinne, dass Sie tatsächlich eine Turing-Maschine implementieren könnten), besteht darin, zu beweisen, dass eine Sprache über ausreichende Fähigkeiten verfügt.

Wenn Sie eine Programmiersprache (oder etwas anderes, das zur Berechnung von Dingen gedacht ist) entwerfen, möchten Sie möglicherweise sicherstellen, dass diese vollständig ist (dh in der Lage ist, alles zu berechnen, was berechenbar ist), indem Sie eine Turing-Maschine implementieren drin.

Natürlich können Sie auch alles andere implementieren, das Turing-vollständig ist (wie C oder kombinatorische Logik), aber manchmal ist eine Turing-Maschine die einfachste Option.

Turing-Maschine ist ein mathematisches Rechenmodell. Ihre Vorteile sind:

1. Entscheidbarkeit prüfen Wenn TM ein Problem nicht in abzählbarer Zeit lösen kann, könnte es keinen Algorithmus geben, der dieses Problem lösen könnte (das ist das Problem, das nicht entschieden werden kann).

Für ein Entscheidungsproblem, wenn sein TM in abzählbarer Zeit für alle Eingaben endlicher Länge stehen bleibt, können wir sagen, dass das Problem durch einen Algorithmus in abzählbarer Zeit gelöst werden könnte.

2. Problem klassifizieren TM hilft, entscheidbare Probleme in Klassen der Polynomialhierarchie zu klassifizieren.

Angenommen, wir haben festgestellt, dass das Problem entscheidbar ist. Dann ist unser Ziel, wie effizient wir es lösen können. Die Effizienz wurde in Schritten, zusätzlichem Platzbedarf und der Länge des Codes / der Größe des FSM berechnet.

3. Entwerfen und Implementieren von Algorithmen für praktische Maschinen TM hilft, die Vorstellung von Algorithmen in anderen praktischen Maschinen zu verbreiten. Nach erfolgreicher Überprüfung der 1,2-Kriterien können wir mit unseren praktischen Geräten / Computern Algorithmen entwerfen und implementieren.

Turingmaschinen sind gute Gedankenspiele mit wenig praktischem Nutzen. Es ist nicht schlimm, wenn man keinen hat. Alle Anwendungen einer Turingmaschine sind entweder intuitiv oder religiös, weil sie nicht bewiesen oder widerlegt werden können.