Standarddefinition der Turingmaschine

Ich habe zwei berühmte Bücher über "Automaten und formale Sprachtheorie" verfolgt:

1. Micheal Sipsers Buch
2. Jeffrey Ullman und John Hopcrofts Buch

In beiden Büchern unterscheidet sich die Tupel-Level-Definition der Turing-Maschine voneinander. Obwohl die Arbeit auf abstrakter Ebene gleich ist, unterscheiden sich die Details. Warum gibt es keine Standarddefinition? Sogar einige andere Bücher haben die Turing-Maschine auf andere Weise erklärt.

Wenn wir versuchen, die zeitliche Komplexität desselben Algorithmus auf diesen Maschinen zu messen, unterscheidet sich auch die genaue Zeit. Warum haben sich die Autoren / Wissenschaftler nicht auf eine Standarddefinition geeinigt?

Es gibt keine Standarddefinition, da es ungewöhnlich ist, die Details der Definition der Turing-Maschine zu verwenden. Im Gegensatz zu anderen Definitionen in der Mathematik sind Turing-Maschinen komplizierte Objekte, deren Definition nicht direkt verwendet werden kann. Stattdessen berufen wir uns auf die Church-Turing-Hypothese und beschreiben Turing-Maschinen, indem wir Algorithmen angeben, anstatt Tupel aufzulisten. Zu diesem Zeitpunkt ist die genaue Definition der Turing-Maschine unwichtig.

Eine ähnliche Situation tritt in anderen Fällen auf, von denen ich zwei beschreiben werde: Zahlensysteme und Forcen .

Zahlensysteme , insbesondere die reellen Zahlen, haben verschiedene Konstruktionen. Wenn Sie sich Bücher ansehen, die eine Konstruktion der reellen Zahlen enthalten, werden Sie wahrscheinlich unterschiedliche Konstruktionen sehen, in einigen Fällen sehr unterschiedliche (z. B. Dedekind-Schnitte im Vergleich zu Cauchy-Sequenzen). Aus Sicht des Benutzers ist es jedoch alles, was uns wichtig ist, dass die reellen Zahlen, die wir konstruieren, die Feldaxiome erfüllen sowie vollständig und archimedisch sind (die genaue Bedeutung dieser Begriffe ist unwichtig). Wir können die eigentlichen zugrunde liegenden Definitionen fast nie verwenden.

Forcen ist eine wichtige Beweismethode in der Mengenlehre. Das Erzwingen kann auf verschiedene Arten definiert werden, wobei das Erzwingen von Beziehungen und Modellen mit Booleschen Werten am beliebtesten ist. (Eine weniger beliebte ist die Modallogik.) Diese Methoden sind alle gleichwertig, aber die formale Entwicklung kann etwas anders sein. Alle diese Methoden führen zu den gleichen Beweisen in der Mengenlehre, aber es gibt keinen "offiziellen". Welches Sie in einem Lehrbuch oder Kurs zur Mengenlehre präsentieren, hängt von Ihrem persönlichen Geschmack ab.

Die genaue Definition der Turing-Maschine spielt eine Rolle, wenn Sie an einem genauen Ressourcenverbrauch interessiert sind, beispielsweise wie viele Schritte erforderlich sind, um ein bestimmtes Problem zu lösen. Da alle vernünftigen Definitionen von Turing-Maschinen zu gleichen Laufzeiten bis hin zu konstanten Faktoren führen und wir uns normalerweise nicht um konstante Faktoren an sich kümmern, spielt die genaue Definition keine Rolle und liefert die gleichen Ergebnisse.

Die gleiche Situation tritt auf, wenn andere Theoreme bewiesen werden, in denen die Church-Turing-Hypothese nicht verwendet werden kann. Wenn wir beispielsweise Cooks Theorem beweisen, dass SAT NP-vollständig ist, müssen wir uns wirklich auf die Definition der Turing-Maschine beziehen. Die Konstruktion funktioniert jedoch für viele verschiedene Definitionen auf die gleiche Weise. Wir wählen eine Definition willkürlich aus und halten uns daran, da wir wissen, dass die Verwendung einer anderen Variante zu einem etwas anderen, aber immer noch gültigen Beweis führt.

Das passiert oft; Zum Beispiel gibt es mehrere Definitionen von endlichen Automaten.

Es gibt zwei Dinge, die uns normalerweise an Rechenmodellen (und an TCS) interessieren:

1. Rechenleistung und
2. Kostenmaßnahmen.

Wenn 1. gleich ist und 2. sich nur unwesentlich unterscheidet (Komplexitätstheoretiker würden sagen, durch einen Polynom / Polylogarithmus / Konstanten / ... Faktor), können wir zwischen (ungefähr) äquivalenten Definitionen wechseln.

Die Bedingungen können formal nachgewiesen werden, sofern die Modelle formal definiert sind. Dies kann eine veranschaulichende Übung für Sie sein.

Warum dann unterschiedliche Definitionen? Weil der eine oder andere Beweis einfacher sein kann oder das eine oder andere Konzept genauer beschrieben wird. Daher kann das Ziel eines Kurses / Buches, die Auswahl der Themen, der didaktische Ansatz und der Geschmack des Autors dazu führen, dass eine Definition besser funktioniert als eine andere.

Ich werde versuchen, einen etwas anderen Ansatz als die anderen Antworten zu wählen und insbesondere das Standardisierungsproblem zu untersuchen.

Es ist ein bisschen überraschend, dass Sie sich über diese Situation wundern. Das Hopcroft-Ullman-Buch (ich verwende die Ausgabe von 1979) enthält zwei Definitionen des PushDown-Automaten (PDA): Akzeptanz nach Endzustand oder nach leerem Stapel.

Wenn Sie den Abschnitt über die Konstruktionstechniken von Turing Machines (TM) lesen (Abschnitt 7.4 in der Ausgabe von 1979), heißt es ausdrücklich:

Das Entwerfen von Turing-Maschinen durch Aufschreiben eines vollständigen Satzes von Zuständen und einer Funktion für den nächsten Schritt ist eine spürbar unbelohnende Aufgabe. Um komplizierte Turing-Maschinenkonstruktionen zu beschreiben, benötigen wir einige "übergeordnete" konzeptionelle Werkzeuge.

Der Rest des Abschnitts und die folgenden Abschnitte zeigen alle Arten von Variationen der Definition eines TM, die die Definition erweitern oder einschränken und alle gleichwertig sind.

Der Punkt ist, dass wir für jedes Problem die Definition auswählen, die am besten geeignet ist, um dieses Problem zu lösen. Natürlich könnte jede dieser Definitionen im Prinzip funktionieren. Abhängig vom Problem geben Ihnen einige Definitionen mehr Klarheit über ein bestimmtes Problem und erleichtern so die Beweise.

In Bezug auf kontextfreie (CF) Sprachen und Grammatiken wurden viele Normalformen definiert: Chomsky-Normalform, Greibach-Normalform, Binärform. Alle können jede CF-Sprache generieren und sie können als Variationen der CF-Grammatikdefinition angesehen werden. Es ist gut, sie koexistieren zu lassen, weil jeder in einem bestimmten Kontext eine Rolle spielt. Sie sind übersetzbar, aber kostenpflichtig.

Wenn Sie versuchen, die Kosten / Komplexität der CF-Analyse zu analysieren, sind diese nicht gleichwertig, und dies ist zu berücksichtigen. Dieses Komplexitätsproblem ist im CF-Fall viel kritischer als im TM-Fall, da CF-Parser in technischen Situationen häufig verwendet werden, während TM ein rein theoretisches Werkzeug ist. Dies hindert Ingenieure, die CF-Parsing verwenden, nicht daran, verschiedene Grammatikformen für dieselbe Sprache auf koordinierte Weise zu verwenden, um verschiedene Probleme zu berücksichtigen.

Im Fall von CF-Sprachen kann dies ein kritisches technisches Problem sein , und es war daher zu erwarten, dass CF-Grammatiken und ihre verschiedenen Formen ungefähr so ​​stark normalisiert / standardisiert werden wie die Größe der Schraubenschlüssel oder der Durchmesser der elektrischen Drähte. Tatsächlich ging es sogar darum, eine genaue Syntax für das Schreiben von CF-Grammatiken zu definieren, die Backus Naur Form (BNF) .

TM hat nur wenige technische Anwendungen, die eine Normalisierung rechtfertigen würden, und sie weisen eine viel größere potenzielle Variabilität auf (was jedoch teilweise berücksichtigt wird, wenn größere Variationen wie Multi-Tape, Multi-Head, ... berücksichtigt werden). Dies erklärt, dass es wenig Druck gab, eine Standardform anzunehmen, da Mathematiker, die sie verwenden, technisch ausgereift genug sein sollten, um vorsichtig zu sein, wenn es einen Unterschied machen kann, so genau die Anzahl der Züge zu zählen. Selbst für die Komplexität spielen die kleinen Variationen in den Definitionen oft keine Rolle, da wir nur die asymptotische Komplexität und oft die asymptotische Komplexität bis zu einer Polynomfunktion betrachten.

In der Mathematik (unter anderen Wissenschaften) ist es durchaus üblich, dass verschiedene Autoren unterschiedliche Definitionen wählen, von denen bekannt ist, dass sie gleichwertig sind (oder in den meisten Zusammenhängen gleichwertig sind), abhängig von ihrem Geschmack, ihrer Sicht auf Anwendungen, ihrer Vision der Problemstruktur. ihre pädagogischen Zwecke usw. Definitionen entwickeln sich auch mit der Zeit, wenn mehr über ein Problem bekannt wird und sich die Perspektiven ändern. Gleiches gilt für Notationen. Diese Variabilität ist eine wichtige Quelle für Fortschritt und Verständnis. Die Griechen machten ausgezeichnete Mathematik, aber mit modernen Konzepten (z. B. Variablen ), Definitionen und Notationen ist es viel einfacher .

Standards werden oft als äußerst praktisch angesehen (siehe Schraubenschlüssel und Drahtdurchmesser). Sie können aber auch ein Faktor der Starrheit sein, der den Fortschritt verhindert. Standardisierung ist ein zweischneidiges Schwert, daher müssen wir es aus Sicherheitsgründen ein wenig stumpfen. Die verschiedenen Definitionen sind normalerweise nicht ganz identisch, aber nahe genug, so dass sich Theorien mehr oder weniger auf die gleiche Weise entwickeln können.