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

11

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?

Ben I.
quelle

Antworten:

21

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
6
Damit ist ein interessantes Ergebnis verbunden. Jede Turing-Maschine, die im wird, akzeptiert eine reguläre Sprache. Ö(LogLogn)
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 2 k log log n = 2 log ( log k n ) = log k n Zeit ausgeführt werden. Es ist jedoch nicht schwer zu zeigen, dass jedes TM, das in o ( n ) Zeit ausgeführt wird, eine Sprache entscheidet, die auch in O ( 1 ) Zeit entschieden werden kann. Dann gibt es eine Konstante c N, so dass das erste ckLogLogn2kLogLogn=2Log(Logkn)=LogknÖ(n)Ö(1)cN.cZeichen 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 0 i c { 0 , 1 } i ein . Vermisse ich etwas Wo ist mein Fehler? 0ichc{0,1}}ich
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 n 2 k log log n . 2kLogLognn2kLogLogn
Skankhunt42
4

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.

RessourceEndliche Automaten:EINLBTM:M.Bandgröße eingebenÖ(N.)Ö(N.)BandoperationenSchreibgeschütztLesen SchreibenBandbewegungVon links nach rechts, nur ein DurchgangBeide Richtungen, keine DurchgangsgrenzeAnzahl der Standorte (Staaten)M.M.Alphabet eingebenΣΣAnnahmebedingungEndliche Position erreichen: fEndliche Position erreichen: f

M.EINEIN

RessourceEndliche Automaten:EIN'LBTM:M.Bandgröße eingebenÖ(N.)Ö(N.)BandoperationenSchreibgeschütztLesen SchreibenBandbewegungVon links nach rechts, nur ein DurchgangBeide Richtungen, keine DurchgangsgrenzeAnzahl der Standorte (Staaten)M.×2N.M.Alphabet eingebenΣΣAnnahmebedingungEndliche Position erreichen: f'Endliche Position erreichen: f

EIN'M.EIN'N.EINN.M.M.

Devendra Bhave
quelle