Points clés et l'importance de Décidabilité

Question

Une langue est décidable Si un TM reconnaît la langue et passe dans un état Accepter ou refuser. En tant que dev. Je pense que cela est important car cela signifierait que nous pourrions déterminer si un programme contient Dépassements de tampon ou de blocage. En outre, les problèmes suivants sont Un-décidable:

• Est-ce qu'un programme jamais accès à une variable non initialisée.
• Faites deux grammaires contexte décrivent la même langauge.
• Est-il une différence si les paramètres à un sous-programme sont passés par référence ou par copie résultat

En termes de Décidabilité ce sont selon vous les points clés à Décidabilité et pourquoi il est important Décidabilité (en particulier à un développeur).

Note: Les points de balle sont très bien dans les réponses - je peux regarder moi-même les sujets. Je veux juste savoir quels sont les points principaux.

Answer 1

Peut-être appartient à la échange cstheory , mais je vais avoir un aller à toute façon.

Le point clé est: certains problèmes sont indécidables, à savoir ne pas résoluble par un algorithme, donc ils devraient être traités par d'autres méthodes. Parmi ces problèmes sont nombreux « méta-problèmes » concernant les langages informatiques, par exemple le problème de la détection d'un virus .

Après avoir déterminé qu'un problème est indécidable, il existe plusieurs possibilités d'action:

1. Certains problèmes peuvent être semi-décidable, à savoir il y a un Semi -algorithm qui permet de résoudre certains cas, mais les boucles pour toujours sur d'autres cas. Lors de la mise en œuvre d'un semi-algorithme, mettre une minuterie et no answer de retour lorsque le temps imparti.
2. Résoudre seulement quelques, parties du problème, espérons cruciales en la simplifiant.
3. 2 + demander à l'utilisateur d'entrée lorsque le problème devient trop complexe.
4. Utiliser une heuristique qui obtient la bonne réponse plus du temps.
5. Utiliser une autre langue, peut-être un complet non Turing.

1 à 3 sont populaires pour les outils de raisonnement automatisés, y compris les vérificateurs du programme. 4 est ce que les scanners de virus font. 5 est un bon choix en permettant aux utilisateurs de scripts d'écriture pour automatiser un plus grand système ; au lieu de les activer / Système / Lua / whatever complet, donnez-leur donnant un sous-ensemble restreint qui ne permet pas récursion / boucles sans bornes.

Answer 2

Supposons que vous devez écrire un logiciel qui satisfait à la condition:. « À l'exécution aucune fonction ne jamais finir par se faisant appeler directement ou indirectement »

Cette condition serait indécidable, mais une condition plus restrictive peut être décidable, par exemple quelque chose comme:. « Pas de pointeurs de fonction doivent être utilisées et aucune fonction contiennent des appels à lui-même, directement ou indirectement »

Il est de souligner que, parfois, il est possible de la flexibilité commerciale pour décidabilité, de sorte que certaines propriétés requises du système peut devenir exécutoire.

Si un langage de programmation est décidable, il sera toujours possible de décider si un programme est un programme valable pour cette langue ou non.

Mais même si un programme est un programme valide pour cette langue, il reste indécidable si ce programme peut encourir un dépassement de mémoire tampon ou une impasse.