theory - explained - halting problem explicacion
Detener en idiomas no completos de Turing (3)
El problema de detención no actúa en los idiomas. Más bien, actúa en máquinas (es decir, programas): pregunta si un programa dado se detiene en una entrada determinada.
Quizás quisiste preguntar si se puede resolver para otros modelos de computación (como expresiones regulares, que mencionas, pero también como autómatas push-down ).
La detención puede, en general, detectarse en modelos con recursos finitos (como expresiones regulares o, de manera equivalente, autómatas finitos, que tienen un número fijo de estados y ningún almacenamiento externo). Esto se logra fácilmente enumerando todas las configuraciones posibles y verificando si la máquina ingresa la misma configuración dos veces (lo que indica un ciclo infinito); con recursos finitos, podemos poner un límite superior en la cantidad de tiempo antes de que tengamos que ver una configuración repetida si la máquina no se detiene.
Por lo general, los modelos con recursos infinitos (TM ilimitadas y PDA, por ejemplo) no se pueden detener, pero sería mejor investigar los modelos y sus problemas abiertos individualmente.
(Perdón por todos los enlaces de Wikipedia, pero en realidad es un recurso muy bueno para este tipo de preguntas).
El problema de detención no se puede resolver para Turing idiomas completos y se puede resolver trivialmente para algunos lenguajes no TC como expresiones regulares donde siempre se detiene.
Me preguntaba si hay algún idioma que tenga la capacidad de detenerse y no detenerse, sino que admite un algoritmo que puede determinar si se detiene.
La respuesta corta es sí, y tales idiomas pueden ser extremadamente útiles.
Hubo una discusión al respecto hace unos meses en LtU: http://lambda-the-ultimate.org/node/2846
Sí. Una clase importante de este tipo son las funciones recursivas primitivas . Esta clase incluye todas las cosas básicas que esperas poder hacer con números (suma, multiplicación, etc.), así como algunas clases complejas como @adrian ha mencionado (expresiones regulares / autómatas finitos, gramáticas sin contexto / pushdown) autómata). Sin embargo, existen funciones que no son recursivas primitivas, como la función de Ackermann .
En realidad, es bastante fácil entender las funciones recursivas primitivas. Son las funciones que se pueden obtener en un lenguaje de programación que no tiene recursión verdadera (por lo que una función f no puede llamarse a sí misma, ya sea directamente o llamando a otra función g que luego llama a f, etc.) y no tiene ciclos while, en lugar de haber limitado for-loops. Un for-loop limitado es uno como "para i de 1 a r", donde r es una variable que ya se ha calculado anteriormente en el programa; Además, no puedo ser modificado dentro del for-loop. El objetivo de tal lenguaje de programación es que cada programa se detenga.
La mayoría de los programas que escribimos son realmente recursivos primitivos (es decir, pueden traducirse a dicho lenguaje).