La longue quête du castor affairé

Dans le périodique : La Recherche (Paris. 1970), n°582 (07/2025)
• • Pascal Michel
  • Tristan Stérin
  • Shawn Ligocki
• Pages : p.88-95
  • Langues : Français
• • Nature du document : documentaire
  • Résumé :

    Le point sur l'évolution des recherches basées sur le problème du "castor affairé" lié à la machine de Turing. Une infinité de programmes. Un nombre limité de combinaisons possibles d'états. Nécessité de trouver des machines de Turing à n états capables d'atteindre des records en termes de nombre d'étapes effectuées ou de cases marquées avec un 1 avant de s'arrêter. Obligation de prouver que la meilleure machine trouvée est effectivement la gagnante. Un algorithme pour éviter les doublons. Alliance des communautés mathématiques et informatiques pour accélérer les travaux permettant la mise en oeuvre d'assistants de preuve. Anthihydria, l'autre machine à six états. Encadré : "Seul l'effort collectif permettrait d'aboutir"

• • Descripteurs : algorithme / méthode de calcul