La longue quête du castor affairé / Pascal Michel in La Recherche (Paris. 1970), 582 (07/2025)

[article]  inLa Recherche (Paris. 1970) > 582 (07/2025) Titre : La longue quête du castor affairé Type de document : texte imprimé Auteurs : Pascal Michel ; Tristan Stérin ; Shawn Ligocki Année : 2025 Article : p.88-95 Langues : Français (fre) Descripteurs : algorithme / méthode de calcul 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" Nature du document : documentaire Genre : Article de périodique [article]  La longue quête du castor affairé de Pascal Michel, Tristan Stérin, Shawn Ligocki In La Recherche (Paris. 1970), 582 (07/2025), p.88-95 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"