Combien d’étapes de calcul au maximum peut exécuter une machine de Turing utilisant 5 règles ? Cette question échappait aux spécialistes depuis plus de soixante ans. Elle vient enfin d’être résolue, au terme d’un remarquable travail collaboratif faisant appel aux assistants de preuves informatiques.
Combien y a-t-il de façons de découper un rectangle en deux pièces superposables ? Cette question en apparence simple conduit à d’intéressants raisonnements combinatoires.
Au-delà des systèmes décimal et binaire, il existe des façon plus atypiques de représenter les nombres entiers. De la numération de Zeckendorf au code de Gros-Gray en passant par le ternaire équilibré, petit aperçu de ces systèmes de numération exotiques innovants.
Le jeu de carte de la bataille française recèle des subtilités mathématiques insoupçonnées. En particulier, savoir s’il existe ou non des parties infinies en fonction de la stratégie des joueurs se révèle étonnamment difficile.
Une étude prouve que l’on peut simuler tout algorithme avec des feuilles de papier judicieusement pliées ! Ces « ordinateurs origami » offrent un éclairage inédit sur la théorie du calcul.
La découverte d’un nouvel algorithme de comptage, reposant sur des principes élémentaires mais pourtant passé inaperçu jusqu’à récemment, étonne les spécialistes.
Qu’est-ce que l’infini ? Au fil de l’histoire, les mathématiciens se sont attachés à donner un sens précis à ce concept. Entretien avec le mathématicien Jean-Paul Delahaye, professeur émérite à l’université de Lille.
De « l’échiquier mutilé » aux assemblages exotiques de petits carrés, la question des formes « dominables » est levée petit à petit, non sans difficultés.
De récents travaux reprennent et affinent les raisonnements du philosophe suédois Nick Bostrom qui, il y a vingt ans, estimait probable que notre réalité soit en fait une simulation informatique menée par une civilisation avancée.
Connexion
Pour la Science
