Loading AI tools
mathématicien américain De Wikipédia, l'encyclopédie libre
Alan Belmont Cobham, né le [1] à San Francisco en Californie, et mort le à Middletown au Connecticut[1],[2], est un mathématicien et informaticien théoricien américain. Il est connu[3] pour ses travaux conduisant à la définition de la classe de complexité P, et la thèse de Cobham, et à la définition et l'étude de ce qui est appelé maintenant les suites automatiques, écrits qui ont eu un impact prolongé.
Naissance | |
---|---|
Décès | |
Nationalité | |
Activités |
A travaillé pour |
---|
|
Entre 1940 et 1945, la famille d'Alan Cobham s'installe dans le Bronx, où Alan fréquent la Fieldston School (en). Il est ensuite élève au Oberlin College, puis étudie à l'Université de Chicago. Au début des années 1950, il travaille quelque temps au « Operations Evaluation Group » de l'United States Navy. Il étudie ensuite à Berkeley et au MIT, mais n'a jamais terminé un Ph. D. Il préfère aller travailler chez IBM[4]. Depuis le début des années 1960, et jusqu'en 1984, Cobham est chercheur au Thomas J. Watson Research Center de IBM à Yorktown Heights. C'est là qu'il produit les articles qui ont fait sa renommée.
Cobham a également réalisé chez IBM un programme de jeu de bridge qui était, à l'époque, l'un des meilleurs programmes de bridge au monde, et a été mentionné dans un article du New York Times du . À l'automne 1984, Cobham quitte IBM pour la direction du département d'informatique naissant de l'Université Wesleyenne à Middletown, dans le Connecticut, où il travaille jusqu'à sa retraite, le [2].
Cobham est renommé pour plusieurs travaux. D'une part, il était l'un des premiers chercheurs à considérer la classe de complexité P dans son article « The intrinsic computational difficulty of functions » de 1965, connu maintenant sous le titre de thèse de Cobham.
D'autre part, il s'intéresse aux ensembles d'entiers que l'on peut reconnaître par un automate fini à partir de leur écriture dans une base donnée. Dans son article « On the base-dependence of sets of numbers recognizable by finite automata » de 1969 il montre que si un même ensemble de nombres est reconnaissable en deux bases multiplicativement indépendantes[5], alors cet ensemble est composé de constante et de suites arithmétiques. Cet énoncé figure sous le nom de « théorème de Cobham » dans le livre d'Allouche et Shallit par exemple ou dans le traité d'Eilenberg qui donne sans preuve; il dit « The proof is correct, long, and hard. Il is a challenge to find a more reasonable proof of this fine theorem ». Depuis, de nombreuses études ont porté sur ce théorème. Un court aperçu est dans la présentation de Véronique Bruyère[6]. Une généralisation aux substitutions est donnée par Fabien Durand[7].
L'autre article sur le même sujet date de 1972 : « Uniform tag sequences ». Il a donné naissance à ce qu'on appelle maintenant des suites automatiques qui font l'objet du livre d'Allouche et Shallit. Comme dit Shallit[1] : « This paper has led to hundreds of others exploring the theory of automatic sequences and generalizing them. »
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.