Warum sind linear begrenzte Turingmaschinen leistungsfähiger als Finite-State-Automaten?

Ich hatte den Eindruck, dass unsere Computer, da sie endlich sind, letztendlich nicht leistungsfähiger sind als (außerordentlich große) endliche Zustandsmaschinen. Linear gebundene Turing-Maschinen sind zwar auch endlich, aber es scheint, dass reguläre Sprachen streng genommen eine unangemessene Teilmenge kontextsensitiver Sprachen sind.

Offensichtlich fehlt mir hier etwas. Was ist los?

finite-automata computation-models linear-bounded-automata Ben I.
quelle

Antworten:

Die linear begrenzte Turing-Maschine ist auf ein Band beschränkt, dessen Länge eine lineare Funktion der Länge der Eingabe ist.

Wenn die Längenbeschränkung konstant wäre, wäre die Maschine nicht leistungsfähiger als ein DFA. Ein DFA kann jedoch nicht mehr Zustände wachsen lassen, um mit einer längeren Eingabe fertig zu werden, was der LBTM tatsächlich tun kann (wobei der Zustand die gesamte Maschinenkonfiguration darstellt). Daher ist der LBTM streng leistungsfähiger.

Rici
quelle

Damit ist ein interessantes Ergebnis verbunden. Jede Turing-Maschine, die im

wird, akzeptiert eine reguläre Sprache.

o (\log \log n)

$o(\log \log n)$

Skankhunt42

@ skankhunt42, warum ist das so?

Ben I.

@ skankhunt42: Korrigieren Sie mich, wenn ich falsch liege, aber… jedes TM, das in

Speicherplatz ausgeführt wird, muss in

Zeit ausgeführt werden. Es ist jedoch nicht schwer zu zeigen, dass jedes TM, das in

Zeit ausgeführt wird, eine Sprache entscheidet, die auch in

Zeit entschieden werden kann. Dann gibt es eine Konstante

so dass das erste

k \log \log n

$k \log \log n$

2^{k \log \log n} = 2^{\log (\log^{k} n)} = \log^{k} n

$2^{k \log \log n} = 2^{\log (\log^k n)} = \log^k n$

o (n)

$o(n)$

O (1)

$\mathcal O(1)$

c \in N

$c \in \mathbb N$

c

$c$ Zeichen der Eingabe bestimmen, ob die Eingabe in der Sprache erfolgt. Aber dann ist die Sprache offensichtlich regulär:

einfach einen Zustand für jedes Präfix in

. Vermisse ich etwas Wo ist mein Fehler?

⋃_{0 \leq i \leq c} {0, 1}^{i}

$\bigcup_{0 \leq i \leq c} \{ 0, 1 \}^i$

wchargin

@Choirbean Es erfordert einen Beweis mit Kreuzungssequenzen. Sie können es hier nachschlagen cs.stackexchange.com/questions/7372/… .

Skankhunt42

@wchargin Ich denke, der Fehler könnte darin bestehen, dass das TM in

Zeit ausgeführt wird, da Sie die Kopfposition des Eingabebandes auch beim Zählen der Anzahl der Konfigurationen berücksichtigen müssen. Ich denke also, das TM läuft in der Zeit

2^{k \log \log n}

$2^{k \log \log n}$

n 2^{k \log \log n}

$n 2^{k \log \log n}$

Skankhunt42

Ich denke, wir müssen zuerst die Beschreibung einer Maschine und die Eingabegröße verstehen, damit der Vergleich nur gültige Objekte betrifft. Angenommen, N ist eine Eingabegröße. Dies bedeutet, dass Maschinen diese Ressourcengrenzen haben.

\begin{array}{lll} Ressource & Endliche Automaten: EIN & LBTM: M. \\ Bandgröße eingeben & Ö (N.) & Ö (N.) \\ Bandoperationen & Schreibgeschützt & Lesen Schreiben \\ Bandbewegung & Von links nach rechts, nur ein Durchgang & Beide Richtungen, keine Durchgangsgrenze \\ Anzahl der Standorte (Staaten) & M. & M. \\ Alphabet eingeben & Σ & Σ \\ Annahmebedingung & Endliche Position erreichen: ℓ_{f} & Endliche Position erreichen: ℓ_{f} \end{array}

$\begin{array}{|l|l|l|} \hline \mbox{Resource} & \mbox{Finite Automata:}\quad \mathcal{A} & \mbox{LBTM:} \quad \mathcal{M}\\ \hline \mbox{Input Tape Size} & O(N) & O(N)\\ \mbox{Tape Operations} & \mbox{Read Only}& \mbox{Read, Write}\\ \mbox{Tape Movement} & \mbox{Left to right, One pass only}& \mbox{Both directions, No pass limit}\\ \mbox{# of Locations (States)} & M & M\\ \mbox{Input Alphabet} & \Sigma & \Sigma\\ \mbox{Acceptance Condition} & \mbox{Reach finite location: }\ell_f & \mbox{Reach finite location: }\ell_f\\ \hline \end{array}$

$\mathcal{M}$ $\mathcal{A}$ $\mathcal{A}$

\begin{array}{lll} Ressource & Endliche Automaten: {EIN}^{'} & LBTM: M. \\ Bandgröße eingeben & Ö (N.) & Ö (N.) \\ Bandoperationen & Schreibgeschützt & Lesen Schreiben \\ Bandbewegung & Von links nach rechts, nur ein Durchgang & Beide Richtungen, keine Durchgangsgrenze \\ Anzahl der Standorte (Staaten) & M. \times 2^{N.} & M. \\ Alphabet eingeben & Σ & Σ \\ Annahmebedingung & Endliche Position erreichen: ℓ_{f}^{'} & Endliche Position erreichen: ℓ_{f} \end{array}

$\begin{array}{|l|l|l|} \hline \mbox{Resource} & \mbox{Finite Automata:}\quad \mathcal{A'} & \mbox{LBTM:} \quad \mathcal{M}\\ \hline \mbox{Input Tape Size} & O(N) & O(N)\\ \mbox{Tape Operations} & \mbox{Read Only}& \mbox{Read, Write}\\ \mbox{Tape Movement} & \mbox{Left to right, One pass only}& \mbox{Both directions, No pass limit}\\ \mbox{# of Locations (States)} & M \times 2^N & M\\ \mbox{Input Alphabet} & \Sigma & \Sigma\\ \mbox{Acceptance Condition} & \mbox{Reach finite location: }\ell'_f & \mbox{Reach finite location: }\ell_f\\ \hline \end{array}$

$\mathcal{A}'$ $\mathcal{M}$ $\mathcal{A}'$ $N$ $\mathcal{A}$ $N$ $\mathcal{M}$ $\mathcal{M}$

Devendra Bhave
quelle