turing
A propos de l'Espace-Turing | Partenaires | Nous contacter
twitter  facebook rss youtube
Accueil > Almanach > Historique > Naissance de « Tibor Radó » mathématicien hongrois qui a proposé l’un des (...)

Naissance de « Tibor Radó » mathématicien hongrois qui a proposé l’un des premiers exemples de fonction non calculable : le jeu du castor affairé

2 juin 1895 - 29 décembre 1965

Voir en ligne : https://fr.wikipedia.org/wiki/Tibor...
JPEG - 13.5 ko

Tibor Radó, né le 2 juin 1895 à Budapest et décédé le 29 décembre 1965 à New Smyrna Beach, est un mathématicien hongrois, émigré aux États-Unis après la Première Guerre mondiale.
Il a étudié entre 1913 et 1915 à l’université de Budapest. Pendant la Première Guerre mondiale, devenu premier lieutenant de l’armée hongroise, il fut capturé au Front de l’Est. Il s’échappa d’un goulag de Sibérie et, au bout de plusieurs milliers de kilomètres à travers le désert arctique, réussit à retourner en Hongrie.

Docteur de l’université de Szeged en 1923, il y enseigna brièvement puis devint chercheur à la Fondation Rockefeller en Allemagne. En 1929, il émigra aux États-Unis et donna des cours à l’université Harvard et à l’université Rice, avant d’obtenir un poste au département de mathématiques de l’Université d’État de l’Ohio en 1930. En 1935 il reçut la nationalité américaine.

Dans les années 1920, il démontra que les surfaces vérifient la Hauptvermutung (en), c’est-à-dire que leur triangulation est essentiellement unique.

Radó résolut le problème de Plateau en 1933 et publia en 1935 sur les fonctions sous-harmoniques.

Pendant la Seconde Guerre mondiale, il interrompit sa carrière universitaire pour être consultant scientifique du gouvernement américain.

Il devint directeur du département de mathématiques de l’Université d’État de l’Ohio en 1948.

Pendant ses dix dernières années, il concentra ses recherches sur l’informatique théorique et en mai 1962, il publia dans le Bell System Technical Journal l’un de ses résultats les plus connus, sur la fonction du castor affairé et sa non calculabilité.

Un castor affairé est, en théorie de la calculabilité, une machine de Turing qui atteint une « activité opérationnelle » maximale (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é quantifie cette activité maximale pour une machine de Turing à n états ; ce type de fonction n’est pas calculable. En fait, au bout d’un certain point, une fonction du castor affairé croît plus rapidement que n’importe quelle fonction calculable. Déterminer le castor affairé pour 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 le résoudre pour un nombre n au-delà de 10.


info portfolio

titre documents joints

Répondre à cet article


Suivre la vie du site RSS 2.0 | Plan du site | Espace privé | SPIP | squelette | Contact site : marc.monticelli [at] unice [point] fr