Castor affairé

Carte Peu commune · n° 159723

Un castor affairé est, en théorie de la calculabilité, une machine de Turing qui maximise son « activité opérationnelle » (comme le nombre de pas effectués ou le nombre de symboles écrits avant son arrêt) parmi toutes les machines de Turing d'une certaine classe. Celles-ci doivent satisfaire certaines spécifications et doivent s'arrêter après être lancées sur un ruban vierge. Une fonction du castor affairé, ou fonction du nombre maximal de pas, quantifie cette activité maximale pour une machine de Turing à n états ; ce type de fonction n'est pas calculable. De plus, à partir d'un certain point, cette fonction croît plus rapidement que n'importe quelle fonction calculable. Déterminer le castor affairé parmi un ensemble de machines de Turing à n états donnés est un problème insoluble algorithmiquement ; en pratique, on ne peut même pas espérer exhiber un castor affairé pour un nombre n au-delà de 10. Le concept, introduit en 1962 par le mathématicien hongrois Tibor Radó, est l'un des premiers...

Lire sur Wikipédia