La plus petite machine de Turing universelle

jeudi 17 avril 2008

http://www.bulletins-electroniques.com/actualites/54018.htm
Alex Smith, un étudiant âgé seulement de 20 ans, de l'Université de Birmingham a remporté le prix Wolfram 2,3 Turing Machine Research de 25.000 $. Ce prix a été créé en mai 2007 par Stephen Wolfram. Dans son livre "A New Kind of Science", celui-ci déclare que la machine de Turing est le système le plus simple qui puisse fonctionner comme un ordinateur universel. Cette "machine" est en fait un modèle de calcul abstrait, inventé par Alan Turing en 1936. Ce modèle est très largement utilisé en informatique théorique afin de résoudre les problèmes de complexité algorithmique et de calculabilité. Une machine de Turing universelle peut calculer et analyser toutes les fonctions récursives.

Le prix a été mis en place afin de récompenser toute personne qui prouvera que la machine de Turing d'une taille de 2*3 (2 états, 3 symboles) que Stephen Wolfram propose est universelle ou qu'elle ne l'est pas. A peine six mois après le lancement du prix, le jury constitué notamment par Stephen Wolfram a unanimement décerné le prix à Alex Smith. Dans un premier temps, Alex Smith pensait que cette dernière ne pouvait pas être universelle. Puis il a découvert qu'il y avait un moyen de prouver que cette machine était universelle. Il expose sa démonstration dans un document d'une cinquantaine de pages. Il a construit une séquence de règles qui montrent que la machine de Turing est capable d'effectuer des calculs définis d'une manière arbitraire. Cet étudiant de 20 ans connait plus de 20 langages de programmation, dont 6 qu'il décrit comme ésotériques.

Alan Mathison Turing (1912-1953)

Mathématicien britannique considéré comme le père fondateur de l'informatique moderne. Il est à l'origine de la formalisation des concepts d'algorithme et de calculabilité notamment grâce à la machine de Turing qu'il a inventé en 1936.

La machine de Turing en pratique

Il s'agit d'un simple système de bande divisé en cases. Chacune des cases contient un symbole d'un alphabet connu. Très souvent cet alphabet se résume à des 0 ou des 1 pour réaliser des traitements binaires.

En plus de la bande, ce système est composé de :

- une tête de lecture/écriture ;

- un registre d'états qui permet de mémoriser l'état en cours de la machine ;

- une table d'actions qui précise les interventions que la tête doit réaliser.

BE Royaume-Uni numéro 85 (17/04/2008) - Ambassade de France au Royaume-Uni / ADIT - http://www.bulletins-electroniques.com/actualites/54018.htm