ribbon

2006.05.14

Douglas Edric Stanley

cf. Machine de Turing

Dans les sciences de l'informatique, une machine abstraite est un modèle théorique décrivant le fonctionnement d'un ensemble de procédés de traitement algorithmiques. C'est le schema d'un ordinateur tel qu'il devrait fonctionner, si on devait le construire. En anglais on la nomme également "abstract computer" (ordainteur abstrait) pour souligner cet aspect pragmatique de la machine abstraite : elle décrit une machine fonctionnelle, mais dont on n'a pas besoin d'instance physique pour l'étudier. Une machine abstraite -- toujours selon la définition informatique -- peut décrire une machine existante ou une machine totalement irréalisable; quelque soit son existance materielle eventuelle, la machine abstraite reste le modèle d'un tel ordinateur, à ne pas confondre avec l'ordinateur physiquement conçu, même s'il est conçu à partir d'une machine abstraite.

La machine de Turing

La plus célèbre des machines abstraites est également une des premières machines dans l'histoire à être appelé une "machine abstraite". Il s'agit de la "machine universelle" d'Alan Turing, décrite en 1936 dans un texte appellé "On Computable Numbers, With an Application to the Entscheidungsproblem". Ce texte n'est pas à confondre avec le célèbre texte de 1950, "Computing Machinery and Intelligence" où Turing propose l'idée d'une intelligence machinique comparable à celle de l'homme. Dans le texte de 1936 Turing ne s'étale pas sur les conséquences de sa proposition, mais déssine simplement les traits d'une machine automatique, capable de déterminer la calculabilité (computability) de n'importe quelle proposition.

Ruban

La machine universelle de Turing suit quatre règles de construction:

  1. un ruban à 1-dimension qui s'étale à l'infini dans un sens et dans l'autre -- imaginez une bande de téléx déroulante, infinement longue, remplit de casiers les uns après les autres où on peut marquer des signes
  2. une tête de lecture qui peut lire et écrire dans seulement un des casiers à la fois
  3. le registre d'état (state register) qui se souvient de l'état actuelle de la machine
  4. une table des actions, qui décrit les actions à prendre selon le signe écrit sur le ruban à l'endroit de la tête de lecture.

Une finitude infinie

Ce qui est étonnant dans la Machine Universelle de Turing -- en dehors du fait que sa machine a été conçue avant l'informatique mais décrit encore aujourd'hui l'ensemble des machines informatiques actuelles -- c'est que sa machine dessine une infinité d'états possible à partir d'un ensemble d'états finis. On utilise des états concrets pour décrire un ensemble abstrait et variable. C'est-à-dire que la machine de Turing n'est pas seulement un modèle abstraite d'un fonctionnement hypothétique; il s'agit d'une des premières conceptions d'une machine conceptuelle variable mais qui pourrait être conçu avec des élements spatiales : des poulies, des rouages, voire avec des plantes, un peu d'eau et de la boue. Ce concept d'état finis (un signe, un autre, un autre...) gérant une infinitude de variations, est un des premières pas vers la manipulation de la logique avec des entités physiques, spatiales, ou dures. Le concept devient objet devient concept.