Aller au contenu

TP : Le Barbier, le Menteur et la Machine — Paradoxes et Indécidabilité

Thème : Comprendre l'indécidabilité à travers les paradoxes logiques

Contexte

En 2026, les intelligences artificielles comme ChatGPT, Claude ou Gemini impressionnent par leurs capacités. Mais peuvent-elles tout calculer ? Peuvent-elles répondre à toutes les questions ?

Dans ce TP, vous allez découvrir que certaines questions n'ont pas de réponse calculable, et ce depuis bien avant l'invention des ordinateurs. Des mathématiciens comme Bertrand Russell, Kurt Gödel et Alan Turing ont prouvé qu'il existe des limites fondamentales à ce que les machines peuvent faire.

Partie 1 : Le Paradoxe du Menteur

L'énoncé

Considérez la phrase suivante :

« Cette phrase est fausse. »

Questions

  1. Si cette phrase est vraie, que peut-on en déduire ?

  2. Si cette phrase est fausse, que peut-on en déduire ?

  3. Pourquoi dit-on que c'est un paradoxe ?

Variante moderne : le tweet impossible

Imaginez un bot Twitter/X programmé ainsi :

SI le tweet dit "Ce tweet est faux" ALORS :
    SI le tweet est vrai → marquer comme faux
    SI le tweet est faux → marquer comme vrai

Que se passe-t-il quand le bot analyse le tweet « Ce tweet est faux » ?

Partie 2 : Le Paradoxe du Barbier

L'énoncé (Bertrand Russell, 1901)

Dans un village, il y a un barbier qui rase tous les hommes qui ne se rasent pas eux-mêmes, et seulement ceux-là.

Question : Le barbier se rase-t-il lui-même ?

Analyse

  1. Hypothèse 1 : Le barbier se rase lui-même.

  2. Que peut-on en déduire d'après la règle ?

  3. Hypothèse 2 : Le barbier ne se rase pas lui-même.

  4. Que peut-on en déduire d'après la règle ?

  5. Conclusion : pourquoi ce paradoxe n'a-t-il pas de solution ?

Application en informatique

Imaginez une fonction Python barbier(personne) qui renvoie True si le barbier rase cette personne :

def barbier(personne):
    """
    Renvoie True si le barbier rase cette personne.
    Règle : le barbier rase ceux qui ne se rasent pas eux-mêmes.
    """
    return not se_rase_soi_meme(personne)

Que renvoie barbier("barbier") si le barbier est une personne du village ?

Partie 3 : L'Ensemble de tous les ensembles

Le paradoxe de Russell (version mathématique)

Considérons l'ensemble R défini ainsi :

R = { tous les ensembles qui ne se contiennent pas eux-mêmes }

Question : R se contient-il lui-même ?

Analyse

  1. Si R ∈ R (R se contient), alors par définition de R, R ne devrait pas se contenir. Contradiction.

  2. Si R ∉ R (R ne se contient pas), alors par définition de R, R devrait se contenir. Contradiction.

Impact historique

Ce paradoxe a provoqué une crise des fondements des mathématiques au début du XXe siècle. Les mathématiciens ont dû repenser la notion même d'ensemble pour éviter ces contradictions.

Partie 4 : Du Paradoxe au Problème de l'Arrêt

Le lien avec l'informatique

Alan Turing a utilisé une structure similaire pour prouver que le problème de l'arrêt est indécidable.

Rappel du problème de l'arrêt

Existe-t-il un programme arret(P, x) qui, pour tout programme P et toute entrée x, répond : - True si P(x) s'arrête - False si P(x) boucle indéfiniment ?

La démonstration de Turing (simplifiée)

Étape 1 : Supposons qu'un tel programme arret existe.

Étape 2 : Construisons le programme paradoxe suivant :

def paradoxe(programme):
    if arret(programme, programme):
        # Si le programme s'arrête sur lui-même, on boucle
        while True:
            pass
    else:
        # Si le programme boucle sur lui-même, on s'arrête
        return True

Étape 3 : Que se passe-t-il si on appelle paradoxe(paradoxe) ?

Complétez le raisonnement :

  • Si arret(paradoxe, paradoxe) renvoie True → ...
  • Si arret(paradoxe, paradoxe) renvoie False → ...

Étape 4 : Conclusion

Quelle conclusion peut-on tirer sur l'existence de la fonction arret ?

Partie 5 : Simulation d'une Machine de Turing en Python

Objectif

Implémenter une machine de Turing simplifiée qui effectue l'addition de 1 à un nombre binaire.

Structure de la machine

class MachineDeTuring:
    def __init__(self, ruban_initial):
        """
        Initialise la machine avec un ruban.
        Le ruban est une liste de caractères ('0', '1', ou ' ' pour vide).
        """
        self.ruban = list(ruban_initial)
        self.position = 0  # Position de la tête de lecture
        self.etat = "chercher_fin"  # État initial

    def lire(self):
        """Lit le symbole sous la tête de lecture."""
        if 0 <= self.position < len(self.ruban):
            return self.ruban[self.position]
        return ' '  # Case vide

    def ecrire(self, symbole):
        """Écrit un symbole sous la tête de lecture."""
        # Étendre le ruban si nécessaire
        while self.position >= len(self.ruban):
            self.ruban.append(' ')
        while self.position < 0:
            self.ruban.insert(0, ' ')
            self.position += 1
        self.ruban[self.position] = symbole

    def gauche(self):
        """Déplace la tête vers la gauche."""
        self.position -= 1

    def droite(self):
        """Déplace la tête vers la droite."""
        self.position += 1

    def afficher(self):
        """Affiche l'état actuel du ruban."""
        ruban_str = ''.join(self.ruban)
        curseur = ' ' * self.position + 'V'
        print(f"État: {self.etat}")
        print(curseur)
        print(ruban_str)
        print()

Exercice : Implémenter l'algorithme d'addition

Complétez la méthode ajouter_un qui implémente l'algorithme d'addition de 1 :

def ajouter_un(self):
    """
    Ajoute 1 au nombre binaire sur le ruban.
    Algorithme :
    1. Aller à droite jusqu'à une case vide
    2. Revenir à gauche et appliquer la règle d'addition avec retenue
    """
    # Étape 1 : Aller à droite jusqu'à une case vide
    while self.lire() != ' ':
        self.droite()

    # Étape 2 : Revenir à gauche et ajouter 1
    self.gauche()

    # À compléter : implémenter la logique d'addition avec retenue
    # Tant qu'on a une retenue à propager...

    pass  # Remplacez par votre code

Test

# Créer une machine avec le nombre binaire 101 (= 5)
machine = MachineDeTuring("101")
machine.afficher()

# Ajouter 1
machine.ajouter_un()
machine.afficher()

# Résultat attendu : 110 (= 6)

Partie 6 : Réflexion finale

Questions de synthèse

  1. Lien entre les paradoxes : Quel point commun voyez-vous entre le paradoxe du menteur, le paradoxe du barbier et le problème de l'arrêt ?

  2. Auto-référence : Qu'est-ce que l'auto-référence ? Pourquoi pose-t-elle problème ?

  3. Limites des machines : Si le problème de l'arrêt est indécidable, cela signifie-t-il que les ordinateurs sont "stupides" ? Justifiez.

  4. IA et indécidabilité : Une intelligence artificielle, aussi avancée soit-elle, peut-elle résoudre le problème de l'arrêt ? Pourquoi ?

Débat : Les limites de l'IA

En 2026, les IA génératives sont partout. Mais elles sont soumises aux mêmes limites fondamentales que n'importe quel programme.

Discutez en groupe : - Une IA peut-elle savoir si elle va boucler indéfiniment sur une tâche ? - Une IA peut-elle vérifier qu'elle n'a pas de bugs ? - Quelles sont les implications pour la sécurité des systèmes autonomes ?

Résumé des notions

Concept Description
Paradoxe Situation logique contradictoire, sans solution
Auto-référence Quand un énoncé parle de lui-même
Problème de l'arrêt Peut-on décider si un programme s'arrête ? (Non !)
Indécidabilité Existence de problèmes sans algorithme de résolution
Machine de Turing Modèle théorique de calcul universel

Bonus : Le théorème d'incomplétude de Gödel

En 1931, Kurt Gödel a prouvé qu'en mathématiques, il existe des énoncés vrais mais indémontrables.

Plus précisément : dans tout système logique assez puissant pour exprimer l'arithmétique, il existe des propositions qui ne peuvent être ni prouvées, ni réfutées.

C'est une autre facette de l'indécidabilité : même les mathématiques ont leurs limites !

Recherchez et expliquez avec vos mots ce que signifie ce théorème.

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.