Conférence : une machine de Turing en légo

Conférencier : Aurélien Alvarez

Qu’est-ce qu’un calcul, qu’est-ce qu’un algorithme ?

En 1936, Alan Turing a apporté une réponse à ces questions en définissant ce que l’on appelle aujourd'hui une machine de Turing, c’est-à-dire un modèle mathématique abstrait qui donne un sens précis à la notion intuitive et ancestrale de calcul, et est particulièrement adapté sur le plan théorique pour aborder des questions de calculabilité et de complexité. Peut-on imaginer construire, uniquement avec des briques Lego, une « machine de Turing » bien réelle et « voir » ainsi un calcul ? C’est le challenge qui sera discuté dans cet exposé.