Arrêt dans des langues non-complètes à Turing

Question

Le problème d’arrêt ne peut pas être résolu pour les langages complets de Turing et il peut être résolu de manière triviale pour certains langages non-TC comme les expressions rationnelles où il s’arrête toujours.

Je me demandais s'il existe des langues capables à la fois de s'arrêter et de ne pas s'arrêter, tout en admettant un algorithme permettant de déterminer s'il s'arrête.

Answer 1

Oui. Les fonctions récursives primitives constituent une classe importante de ce type. Cette classe inclut toutes les tâches de base que vous vous attendez à pouvoir faire avec des nombres (addition, multiplication, etc.), ainsi que des classes complexes comme @adrian a mentionné (expressions régulières / automates finis, grammaires / contexte sans contexte automates). Toutefois, il existe des fonctions qui ne sont pas récursives primitives, telles que la fonction Ackermann .

Il est en fait assez facile de comprendre les fonctions récursives primitives. Ce sont les fonctions que vous pourriez obtenir dans un langage de programmation qui n'avait pas de vraie récursivité (donc une fonction f ne peut pas s'appeler elle-même, que ce soit directement ou en appelant une autre fonction g qui appelle ensuite f, etc.) et qui n'a pas de boucles while, au lieu d'avoir borné pour-boucles. Une boucle for liée est semblable à "pour i de 1 à r" où r est une variable qui a déjà été calculée plus tôt dans le programme; aussi, je ne peux pas être modifié dans la boucle for. L’intérêt d’un tel langage de programmation est que tous les programmes s’arrêtent.

La plupart des programmes que nous écrivons sont en réalité récursifs primitifs (je veux dire, ils peuvent être traduits dans un tel langage).

Answer 2

Le problème d'arrêt n'agit pas sur les langues. Au contraire, il agit sur des machines (programmes): il demande si un programme donné s’arrête sur une entrée donnée.

Peut-être que vous vouliez demander si cela peut être résolu pour d'autres modèles de calcul (comme les expressions régulières, que vous mentionnez, mais aussi comme automates déroulants ).

L’arrêt peut, en général, être détecté dans des modèles avec des ressources finies (comme expressions régulières ou, de manière équivalente, automates finis, qui ont une valeur fixe nombre d'états et pas de stockage externe). Ceci est facilement accompli par énumérer toutes les configurations possibles et vérifier si la machine entre la même configuration deux fois (indiquant une boucle infinie); avec fini ressources, nous pouvons mettre une limite supérieure sur la quantité de temps avant que nous devons voir une configuration répétée si la machine ne s’arrête pas.

Habituellement, les modèles avec des ressources infinies (TM et PDA non liés, par exemple), ne peut être stoppé-vérifié, mais il serait préférable d'examiner les modèles et leurs problèmes individuels individuellement.

(Désolé pour tous les liens Wikipedia, mais c’est une très bonne ressource pour ce genre de question.)

Answer 3

La réponse courte est oui, et de telles langues peuvent même être extrêmement utiles.

Il y a eu une discussion à ce sujet il y a quelques mois sur LtU: http://lambda-the-ultimate.org/node/2846