2
Lorsque vous prouvez qu'une langue est décidable, que faites-vous réellement?Quand vous prouvez qu'une langue est décidable, que faites-vous réellement?
A
Répondre
2
Si vous demandez COMMENT cela est fait, je ne suis pas sûr, mais je peux vérifier. Fondamentalement, decidable est le langage pour lequel on peut construire un algorithme (c'est-à-dire une machine de Turing) qui s'arrêtera pour toute entrée finie (en acceptant ou en rejetant l'entrée). Indécidable est le langage qui n'est pas décidable.
http://en.wikipedia.org/wiki/Recursive_language ... mais plus sur le sujet peut facilement être trouvé. Sur ce lien, il n'y a qu'une brève mention du terme.
p.s. Ainsi, en construisant l'algorithme mentionné ci-dessus, vous prouvez fondamentalement que le langage est décidable.