¿Por qué las máquinas de Turing con límites lineales son más potentes que los autómatas de estado finito?

11

Tenía la impresión de que nuestras computadoras, siendo finitas, en última instancia no son más poderosas que las máquinas de estado finito (extraordinariamente grandes). Sin embargo, las máquinas de Turing con límites lineales también son finitas, pero parece que los lenguajes regulares son estrictamente un subconjunto incorrecto de lenguajes sensibles al contexto.

Obviamente, me falta algo aquí. Que esta pasando?

Ben I.
fuente

Respuestas:

21

La máquina de Turing lineal limitada está restringida a una cinta cuya longitud es una función lineal de la longitud de la entrada.

Si el límite de longitud fuera constante, la máquina no sería más poderosa que un DFA. Sin embargo, un DFA no puede hacer crecer más estados para hacer frente a una entrada más larga, lo que en efecto el LBTM puede hacer (tomando el estado como la configuración completa de la máquina). Por lo tanto, el LBTM es estrictamente más poderoso.

rici
fuente
66
o(loglogn)
@ skankhunt42, ¿por qué es eso?
Ben I.
kloglogn2kloglogn=2log(logkn)=logkno(n)O(1)cNc0ic{0,1}i
@Choirbean Requiere una prueba usando secuencias cruzadas. Puede buscarlo aquí cs.stackexchange.com/questions/7372/… .
skankhunt42
2kloglognn2kloglogn
4

Creo que primero debemos entender la descripción de una máquina y el tamaño de entrada, para que la comparación sea solo de objetos válidos. Digamos que N es un tamaño de entrada. Esto significa que las máquinas tendrán estos límites de recursos.

ResourceFinite Automata:ALBTM:MInput Tape SizeO(N)O(N)Tape OperationsRead OnlyRead, WriteTape MovementLeft to right, One pass onlyBoth directions, No pass limit# of Locations (States)MMInput AlphabetΣΣAcceptance ConditionReach finite location: fReach finite location: f

MAA

ResourceFinite Automata:ALBTM:MInput Tape SizeO(N)O(N)Tape OperationsRead OnlyRead, WriteTape MovementLeft to right, One pass onlyBoth directions, No pass limit# of Locations (States)M×2NMInput AlphabetΣΣAcceptance ConditionReach finite location: fReach finite location: f

AMANANMM

Devendra Bhave
fuente