¿Cuáles son los límites útiles de Autómatas limitados lineales en comparación con las Máquinas Turing?

Hay idiomas que una máquina de Turing puede manejar que un LBA no puede, pero ¿hay algún problema práctico que los LBA no puedan resolver, pero las TM sí?¿Cuáles son los límites útiles de Autómatas limitados lineales en comparación con las Máquinas Turing?

Un LBA es solo una máquina de Turing con una cinta finita, y las computadoras reales tienen un almacenamiento finito, por lo que me parece que no hay nada de importancia práctica que un LBA no pueda hacer. Excepto por el hecho de que un Autómata limitado lineal no tiene solo una cinta finita, sino una cinta con un tamaño que es una función lineal del tamaño de la entrada. ¿La linealidad de la finitud restringe el LBA de alguna manera?

¿Hay problemas que un LBA no puede hacer frente, pero un autómata potencialmente limitado podría (si tales cosas existen)?

Fuente

2010-01-26 Bribles

¿Qué tan rápido puede ser la TM? – Beta

Hay TM's que actualmente exceden 1 BFs (BigaFlops). Teóricamente, ¡no se puede obtener mucho más rápido que eso! – RAL

@Robert Lamb: muy gracioso, pero mi pregunta era seria. Como no se puede construir una MT, necesitamos algún punto de referencia si vamos a preguntar sobre problemas "prácticos". – Beta

Voy a salir en una extremidad y decir "no". Casi todos los lenguajes de programación que usamos hoy son sensibles al contexto. (En realidad ni siquiera es sensible al contexto, solo un poco más fuerte que el contexto libre, IIRC). Y obviamente, si no podemos programarlo, realmente no nos importa ...

OTOH, todo esto depende de tu definición de "interesante" ... La función de Ackerman encaja claramente en esta categoría. .. es eso interesante?

Fuente

2010-02-24 17:02:35

¿Estás diciendo que la función de Ackerman no puede ser computada por un LBA? – Bribles

Estoy bastante seguro de que Ackerman's tiene PSpace, así que no es computable por LBA ... En realidad es Primitive Recursive Complete, lo que significa que es incluso más difícil que PSPACE ... –

El artículo de Wikipedia para context-sensitive languages establece que cualquier lenguaje recursivo (es decir, reconocible por una máquina de Turing), cuya decisión es EXPSPACE -Hard no es sensible al contexto, y por lo tanto no puede ser reconocido por un LBA. Ellos dan un ejemplo de dicho lenguaje: el conjunto de pares de expresiones regulares equivalentes, incluida la exponenciación.

Fuente

2010-01-27 00:46:12

Estaba buscando problemas además de aceptar/rechazar lenguajes recursivos o recursivamente enumerables. – Bribles

@Bribles: es difícil proporcionar una respuesta autónoma bien respaldada a su pregunta sin hacer una especie de argumento de que el problema propuesto es (a) decidible, pero (b) no computable con un LBA. ¡Y reducir un problema computacional a un problema de decisión del lenguaje es la técnica de referencia para este tipo de argumento! –

Una pregunta relacionada es si la equivalencia de Turing para un lenguaje de programación o máquina abstracta es necesaria para el mundo real, o si la equivalencia de LBA sería suficiente. Me pregunto si hay algo útil en la diferencia entre un autómata lineal limitado y un autómata meramente finito. ¿Hay algo que un autómata limitado exponencialmente podría hacer que un lineal no puede importar a los no teóricos? – Bribles

¿Cuáles son los límites útiles de Autómatas limitados lineales en comparación con las Máquinas Turing?

Respuesta

Cuestiones relacionadas