Alan Turing : La Machine Universelle et l'Indécidabilité
En 1936, Alan Turing publie un article fondateur qui définit les bases de l'informatique moderne. En inventant un modèle de calcul universel, il démontre qu'il existe une limite mathématique à ce que les machines peuvent résoudre : c'est le problème de l'arrêt.
Alan Mathison Turing
23 June 1912 - 7 June 1954 (à 41 ans) - England
Sommaire du cours
1. Alan Turing : Un destin hors du commun
Le destin tragique d'Alan Turing
Malgré ses services héroïques durant la guerre, Alan Turing fut condamné en 1952 pour son homosexualité. Soumis à une castration chimique forcée, il meurt deux ans plus tard, à seulement 41 ans, par empoisonnement au cyanure.
"Nous ne pouvons voir qu'à une courte distance devant nous, mais nous pouvons voir que beaucoup reste à faire." — Alan Turing
2. La Machine de Turing : Le modèle de calcul
Pour Turing, calculer revient à manipuler des symboles selon des règles strictes. Sa machine est un automate composé de trois éléments fondamentaux :
- Le Ruban : Une mémoire infinie découpée en cases contenant des symboles \( \{0, 1, \beta\} \) (où \( \beta \) est le symbole vide).
- La Tête de lecture/écriture : Elle lit le symbole, le modifie et se déplace vers la Gauche (L) ou la Droite (R).
- Le Registre d'état : Il mémorise la situation actuelle de la machine (ex: \( q_0, q_1, \dots, q_{accept} \)).
3. Exemple : La machine "Inverseur" (États A et B)
Considérons une machine dont le but est de parcourir un ruban et de transformer chaque \( 0 \) en \( 1 \). Elle s'arrête dès qu'elle rencontre une case vide \( \beta \).
Table de transition simplifiée
| État actuel | Symbole lu | Action : Écrire | Action : Déplacer | Nouvel État |
|---|---|---|---|---|
| État A (Calcul) | \( 0 \) | \( 1 \) | Droite (R) | État A |
| État A (Calcul) | \( 1 \) | \( 1 \) | Droite (R) | État A |
| État A (Calcul) | \( \beta \) (Vide) | \( \beta \) | Stop (S) | État B (Arrêt) |
Un Autre exemple de machine de Turing
4. Lexique et Définitions
| Concept | Définition du programme NSI |
|---|---|
| Machine de Turing (MT) | Modèle abstrait d'un appareil de calcul mécanique composé d'un ruban, d'une tête de lecture et d'une unité de contrôle. |
| Algorithme | Un algorithme est la table de transition d'une machine de Turing. |
| Calculabilité | Un problème est calculable s'il existe une machine de Turing déterministe qui le résout. |
| MT Universelle | Machine capable de simuler n'importe quelle autre machine de Turing en lisant sa description. |
| Problème de décision | Problème fermé dont la réponse est binaire : Oui ou Non. |
| Décidabilité | Un problème est décidable s'il existe un algorithme qui répond en un nombre fini d'étapes. Sinon, il est indécidable. |
| Équivalence | La notion de décidabilité et celle de calculabilité sont semblables. |
5. Le Problème de l'Arrêt : Démystifier le Paradoxe
C'est le cœur de la découverte de Turing. Pour prouver qu'un problème est indécidable (qu'aucun algorithme ne peut le résoudre), il utilise un raisonnement par l'absurde. Pour le rendre concret, nous allons utiliser du code Python.
A. L'Hypothèse de départ : La fonction magique \(H\)
Imaginons qu'un programmeur de génie ait réussi à écrire une fonction Python parfaite, nommée test_arret(programme, entree). Sa spécification est simple :
- Elle analyse le code source de n'importe quel
programme. - Elle regarde ce que ce programme fait avec une
entreedonnée. - Elle répond **"S'arrête"** ou **"Boucle"**. Elle ne se trompe JAMAIS.
B. La construction du "Saboteur"
Pour piéger cette fonction magique, nous construisons un programme paradoxal. Appelons-le le Saboteur. Sa mission est simple : utiliser la prédiction de test_arret pour faire exactement le contraire.
Voici son code source simulé en Python :
# --- LE PROGRAMME SABOTEUR --- def saboteur(programme): # ÉTAPE 1 : Le Saboteur utilise la fonction magique # pour prédire ce qu'il ferait s'il s'analysait lui-même. prediction = test_arret(programme, programme) # ÉTAPE 2 : Il agit à l'opposé de la prédiction. if prediction == "S'arrête": # Si la fonction dit : "Il va s'arrêter"... # ...le Saboteur force une boucle infinie ! while True: pass else: # Si la fonction dit : "Il va boucler"... # ...le Saboteur s'arrête immédiatement. return "Fin"
C. Le Bug Logique : saboteur(saboteur)
Le moment critique arrive quand on demande à la fonction magique d'analyser le programme saboteur en lui donnant son propre code comme entrée. C'est l'auto-analyse :
Que fait l'exécution de \( saboteur(saboteur) \) ?
Il n'y a que deux cas possibles pour la réponse de la fonction magique \(H\) (test_arret) :
- Cas 1 : Si \(H\) répond "S'arrête"
Le code du Saboteur entre dans le blocif. Le programme se met à **boucler à l'infini**.
⮕ CONTRADICTION : La fonction avait prédit qu'il s'arrêterait, mais il boucle. - Cas 2 : Si \(H\) répond "Boucle"
Le code du Saboteur saute au blocelse. Le programme **s'arrête** immédiatement.
⮕ CONTRADICTION : La fonction avait prédit qu'il bouclerait, mais il s'arrête.
D. Conclusion Mathématique
Puisque peu importe la réponse de la fonction test_arret, elle finit par se contredire elle-même face au Saboteur, c'est que notre hypothèse de départ est fausse.
La fonction magique test_arret ne peut pas exister.
Sources et Références NSI
- Support de cours : Machine de Turing (Diaporama Math93).
- Archive Historique : A. Turing, "On Computable Numbers" (1936).
- Vidéo : Le problème de l'arrêt (ScienceÉtonnante).
Cours de Spécialité NSI - Terminale - Mis à jour en 2026
