Une machine de Turing à deux états et trois couleurs est universelle

Nous apprend Pour la science.
Marvin Minsky (prix Turing) avait démontré qu'aucune machine à deux états et deux couleurs (on a un alphabet de seulement deux éléments) était universelle. Stephen Wolfram, celui qui a conçu Mathematica, a démontré l'existence d'une machine de Turing universelle à 2 états et 5 couleurs. Il a proposé en mai 2007 un prix de 25 000 dollars à qui prouverait la conjecture "Une machine de Turing à deux états et trois couleurs est universelle". Défi relevé quelques mois plus tard par un étudiant âgé de 20 ans : Alex Smith.