Castor affairé

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. En fait, à 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 exemples connus de fonction non calculable. Le terme « castor affairé » est la traduction littérale de l'expression anglaise « busy beaver », désignant familièrement une personne industrieuse et travailleuse. Le terme (et le concept) est introduit en 1962 par Tibor Radó sous le nom « busy beaver game » (« jeu du castor affairé ») dans son article de 1962 « On Non-Computable Functions » (« Sur des fonctions non calculables »). Le jeu du castor affairé à n états, introduit par Tibor Radó, utilise une classe de machines de Turing dont chaque membre répond aux spécifications suivantes : La machine possède n états plus un état spécial d'arrêt, où n est un nombre entier positif ; l'un des n états est défini comme l'état de départ. Ils sont typiquement nommés 1, 2, ..., n, 1 étant l'état de départ, ou A, B, C, ..., A étant l'état de départ. Elle utilise un ruban unique, s'étendant à l'infini à droite et à gauche. L'alphabet du ruban est {0, 1}, 0 servant de symbole vierge.