Aller au contenu

C14 Calculabilité, décidabilité

Activités

▪ Activité 1 : Programme comme donnée

De façon schématique, un programme (ou une fonction) prend en entrée des données, effectue un traitement sur ces données et produit un résultat :

graph LR
D["Données"]
P(["⚙ Programmes"])
R["Résultat"]
D --> P
P --> R

  1. Dans l'exemple d'une fonction qui compte le nombre de lettres dans un mot, que sont les données ? le résultat ?

  2. On souhaite écrire une fonction qui compte le nombre de lignes d'un fichier. Que sont les données de cette fonction ?

  3. Que sont les données pour les programme suivants : un antivirus, un compilateur ?

  4. Recopier et compléter avec les mots "programme" et "donnée" :

    un ........ prend des ....... en entrée mais, un ........ peut aussi être la ............ d'un .............

▪ Activité 2 : Problème de l'arrêt

On suppose qu'on dispose d'un programme appelé teste_arret qui prend en entrée un programme P et des données X et renvoie True ou  False selon que P s'arrête ou non avec les données X comme cela est schématisé ci-dessous :

graph LR
D["Programme P"]
X["Données X"]
P(["⚙ teste_arret"])
T["True"]
F["False"]
D --> P
X --> P
P --P s'arrête avec les données X--> T
P --P ne s'arrête pas avec les données X--> F

  1. On définit le nouveau programme suivant :

    1
2
3
4
5
6
    def Q(P,X):
    if teste_arret(P,X):
        while True:
            pass
    else:
        return 1
    1. Que dire des lignes 3 et 4 (on rappelle que l'instruction pass ne fait rien)
    2. Si P s'arrête avec les données X, que fait ce programme ?
    3. Si P ne s'arrête pas avec les données X, que fait ce programme ?

  2. Le programme Q prend en entrée un programme P et des données X, il peut donc se prendre lui-même en entrée avec lui-même comme donnée ! On cherche à déterminer le résultat de l'appel : Q(Q,Q). Pour cela, recopier et compléter le schéma suivant :

    graph LR
D["Programme : ..."]
X["Données : ..."]
P(["⚙ Programme Q"])
T["...."]
F["Arrêt"]
D --> P
X --> P
P --Q ...... avec Q comme donnée--> T
P --Q ne s'arrête pas avec Q comme donnée X--> F

  3. D'après ce schéma, que se passe-t-il si Q s'arrête avec lui même comme donnée ? Et dans le cas contraire ? Que peut-on en conclure sur l'existence du programme teste_arret ?

Note

On pourra compléter cette activité avec le visionnage de la vidéo suivante :

Dans cette activité, nous avons prouvé que le programme teste_arret ne peut pas exister, on dit que le problème de l'arrêt est indécidable c'est à dire qu'il n'existe pas d'algorithme permettant de résoudre ce problème.

Cours

Vous pouvez télécharger une copie au format pdf du diaporama de synthèse de cours présenté en classe :

Diaporama de cours

Attention

Ce diaporama ne vous donne que quelques points de repères lors de vos révisions. Il devrait être complété par la relecture attentive de vos propres notes de cours et par une révision approfondie des exercices.

Exercices

▪ Exercice 1 : Vocabulaire

  1. Donner un ou plusieurs exemples de programmes acceptant un programme comme donnée
  2. Donner un exemple de fonction calculable.
  3. Donner un exemple de problème indécidable.
  4. Que signifie la phrase "le problème de l'arrêt est indécidable" ?

▪ Exercice 2 : Nombre premier

  1. Proproser un algorithme permettant de savoir si un entier donné \(n\) est premier ou non. Que peut-on en déduire sur la décidabilité de ce problème ?
  2. Implémenter en Python cet algorithme.