Detención en idiomas no completos de Turing

Question

El problema de detención no se puede resolver para los idiomas completos de Turing y se puede resolver trivialmente para algunos idiomas que no son TC como expresiones regulares donde siempre se detiene.

Me preguntaba si hay algún lenguaje que tenga la capacidad de detenerse y no detenerse, pero admite un algoritmo que puede determinar si se detiene.

Answer 1

Sí Una clase importante de este tipo son las funciones recursivas primitivas . Esta clase incluye todas las cosas básicas que espera poder hacer con los números (suma, multiplicación, etc.), así como algunas clases complejas como @adrian ha mencionado (expresiones regulares / autómatas finitos, gramáticas / pushdown sin contexto autómatas). Sin embargo, existen funciones que no son primitivas recursivas, como la función de Ackermann .

En realidad, es bastante fácil entender las funciones recursivas primitivas. Son las funciones que puede obtener en un lenguaje de programación que no tiene una 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 bucles while, en lugar de tener for-loops delimitados. Un bucle for acotado 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 ciclo for. El punto de dicho lenguaje de programación es que cada programa se detiene.

La mayoría de los programas que escribimos son en realidad primitivos recursivos (quiero decir, se pueden traducir a dicho lenguaje).

Answer 2

El problema de detención no actúa en los idiomas. Por el contrario, actúa en máquinas (es decir, programas): pregunta si un programa determinado se detiene en una entrada determinada.

Quizás quisiste preguntar si se puede resolver para otros modelos de cálculo (como expresiones regulares, que mencionas, pero también como autómata push-down ).

La detención se puede detectar, en general, en modelos con recursos finitos (como expresiones regulares o, de manera equivalente, autómatas finitos, que tienen un fijo número de estados y sin almacenamiento externo). Esto se logra fácilmente mediante enumerando todas las configuraciones posibles y verificando si la máquina entra la misma configuración dos veces (que indica un bucle infinito); con finito recursos, podemos poner un límite superior en la cantidad de tiempo antes de que debemos ver una configuración repetida si la máquina no se detiene.

Por lo general, los modelos con recursos infinitos (TM y PDA ilimitados, por ejemplo), no se puede 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 muy buen recurso para este tipo de pregunta.)

Answer 3

La respuesta corta es sí, y tales lenguajes pueden ser extremadamente útiles.

Hubo una discusión al respecto hace unos meses en LtU: http://lambda-the-ultimate.org/node/2846