Une machine à registres est un modèle théorique de calcul conçu pour ressembler d’assez près à la manière dont fonctionne un ordinateur réel. On l’imagine comme un dispositif disposant d’un certain nombre de cases numérotées, appelées registres, dont chacune peut contenir un nombre entier aussi grand qu’on veut. La machine exécute un programme composé d’instructions très simples: ajouter un à un registre, retirer un à un registre, ou tester si un registre vaut zéro et sauter en conséquence à une autre instruction. À partir de ces opérations rudimentaires portant directement sur des nombres rangés en mémoire, on parvient à programmer n’importe quel calcul. Ce modèle capture donc lui aussi l’idée de calculable, mais avec un vocabulaire proche de celui de la programmation ordinaire plutôt que celui d’un ruban parcouru case par case.
Ce type de machine a été formalisé au début des années 1960, notamment par les logiciens Marvin Minsky, ainsi que Shepherdson et Sturgis, à une époque où les ordinateurs existaient déjà réellement. L’intention était de proposer un modèle théorique plus intuitif et plus proche des machines concrètes que la machine de Turing imaginée trente ans plus tôt, tout en conservant la même rigueur. Le résultat attendu fut au rendez-vous: les machines à registres calculent exactement les mêmes fonctions que les machines de Turing, les fonctions récursives et le lambda-calcul. Une fois de plus, un modèle bâti sur des principes différents rejoignait précisément la même frontière du calculable, confortant la thèse de Church-Turing selon laquelle cette notion ne dépend pas de la formalisation choisie.
L’intérêt des machines à registres est surtout pédagogique et conceptuel. Parce qu’elles manipulent des nombres dans une mémoire adressable et enchaînent des instructions à la manière d’un vrai programme, elles servent de pont entre la théorie abstraite du calcul et le fonctionnement effectif d’un processeur, qui repose lui aussi sur des registres et des instructions élémentaires. Elles offrent ainsi un modèle commode pour raisonner sur ce qu’un ordinateur peut faire sans se perdre dans la mécanique du ruban, et illustrent de façon frappante que des architectures en apparence très éloignées possèdent en réalité exactement la même puissance de calcul.
Laisser un commentaire