Definitionen von Turingmaschinen beziehen sich immer explizit darauf, dass das leere Symbol nicht Teil des eingegebenen Alphabets ist.
Ich frage mich , was schief geht , wenn Sie würde es ein Teil des Eingabealphabet machen, weil effektiv das leere Symbol bereits Teil des Eingangs zu sein scheint.
Um zu erklären, dass 'scheint' im letzten Satz, betrachten Sie das Folgende.
In der Standardeinstellung wird rechts neben der Eingabe eine unbegrenzte Anzahl leerer Symbole angezeigt. Wenn sich der Bandkopf über das erste leere Symbol bewegt, kann die Berechnung einfach fortgesetzt werden, da es sich nicht um einen Annahme- oder Ablehnungszustand handeln muss.
Angenommen, die Berechnung würde anschließend Symbole aus dem Eingabealphabet rechts von diesem ersten leeren Symbol schreiben und dann an die äußerste linke Position zurückkehren und gleichzeitig in den Startzustand zurückkehren. Es würde dann mit einem anderen Band "von vorne beginnen". Tatsächlich beginnt es jetzt mit einer anderen Eingabe, bei der sich rechts neben dem Leerzeichen Eingabesymbole befinden, die vorher nicht vorhanden waren. Die Eingabe scheint effektiv das leere Symbol zu enthalten. Das weitere Verhalten der Maschine könnte nun auch anders sein: Nach erneutem Auftreffen auf den Rohling werden rechts verschiedene Symbole angezeigt.
Angenommen, dieses Szenario ist in der Tat möglich. Warum würden Sie das leere Symbol nicht als Teil des Eingabealphabets betrachten und warum würden Sie es nicht als Teil der 'anfänglichen' Eingabe zulassen?
Vielleicht ist es nur eine Möglichkeit, die Eingabe so zu definieren, dass sie nicht immer unendlich ist?
quelle
Antworten:
Der Hauptgrund ist, dass das Gerät das Ende seiner Eingabe erkennen kann: Es ist (das Zeichen vor) das erste Leerzeichen. Wenn Sie Leerzeichen in der Eingabe zulassen, kann das Gerät niemals erkennen, ob es möglicherweise mehr Eingaben findet, indem es weiter rechts scannt. Sie könnten das natürlich lösen, indem Sie ein spezielles "Ende der Eingabe" -Zeichen haben, aber dann müssen Sie darauf bestehen, dass das nicht in der Eingabe erscheint, also haben Sie das Problem nur eine Ebene tiefer verschoben.
Dies erleichtert auch die Angabe der Anfangsbedingungen: Die Eingabe ist der nicht leere Abschnitt des Anfangsbands, der endlich und zusammenhängend sein muss. Und wenn Sie möchten, dass ein leeres Zeichen Teil des eingegebenen Alphabets ist, können Sie jederzeit ein zusätzliches Zeichen hinzufügen (nennen Sie es "Leerzeichen" oder so) und die Maschine so verhalten, wie Sie es möchten, wenn sie es sieht.
quelle
Sie können das leere Symbol als Teil des Alphabets definieren. Das Problem dabei ist, dass wenn eine Turing-Maschine mit dem Eingang b010010b (wobei b für leer steht ) niemals nach dem zweiten b liest, sich die Maschine bei allen Eingaben, die mit b010010b beginnen, genauso verhält.
Diese Turingmaschinen werden Präfix-Turingmaschinen genannt und sind sehr nützlich, um einige Theoreme über die Komplexität von Kolmogorov zu beweisen.
quelle
Sehr kurze Antwort: Das Bandalphabet ist der Satz von Symbolen, die auf dem Band erscheinen können, und es enthält das leere Symbol. Das Eingabealphabet besteht aus einer Reihe von Symbolen, die bei der ersten Eingabe angezeigt werden können , und enthält kein leeres Symbol. Das Hauptalphabet, um das sich das Gerät kümmert, ist das Bandalphabet: Es benötigt weiterhin Regeln, was zu tun ist, wenn beispielsweise ein Leerzeichen angezeigt wird.
Diese Unterscheidung ist wichtig, wie andere gesagt haben, damit die Maschine erkennen kann, wo ihre Eingabe endet. Es ist der gleiche Grund, warum Sie in C (sinnvollerweise) kein Nullzeichen in die Mitte eines Strings setzen können: Das Nullzeichen ist reserviert, um "das letzte Nicht-Nullzeichen" zu bedeuten, bevor dies das Ende der Daten ist wenn du das siehst, bist du fertig ". Wenn Sie in der Mitte der Zeichenkette Null-Zeichen erwarten müssen, wird das Schreiben
strlen
sehr viel schwieriger.quelle