Wolfram Research et Stephen Wolfram annoncent aujourd’hui [14 mai] la constitution d’un prix de 25 000 $ pour celui ou ceux qui prouveront (ou réfuteront) qu’une machine de Turing particulièrement simple peut agir comme un ordinateur universel.

Comme chacun sait, une machine de Turing est une machine formelle comprenant une tête de lecture / écriture et un ruban marqué de divers symboles dans des cases distinctes qui défile dans la machine. Cette machine n’a “conscience” (le mot est de Turing) que du symbole qui est sous la tête de lecture / écriture. Cette machine a un nombre fini d’états ; chacun d’eux découle de l’état précédent et du symbole lu, suivant un nombre fini d’instructions. A chaque instant de son fonctionnement, suivant son état et ses instructions, la machine peut réécrire un symbole et faire défiler le ruban dans un sens ou dans l’autre d’un nombre de pas (de cases) variables. Une telle machine est universelle puisqu’elle peut accomplir, abstraitement, tous les calculs possibles.

Stephen Wolfram a déjà démontré dans A New Kind of Science qu’une machine ayant deux états et cinq symboles était une machine universelle. Ce prix a pour but d’établir si, oui ou non, une machine ayant seulement deux états et trois symboles est, elle aussi, universelle. Plus généralement, il s’agit de définir le degré minimal de complexité nécessaire au calcul opéré par une machine.

Source pour l’annonce du prix et le site de The Wolfram 2,3 Turing Machine Research Prize.