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?
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.
fuente