cours/langage décidé.md

up:: langages formels, machine de turing sibling:: décidabilité #s/informatique

[!definition] langage décidé Un langage est dit décidé si il est langage accepté par une machine de Turing par une machine de turing ET que cette machine n'a aucune exécution infinie.

Cela garantit que :

• tout mot du langage représente une instance d'un problème de décision
• on peut toujours dire en un temps fini si la réponse au problème de décision modélisé est VRAI ou FAUX ^definition