He leído en Wikipedia y algunos otros textos que
El problema de detención es [...] decidible para autómatas lineales (LBA) [y] máquinas deterministas con memoria finita.
Pero antes se escribe que el problema de detención es un problema indecidible y, por lo tanto, TM no puede resolverlo. Dado que LBA se define como un tipo de TM, ¿no debería ser lo mismo para ellos?
Respuestas:
El problema de detención se puede resolver para cualquier máquina de Turing que use una cantidad limitada de espacio conocida, mediante una generalización del argumento dado por Yonatan N. Si la cantidad de espacio es , el tamaño del alfabeto es A y el número de estados es Q , entonces el número de posibles configuraciones es Q S A S . Si la máquina se detiene, debe detenerse dentro de los pasos Q S A S , ya que, de lo contrario, según el principio del casillero, tiene una configuración repetida y, por lo tanto, está atrapada en un bucle infinito. Por lo tanto, para determinar si la máquina se detiene, simplemente la ejecutamos para Q S A SS UN Q Q SUNS Q SUNS Q SUNS pasos y ver si se detiene dentro de ese marco de tiempo.
fuente
Pareces atrapado con un problema lógico.
Por el hecho de que hay libros que no puedes leer, no puedes inferir que no puedes leer ningún libro.
Decir que el problema de detención es indecidible para Turing Machines (TM) solo significa que hay máquinas para las cuales no hay forma de determinar si se detienen o no mediante algún procedimiento uniforme que siempre se detendrá.
Sin embargo, hay máquinas de Turing que se detienen. Ahora tome un subconjunto de Máquinas de Turing, llamadas las Máquinas de Turing de Niza (NTM), de modo que solo contenga Máquinas de Turing que se detengan si y solo si la cinta contiene un número par de símbolos. Si se sabe que una máquina M es de ese conjunto, tiene una manera simple de decidir si M se detendrá: verificará si el número de símbolos de cinta es par (solo requiere dos dedos).
Pero ese procedimiento no funcionará para TM que no están en el conjunto NTM. (¡demasiado!)
Por lo tanto, el problema de detención es decidible para el NTM, pero no para el TM en general, a pesar de que el conjunto NTM está incluido en el conjunto TM.
Esto es realmente crítico, y a veces olvidado, al interpretar el resultado de indecidibilidad.
Es muy posible que se pueda demostrar que una propiedad importante es indecidible para una familia muy grande de objetos matemáticos o computacionales.
Esto no significa que deba dejar de buscar una solución, sino que no encontrará una para toda la familia.
Lo que puede hacer es identificar subfamilias relevantes para las cuales resolver el problema sigue siendo importante e intentar proporcionar algoritmos para decidir si la propiedad es válida para los miembros de esa familia más pequeña.
Por lo general, la detención es indecidible para TM en general, pero es decidible, a menudo de manera muy simple, para familias grandes y útiles de autómatas, que pueden considerarse como casos especiales de TM.
fuente
En resumen, A LBA tiene un número finito de configuraciones, digamos D. Por lo tanto, podemos ejecutar pasos D y concluir el resultado. Si se ejecuta por más de D pasos, por principio de casillero, podemos decir que está atrapado en un bucle infinito.
fuente