Chapitre 15 : Calculabilité, décidabilité.

1. Tout programme peut être une donnée:

Tout programme peut être vu comme une donnée :

• On peut le stocker dans un fichier.
• Un programme dans un langage informatique est soit un langage interprété, soit un langage compilable.
• Un système d'exploitation est un programme qui manipule d'autres programme.

Cette précision est là pour bien mettre en avant que de nos jours qu'un algorithme est programmable et n'est donc pas induit dans la conception de la machine elle même. On fait ainsi la différence, par exemple, entre une horloge mécanique et une montre programmée informatiquement.

2. Church-Turing

Dans les années 1930, les travaux des mathématiciens Alonso Church et Alan Turing ont permis d'éclaircir ce qu'est un programme basés sur des calculs.

3.Machine de Turing

Une machine de Turing est une machine conceptualisée par Alan Turing. C'est une machine imaginaire que l'on peut représenter ainsi:

• Cette machine dispose d'un ruban composé de symboles (par exemple de 0 ou 1) .
• Cette machine dispose d'une tête de lecture et d'écriture et elle dispose d'un état qui est précisé ( par exemple 0 ou 1).
• La tête de lecture peut se déplacer vers la gauche ou vers la droite.
• La machine dispose d'une table de transition. Elle contient les instructions suivants les états de la tête de lecture et ce qui est lu sur le ruban où se trouve la tête de lecture.

9. Thèse de Church-Turing

Tout traitement réalisable mécaniquement peut-être accompli par une machine de Turing.

10. La calculabilité en informatique

Définition

En informatique, la calculabilité étudie ce qu’un ordinateur peut ou ne peut pas résoudre à l’aide d’un programme.

Problème calculable

Un problème est dit calculable s’il existe un algorithme qui fournit une réponse correcte et qui termine pour toute entrée possible.

Problème non calculable

Un problème est dit non calculable lorsqu’aucun algorithme ne peut le résoudre dans tous les cas possibles.

Limites de l’informatique

La calculabilité ne dépend pas de la puissance de l’ordinateur, mais des limites théoriques de l’informatique.

13. La décidabilité en informatique

Définition

En informatique, un problème est dit décidable s’il existe un algorithme qui donne une réponse oui ou non pour toutes les entrées possibles, et qui se termine toujours.

Problème décidable

Un problème est décidable lorsqu’un algorithme permet de répondre correctement dans tous les cas, sans jamais boucler indéfiniment.

Problème indécidable

Un problème est indécidable lorsqu’aucun algorithme ne peut répondre correctement pour toutes les entrées tout en garantissant de toujours s’arrêter.

Lien avec la calculabilité

La décidabilité concerne des problèmes à réponse oui / non. Tout problème décidable est calculable, mais certains problèmes calculables ne sont pas décidable sous forme de question fermée.

Exemple célèbre

Le problème de l’arrêt consiste à savoir si un programme s’arrêtera ou non pour une entrée donnée. Ce problème est indécidable : aucun algorithme ne peut toujours donner la bonne réponse.

14. Le problème de l'arrêt

On peut se poser la question s'il est possible de savoir si un problème (un algorithme) s'arrêtera.

Est-il possible d'écrire un algorithme permettant de voir si n'importe quel autre algorithme s'arrête ou non?

Raisonnons par l'absurde :

Imaginons que ce programme que l'on appellera \(A\) existe.

Si on lui donne un programme \(P\) quelconque, alors \(A(P)=VRAI\) si le programme P s'arrête et \(A(P)=FAUX\) si le programme P ne s'arrête pas.

Regardons maintenant un programme \(B\) qui est définit de la manière suivante :

1. Il prend un programme \(P\) puis évalue \(A(P)\).
2. Si \(A(P)\) est \(VRAI\), il lance une boucle infinie.
3. Si \(A(P)\) est \(FAUX\), il s'arrête.

Regardons \(B(B)\)

• Si \(B(B)\) s'arrête , c'est que \(A(P)\) était \(FAUX\) et donc il ne s'arrêtait pas.
• Si \(B(B)\) ne s'arrête pas , c'est que \(A(P)\) était \(VRAI\) et donc qu'il s'arrêtait.

\(B\) ne peut pas exister donc A non plus.

15. Prouver la correction d’un algorithme

Qu’est-ce que la correction d’un algorithme ?

Un algorithme est dit correct s’il produit toujours le résultat attendu pour toutes les entrées valides.

Objectif d’une preuve de correction

Prouver la correction d’un algorithme consiste à montrer, de manière logique et rigoureuse, que l’algorithme fait exactement ce qui est demandé dans l’énoncé.

Deux aspects de la correction

• Correction partielle : si l’algorithme termine, alors le résultat est correct.
• Correction totale : l’algorithme termine et le résultat est correct.

Rôle des invariants

Pour les algorithmes utilisant des boucles, on utilise souvent un invariant de boucle.

Un invariant est une propriété qui est vraie :

• avant l’entrée dans la boucle,
• après chaque itération,
• à la fin de la boucle.

🛠 Méthode générale de preuve

• Décrire précisément ce que l’algorithme doit faire.
• Identifier les hypothèses sur les données d’entrée.
• Montrer que chaque étape respecte l’objectif.
• Conclure que le résultat final est correct.

Exemple simple

Algorithme : calculer la somme des éléments d’une liste.

somme = 0
pour chaque element de la liste :
    somme = somme + element

Invariant : après chaque itération, somme est égale à la somme des éléments déjà parcourus.

À la fin de la boucle, tous les éléments ont été parcourus, donc somme est bien la somme totale.

def maximum(liste):
    max_val = liste[0]
    for x in liste:
        if x > max_val:
            max_val = x
    return max_val
  

17. La terminaison d’un algorithme

Définition

Un algorithme est dit terminant s’il s’arrête après un nombre fini d’étapes, quelle que soit l’entrée fournie.

Pourquoi la terminaison est importante

Un algorithme qui ne termine pas ne donne jamais de résultat. La terminaison est donc une condition indispensable pour qu’un algorithme soit correct.

Causes fréquentes de non-termination

• une boucle dont la condition ne devient jamais fausse,
• une variable de boucle qui n’évolue pas correctement,
• une récursion sans condition d’arrêt.

Principe de preuve de terminaison

Pour prouver qu’un algorithme termine, on montre qu’à chaque étape une quantité diminue strictement et qu’elle ne peut pas diminuer indéfiniment.

Exemple simple

def compte_a_rebours(n):
    while n > 0:
        n = n - 1

Ici, la variable n est un nombre entier qui diminue strictement à chaque tour et ne peut pas devenir négative. La boucle termine donc forcément.

def mystere(n):
    while n != 1:
        if n % 2 == 0:
            n = n // 2
        else:
            n = n + 1
    return n