# Alan Cobham (informaticien)

Alan Belmont Cobham, né le 4 novembre 1927 à San Francisco en Californie, et mort le 28 juin 2011 à Middletown au Connecticut$^,$, est un mathématicien et informaticien théoricien américain. Il est connu 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é.

## Biographie

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. 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 7 octobre 1984. À 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 30 juin 1988.

## Travaux

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, 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. Une généralisation aux substitutions est donnée par Fabien Durand.
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 : « This paper has led to hundreds of others exploring the theory of automatic sequences and generalizing them. »

## Publications
### Articles

* [1986] (en) Alan Cobham, « Stochastic automata with large state spaces and low rank », Linear Algebra and its Applications, vol. 75,‎ 1986, p. 57–66 (DOI 10.1016/0024-3795(86)90181-3, MR 0825399, lire en ligne).
* [1977] (en) Alan Cobham, « Representation of a word function as the sum of two functions », Mathematical Systems Theory, vol. 11, n$^o$ 1,‎ 1977, p. 373–377 (DOI 10.1007/BF01768487, MR 0484854)
* [1972] (en) Alan Cobham, « Uniform tag sequences », Mathematical Systems Theory, vol. 6, n$^{os}$ 1-2,‎ 1972, p. 164–192 (DOI 10.1007/BF01706087, MR 0457011).
* [1969] (en) Alan Cobham, « On the base-dependence of sets of numbers recognizable by finite automata », Mathematical Systems Theory, vol. 3, n$^o$ 2,‎ 1969, p. 186–192 (DOI 10.1007/BF01746527, MR 0250789) (Reviewer: J. Hartmanis)
* [1963] (en) Alan Cobham, « Some remarks concerning theories with recursively enumerable complements », The Journal of Symbolic Logic, vol. 28, n$^o$ 01,‎ 1963, p. 72–74 (DOI 10.2307/2271337, MR 173629, zbMATH 0124.25002) (Reviewer: P. Lorenzen)
* [1956] (en) Alan Cobham, « Reduction to a symmetric predicate », The Journal of Symbolic Logic, vol. 21, n$^o$ 01,‎ 1956, p. 56–59 (DOI 10.2307/2268487, MR 0078311) (Reviewer: P. Lorenzen)
* [1954] (en) Alan Cobham, « Priority Assignment in Waiting Line Problems », Journal of the Operations Research Society of America, vol. 2, n$^o$ 1,‎ 1954, p. 70–76 (DOI 10.1287/opre.2.1.70) - Correction Operations Research vol 3 n° 4 p. 547 (1955)

### Conférences

* [1968] (en) Alan Cobham, « On the Hartmanis-Stearns problem for a class of tag machines », 9th Annual Symposium on Switching and Automata Theory, IEEE Computer Society,‎ 1968, p. 51–60 (DOI 10.1109/SWAT.1968.20)
* [1968] (en) A. Cobham, « Functional equations for register machines », Proccedings of the Hawaii International Conference on System Sciences,‎ 1968, p. 10-13
* [1966] (en) Alan Cobham, « The recognition problem for the set of perfect squares », 7th Annual Symposium on Switching and Automata Theory, IEEE Computer Society,‎ 1966, p. 78–87 (DOI 10.1109/SWAT.1966.30)
* [1965] (en) Alan Cobham, « The intrinsic computational difficulty of functions », Studies in logic and the foundations of mathematics, North-Holland « Logic, Methodology and Philos. Sci. (Proc. 1964 Internat. Congr.) »,‎ 1964, p. 24–30 (MR 0207561, SUDOC 005411750) (Reviewer: J. R. Büchi)
* [1961] (en) A. Cobham, R. Fridshal et J. H. North, « An application of linear programming to the minimization of Boolean functions », 2nd Annual Symposium on Switching Circuit Theory and Logical Design, IEEE Computer Society,‎ 1961, p. 3–9 (DOI 10.1109/FOCS.1961.5)