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].
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[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. »
[1977] (en) Alan Cobham, « Representation of a word function as the sum of two functions », Mathematical Systems Theory, vol. 11, no 1, , p. 373–377 (DOI10.1007/BF01768487, MR0484854)
[1972] (en) Alan Cobham, « Uniform tag sequences », Mathematical Systems Theory, vol. 6, nos 1-2, , p. 164–192 (DOI10.1007/BF01706087, MR0457011).
[1969] (en) Alan Cobham, « On the base-dependence of sets of numbers recognizable by finite automata », Mathematical Systems Theory, vol. 3, no 2, , p. 186–192 (DOI10.1007/BF01746527, MR0250789) (Reviewer: J. Hartmanis)
[1963] (en) Alan Cobham, « Some remarks concerning theories with recursively enumerable complements », The Journal of Symbolic Logic, vol. 28, no 01, , p. 72–74 (DOI10.2307/2271337, MR173629, zbMATH0124.25002) (Reviewer: P. Lorenzen)
[1956] (en) Alan Cobham, « Reduction to a symmetric predicate », The Journal of Symbolic Logic, vol. 21, no 01, , p. 56–59 (DOI10.2307/2268487, MR0078311) (Reviewer: P. Lorenzen)
[1954] (en) Alan Cobham, « Priority Assignment in Waiting Line Problems », Journal of the Operations Research Society of America, vol. 2, no 1, , p. 70–76 (DOI10.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, , p. 51–60 (DOI10.1109/SWAT.1968.20)
[1968] (en) A. Cobham, « Functional equations for register machines », Proccedings of the Hawaii International Conference on System Sciences, , 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, , p. 78–87 (DOI10.1109/SWAT.1966.30)[8]
[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.) », , p. 24–30 (MR0207561, SUDOC005411750) (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, , p. 3–9 (DOI10.1109/FOCS.1961.5)
Jeffrey Shallit, « Alan Cobham », Recursivity, sur recursed.blogspot.fr, (consulté le ).
(en) Philip L. Frana, « An interview with Stephen A. Cook », Communications of the ACM, vol. 55, no 1, , p. 41 (DOI10.1145/2063176.2063193).
Véronique Bruyère, « Around Cobham's theorem and some of its extensions », Dynamical Aspects of Automata and Semigroup Theories, Satellite Workshop of Highlights of AutoMathA, (consulté le ) (présentation)
(en) Fabien Durand, « Cobham's theorem for substitutions », Journal of the European Mathematical Society, vol. 13, no 6, , p. 1797–1812 (DOI10.4171/JEMS/294, arXiv1010.4009, lire en ligne).
