Ist eine Turing-Maschine, die nicht in der Lage ist, auf leere Zellen zu schreiben, weniger leistungsfähig als eine Standard-Turing-Maschine?

Ist eine Turing-Maschine, die nicht in der Lage ist, auf leere Zellen zu schreiben, weniger leistungsfähig als eine Standard-Turing-Maschine?

Ich denke, die Antwort ist ja, aber ich kann keine Berechnung finden, die die Standard-Turing-Maschine kann, aber diese Maschine nicht.

Irgendwelche Ideen?

Mit anderen Worten: " Wäre ein Computer mit begrenztem Arbeitsspeicher weniger leistungsfähig als ein Computer mit unbegrenztem Arbeitsspeicher ?"

Nat

Antworten:

Der von Ihnen beschriebene Turing-Maschinentyp ist ein linear begrenzter Automat (er kann nur auf die Teile des Bandes schreiben, die die Eingabe enthalten). LBAs sind die Akzeptoren für kontextsensitive Sprachen. Um ein spezifisches Beispiel für ein Problem zu finden, das mit dieser Einschränkung nicht gelöst werden kann, das aber im Allgemeinen von einer Turing-Maschine gelöst werden kann, benötigen Sie lediglich eine Sprache, die entscheidbar, aber nicht kontextsensitiv ist. empfindlich.

Das Beispiel auf Wikipedia ist:

Ein Beispiel für eine rekursive Sprache, die nicht kontextsensitiv ist, ist jede rekursive Sprache, deren Entscheidung ein EXPSPACE-schwieriges Problem darstellt, beispielsweise die Menge von Paaren äquivalenter regulärer Ausdrücke mit Exponentiation.

Weitere Beispiele finden Sie unter Gibt es ein Beispiel für eine rekursive Sprache, die nicht kontextsensitiv ist?

Roctothorpe
quelle

Eine Turing-Maschine, die nicht auf Leerzeichen schreiben kann, ist nach der Raumversion des linearen Beschleunigungssatzes ein linear begrenzter Automat. Daher kann ein Entscheidungsproblem außerhalb von nicht von ihm entschieden werden. Solche Probleme existieren nach dem Raumhierarchiesatz. $\textsf{DSPACE}(O(n))$

schnelle Sorte
quelle

Können Sie für ein bestimmtes Problem nicht einfach ein ausreichend langes Suffix mit speziellen Symbolen am Ende des Bands angeben, das als Leerzeichen verwendet werden kann?

Gen

@gen Im Allgemeinen nicht. Beachten Sie im allgemeinen Fall nur, dass das Problem des Anhaltens entschei- dbar wird, wenn Sie ein so langes Suffix kennen. Folglich kann die Berechnung eines ausreichend langen Präfixes im Allgemeinen unentscheidbar sein - daher ist es nicht zumutbar anzunehmen, dass ein solches Suffix angegeben wird.

Chi

Wäre es richtig, diese Antwort so zu interpretieren, dass " Turing-Maschinen mit begrenztem Arbeitsspeicher nicht genug Arbeitsspeicher haben, um ein beliebiges Programm auszuführen, da einige Programme möglicherweise mehr Arbeitsspeicher benötigen als sie zufällig haben "?

Nat

@Nat: Ich würde es so ausdrücken, dass "die Menge an Speicher, die ein Programm möglicherweise benötigt, im Allgemeinen nicht bekannt ist, bis das Programm ausgeführt wird". Das Merkwürdige (ein großes mathematisches Paradoxon) ist, dass für jedes ganzzahlige Triplett X, Y, Z eine Obergrenze für die Anzahl der Bandzellen existiert, die für Programme erforderlich sind, die beendet werden und die höchstens X-Zustände enthalten, auf Bändern, die halten können höchstens Y-Symboltypen und werden mit Z-Symbolen auf dem Band initialisiert, aber keine solche Obergrenze ist nachweisbar, mit Ausnahme der trivialen Werte von X, Y und Z.

supercat