Aller au contenu

Exercices : Calculabilité et Décidabilité

Exercice 1 : Problèmes décidables ou non ?

Pour chaque problème ci-dessous, indiquez s'il est décidable ou indécidable. Justifiez votre réponse.

  1. Déterminer si un nombre entier est premier.

  2. Déterminer si une chaîne de caractères est un palindrome.

  3. Déterminer si un programme Python quelconque va s'arrêter.

  4. Déterminer si un nombre est divisible par 7.

  5. Déterminer si deux programmes Python produisent toujours le même résultat pour toutes les entrées possibles.

Exercice 2 : Écrire des prédicats

Un prédicat est une fonction qui renvoie un booléen. Écrivez en Python les prédicats suivants :

2.1 Prédicat est_puissance_de_2

def est_puissance_de_2(n):
    """
    Renvoie True si n est une puissance de 2, False sinon.
    Exemples : 1, 2, 4, 8, 16, 32... sont des puissances de 2.
    """
    # À compléter
    pass

2.2 Prédicat est_parfait

Un nombre parfait est un entier positif égal à la somme de ses diviseurs propres (diviseurs stricts, c'est-à-dire sans compter le nombre lui-même).

Exemple : 6 = 1 + 2 + 3 est parfait.

def est_parfait(n):
    """
    Renvoie True si n est un nombre parfait, False sinon.
    """
    # À compléter
    pass

2.3 Prédicat contient_doublon

def contient_doublon(liste):
    """
    Renvoie True si la liste contient au moins un élément en double.
    """
    # À compléter
    pass

Exercice 3 : Thèse de Church-Turing

3.1 Questions de cours

  1. Qui est Alonzo Church et quelle est sa contribution à l'informatique théorique ?

  2. Qu'affirme la thèse de Church-Turing ?

  3. Pourquoi parle-t-on de "thèse" et non de "théorème" ?

3.2 Réflexion

Si un algorithme fonctionne en Python, peut-il être traduit dans n'importe quel autre langage de programmation ? Justifiez en vous appuyant sur la thèse de Church-Turing.

Exercice 4 : Le problème de l'arrêt

4.1 Compréhension

Considérez le programme suivant :

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

  1. Testez ce programme avec les valeurs 6, 11, 27. Que constatez-vous ?

  2. Ce programme s'arrête-t-il toujours ? (Indice : c'est la conjecture de Syracuse, non résolue à ce jour !)

  3. En quoi cet exemple illustre-t-il le problème de l'arrêt ?

4.2 Démonstration par l'absurde

Expliquez avec vos propres mots pourquoi le problème de l'arrêt est indécidable. Utilisez le raisonnement par l'absurde vu en cours.

Exercice 5 : Machine de Turing

5.1 Addition binaire

Utilisez l'algorithme de la machine de Turing (activité TURING.md) pour calculer :

  1. 11₂ + 1 = ?
  2. 111₂ + 1 = ?
  3. 1111₂ + 1 = ?

5.2 Réflexion

Que remarquez-vous sur le nombre d'étapes nécessaires quand tous les bits sont à 1 ?

Exercice 6 : QCM de révision

Question 1

Un prédicat est une fonction qui : - [ ] A. Prend un booléen en paramètre - [ ] B. Renvoie un booléen - [ ] C. Ne s'arrête jamais - [ ] D. Est toujours récursive

Question 2

Le problème de l'arrêt est : - [ ] A. Décidable et calculable - [ ] B. Indécidable - [ ] C. Résolu par Alan Turing en 1936 - [ ] D. Un problème simple à résoudre

Question 3

Selon la thèse de Church-Turing : - [ ] A. Python est le meilleur langage de programmation - [ ] B. Tout ce qui est calculable peut l'être par une machine de Turing - [ ] C. Certains langages sont plus puissants que d'autres - [ ] D. Les ordinateurs quantiques peuvent tout calculer

Question 4

Un problème est dit décidable si : - [ ] A. On peut toujours trouver une solution - [ ] B. Il existe un algorithme qui répond oui ou non en temps fini - [ ] C. Il n'a pas de solution - [ ] D. Il nécessite un supercalculateur

Exercice 7 : Pour aller plus loin

Le paradoxe de Russell

Bertrand Russell a proposé le paradoxe suivant en 1901 :

« Dans un village, le barbier rase tous ceux qui ne se rasent pas eux-mêmes, et seulement ceux-là. Qui rase le barbier ? »

  1. Expliquez pourquoi ce paradoxe n'a pas de solution logique.

  2. En quoi ce paradoxe est-il similaire au problème de l'arrêt ?

  3. (Bonus) Recherchez le "paradoxe du menteur" et expliquez son lien avec l'indécidabilité.

Auteur : Florian Mathieu

Licence CC BY NC

Licence Creative Commons
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.