Eingabelänge auf einer Ein-Band-Turing-Maschine berechnen

Im Zusammenhang mit dieser Frage stellte sich mir die Frage : Wie viel Zeit benötigt eine Single-Tape-Single-Head-Turing-Maschine, um die Länge ihrer Eingabe zu berechnen? Angenommen, das Bandalphabet ist , die Eingabe ist eine Zeichenfolge in die von Leerzeichen umgeben ist. Die Maschine beginnt am linken Eingabesymbol und muss bei enden Das Symbol ganz links in (ebenfalls von Leerzeichen umgeben), das die binäre Darstellung der Eingabelänge angibt. Dies kann auch als das Problem angesehen werden, eine Zahl von unär nach binär umzuwandeln. $\{0,1,b\}$ $(0+1)^*$ $(0+1)^*$

Es ist einfach, dies auf einem Zwei-Band-Computer oder einem Zwei-Kopf-Computer in linearer Zeit zu lösen (scannen Sie einfach die Eingabe mit einem Kopf, während Sie den anderen Kopf zum wiederholten Inkrementieren eines Zählers verwenden; Inkrementieren ist eine konstant amortisierte Zeitoperation). Die Einzelkopflösungen, die ich finden kann, sind jedoch nur (z. B. durch wiederholtes Inkrementieren eines Zählers und anschließendes Verschieben um eine Position entlang des Bandes). Gibt es eine passende Untergrenze? $O(n\log n)$

Ich habe einige Suchanfragen durchgeführt, aber Ausdrücke wie "ein Kopf" und "Eingabelänge" sind so verbreitet, dass es schwierig ist, in der Literatur nach bekannten Ergebnissen zu diesem Problem zu suchen.

turing-machines David Eppstein
quelle

Interessant .. Dies ist weniger offensichtlich, als es scheint, sollte es sein. Ich bin neugierig, ob es eine Beziehung zwischen einer Untergrenze für diese und einer Untergrenze für die vergessene TM-Simulation gibt. (Jedes TM, das dieses Problem löst, würde per Definition vergessen (oder überflüssigen Code haben).)

Daniel Apon

Antworten:

Es kann nicht in der Zeit berechnet werden . $o(n\lg n)$

Sei eine Maschine, bei der eine eingegebene Zeichenfolge mit der Größe von stoppt, die binär auf das Band geschrieben ist. $M$ $x$ $x$

Wir können einen einfachen DFA (mit linearer Zeit im Nullraum) zu hinzufügen , um zu überprüfen, ob die Größe der Eingabe eine Zweierpotenz ist: Überprüfen Sie einfach, ob das erste Bit 1 und der Rest Null ist. $M$

Nehmen wir an, dass die Zeit . Dann können wir in der Zeit dass die Größe der Eingabe eine Potenz von zwei ist. Mit anderen Worten ist die folgende Sprache in . Es folgt aus $M$ $o(n \lg n)$ $o(n \lg n)$ $\mathsf{DTime}(n \lg n)$

L = {0^{ich} ∣ \exists k ich = 2^{k}}

$L = \{ 0^i \mid \exists k \ i = 2^k\}$

dass

soll regelmäßig sein. Es ist jedoch leicht zu überprüfen, ob die Sprache nicht regelmäßig ist. So

kann inZeit nicht ausgeführt

D T i m e (o (n \lg n)) = R e g

$\mathsf{DTime}(o(n \lg n)) = \mathsf{Reg}$

L

$L$

M

$M$

o (n \lg n)

$o(n \lg n)$

Kaveh
quelle

Ich vermisse hier etwas: Wenn Sie sagen,

, ziehen Sie Berechnungen auf einem Einzelbandgerät in Betracht? Normalerweise denke ich, werden Zwei-Band-Maschinen verwendet, um Komplexitätsklassen zu definieren. Eine sehr verwandte Frage ist, woher das obige Ergebnis kommt.

D T i m e (o (n \lg n)) = R e g

$\mathsf{DTime}(o(n\lg n))=\mathsf{Reg}$

Bruno

@Bruno, ja, ich spreche von Single-Tape-Turing-Maschinen. Ich bin nicht sicher, was der Standard ist, um die Komplexitätsklassen zu definieren, verschiedene Bücher verwenden unterschiedliche Modelle. Die Originalarbeiten der Komplexitätstheorie wurden mehrere Band diejenigen mit Ich denke , aber es scheint , dass sich geändert hat, sehen diese . Für

Sie es in "Classical Rekursionstheorie" vol finden. II und "Handbuch der Theoretischen Informatik".

D T i m e (n \lg n) = R e g

$\mathsf{DTime}(n \lg n) = \mathsf{Reg}$

Kaveh

Vielen Dank für die Hinweise, ich hatte einen Blick in "Classical Recursion Theory" vol. II. Dass es sich geändert hat, ist mir nicht so klar. Zum Beispiel verwendet Sipsers Buch Single-Tape-TMs, um Zeitkomplexitätsklassen zu definieren, aber Hopcroft-Ullmans Buch und das neueste Arora-Barak- und Goldreich-Buch verwenden Multitape-TMs.

Bruno

@Bruno, ich denke, was die allgemeinere Definition von DTime ist, ist komplizierter. ZB gilt die allgemein geltend gemachte Behauptung, dass "der Zeithierarchiesatz nicht als eng bekannt ist" nur für Einzelbandmaschinen, für Doppelbandmaschinen als eng bekannt seit 1982.

Kaveh

D T i m e

$\mathsf{DTime}$