Objectifs de la leçon
À l’issue de cette leçon, vous saurez décrire le principe de la machine de Turing, définir la notion d’algorithme et ses propriétés, distinguer algorithme et programme, et comprendre comment un ordinateur réel réalise des calculs à partir de ces concepts théoriques.
1. La machine de Turing (1936)
En 1936, le mathématicien britannique Alan Turing publie un article fondateur définissant une machine abstraite — la machine de Turing — pour répondre à la question philosophique : « Qu’est-ce qu’un calcul ? »
Description de la machine :
- Un ruban infini divisé en cases pouvant contenir des symboles (ex. 0, 1 ou blanc)
- Une tête de lecture/écriture qui peut lire le symbole courant, l’effacer, écrire un nouveau symbole, et se déplacer d’une case à gauche ou à droite
- Un état interne (la machine est dans un état parmi un ensemble fini d’états)
- Une table de transition (ou « programme ») : pour chaque combinaison (état actuel, symbole lu), elle spécifie le symbole à écrire, le déplacement (gauche/droite), et le nouvel état
La machine s’arrête quand elle atteint un état final. Le résultat du calcul est alors ce qui est écrit sur le ruban.
Importance théorique : Turing a démontré que tout algorithme (toute procédure de calcul mécanique) peut être réalisé par une telle machine. Il a aussi défini la machine de Turing universelle — une machine capable de simuler n’importe quelle autre machine de Turing, si on lui fournit la description de cette machine en entrée. C’est le concept théorique à l’origine de l’ordinateur à programme enregistré.
Le problème de l’arrêt
Turing a aussi démontré qu’il existe des problèmes insolubles algorithmiquement — notamment le « problème de l’arrêt » : il n’existe pas d’algorithme général permettant de déterminer si une machine de Turing s’arrêtera ou tournera indéfiniment pour un programme et une entrée donnés. C’est la première démonstration rigoureuse de l’existence de limites fondamentales au calcul.
2. La notion d’algorithme
Un algorithme est une suite finie et non ambiguë d’instructions permettant de résoudre un problème ou de réaliser une tâche. Il possède trois propriétés essentielles :
- Finitude : l’algorithme se termine toujours en un nombre fini d’étapes
- Non-ambiguïté : chaque instruction est définie de façon précise, sans interprétation possible
- Généralité : l’algorithme résout un problème pour toute instance valide (pas seulement un cas particulier)
Exemples d’algorithmes :
- Recette de cuisine : liste ordonnée d’instructions non ambiguës → analogie pédagogique, mais pas un vrai algorithme (ambiguïtés fréquentes !)
- Algorithme d’Euclide (PGCD) : un des plus anciens algorithmes formels connus (~300 av. J.-C.)
- Tri par sélection : pour trier une liste, trouver le minimum, le mettre en première position, répéter sur le reste
- Recherche dichotomique : trouver un élément dans une liste triée en coupant l’espace de recherche en deux à chaque étape
La notion de complexité algorithmique évalue les ressources (temps de calcul, mémoire) nécessaires à l’exécution d’un algorithme en fonction de la taille de l’entrée. Un algorithme en O(n) est linéaire ; un algorithme en O(n²) est quadratique (beaucoup plus lent pour les grandes entrées) ; un algorithme en O(2ⁿ) est exponentiel (impraticable pour les grandes entrées).
3. De l’algorithme au programme
Un programme est la traduction d’un algorithme dans un langage de programmation — un langage formel compréhensible par un ordinateur. Les langages de programmation peuvent être :
- Bas niveau : proche du langage machine (assembleur) — difficile à écrire, mais efficace
- Haut niveau : plus proches du langage humain (Python, Java, C++) — plus lisibles, traduits en langage machine par un compilateur ou un interpréteur
Un programme, une fois écrit, est compilé ou interprété pour produire une suite d’instructions en langage binaire (0 et 1) exécutable par le processeur.
4. L’ordinateur : architecture de Von Neumann
L’ordinateur moderne repose sur l’architecture de Von Neumann (1945), qui comporte :
- Unité centrale de traitement (CPU) : effectue les opérations arithmétiques et logiques ; contient l’unité arithmétique et logique (ALU) et l’unité de contrôle
- Mémoire vive (RAM) : stocke temporairement les données et les instructions en cours d’exécution
- Bus de données : transfère les informations entre CPU et mémoire
- Entrées/sorties : clavier, écran, disque, réseau
- Programme enregistré : le programme est stocké dans la même mémoire que les données (innovation majeure de Von Neumann, inspirée de la machine universelle de Turing)
Le CPU exécute des instructions élémentaires (addition, comparaison, lecture/écriture en mémoire) à une cadence de plusieurs milliards par seconde (fréquence en GHz). La puissance de calcul des processeurs modernes a été multipliée par ~10⁶ depuis les années 1970 — illustrant la loi de Moore (doublement du nombre de transistors sur une puce tous les ~2 ans).
Points clés à retenir
- Machine de Turing (1936) : modèle abstrait du calcul — ruban + tête + états + table de transition
- Machine universelle = ordinateur théorique pouvant simuler tout algorithme
- Algorithme : suite finie, non ambiguë, générale d’instructions
- Programme = algorithme traduit en langage de programmation
- Architecture Von Neumann : CPU + RAM + bus + E/S + programme enregistré
Mémo express
Turing → machine abstraite → fonde la théorie du calcul (1936)
Algorithme → fini + non ambigu + général
Programme → algorithme en langage de programmation
Von Neumann → CPU + RAM + programme enregistré = ordinateur moderne
Questions fréquentes
Pourquoi une machine aussi simple que la machine de Turing peut-elle modéliser tout calcul possible ?
La puissance de la machine de Turing vient de la combinaison de trois éléments : une mémoire potentiellement infinie (le ruban), la capacité de lecture/écriture à n’importe quelle position, et une logique de transition qui peut être aussi complexe qu’on le souhaite. Turing a prouvé que ces mécanismes simples suffisent à simuler n’importe quel calcul mécanique — c’est la thèse de Church-Turing. En pratique, les ordinateurs réels ont des mémoires finies, mais les processus qui s’exécutent en un temps fini sur des données finies entrent dans le cadre de la machine de Turing finie.
Qu’est-ce que la complexité algorithmique O(n) et pourquoi est-ce important en pratique ?
La notation O(n) décrit comment le temps de calcul (ou la mémoire) croît avec la taille n de l’entrée. O(n) signifie croissance linéaire (doubler n double le temps) ; O(n²) signifie croissance quadratique (doubler n multiplie le temps par 4) ; O(2ⁿ) signifie croissance exponentielle (ajouter 1 à n double le temps). En pratique : un algorithme O(n²) pour trier 10 éléments prend un millième du temps d’un algorithme O(2ⁿ), mais pour 100 éléments, l’écart devient gigantesque. Choisir le bon algorithme peut faire la différence entre un calcul faisable en 1 seconde et un calcul qui prendrait des millions d’années.
La loi de Moore est-elle encore valide aujourd’hui ?
La loi de Moore (Gordon Moore, 1965) prévoyait un doublement du nombre de transistors par puce tous les 18-24 mois. Elle a remarquablement bien tenu jusqu’aux années 2010. Depuis, la progression ralentit car on approche des limites physiques de la miniaturisation — les transistors font maintenant 2-3 nm, soit quelques dizaines d’atomes. Les industriels compensent en augmentant le nombre de cœurs (processeurs multi-cœurs), en utilisant des architectures spécialisées (GPU pour l’IA, processeurs neuromorphiques), et en explorant l’informatique quantique. La loi de Moore au sens strict est considérée comme terminée ou très ralentie, mais la puissance de calcul continue d’augmenter par d’autres voies.
Quelle est la différence entre un langage compilé (C++) et un langage interprété (Python) ?
Un langage compilé (C, C++, Rust) est intégralement traduit en code machine avant l’exécution par un compilateur. L’exécution est rapide car le processeur exécute directement le code binaire optimisé. Un langage interprété (Python, JavaScript dans un navigateur) est traduit instruction par instruction à l’exécution par un interpréteur. Plus flexible et plus facile à déboguer, mais plus lent. Python est 10 à 100 fois plus lent que C++ pour les calculs intensifs, mais les bibliothèques numériques (NumPy, TensorFlow) appellent en dessous du Python du code compilé en C/C++ — d’où sa popularité malgré sa lenteur native.
Qu’est-ce que le problème de l’arrêt et pourquoi est-il important ?
Le problème de l’arrêt demande : étant donné un programme et une entrée, peut-on toujours savoir si le programme va s’arrêter ou tourner indéfiniment ? Turing a prouvé en 1936 que la réponse est non : il n’existe pas d’algorithme général capable de résoudre ce problème pour tous les programmes et toutes les entrées. La preuve utilise un raisonnement par l’absurde (diagonalisation). L’importance philosophique : il existe des problèmes bien définis qui ne sont pas solubles algorithmiquement — l’ordinateur a des limites fondamentales, pas seulement pratiques. En informatique, de nombreux problèmes (vérification formelle, analyse de virus) se ramènent au problème de l’arrêt et sont donc indécidables.
Pour aller plus loin
Contenu rédigé pour Terminale — Enseignement Scientifique · reussir-svt.com
Sources : Turing (1936), « On Computable Numbers » ; Sipser, Introduction to the Theory of Computation (2012) ; Von Neumann (1945), rapport EDVAC ; Programme officiel ES Terminale (BO 2020).