Alan Belmont Cobham (4 November 1927 – 28 June 2011)[1] was an American mathematician and computer scientist known for (with Jack Edmonds and Michael O. Rabin) inventing the notion of polynomial time and the complexity class P,[2][B] for Cobham's thesis stating that the problems that have practically usable computer solutions are characterized by having polynomial time,[3][B] and for Cobham's theorem on the sets of numbers that can be recognized by finite automata.[4][C] He also did foundational work on automatic sequences,[5][D] invented priority queues and studied them from the point of view of queueing theory,[6][A] and wrote a program for playing contract bridge that was at the time (in the mid-1980s) one of the best in the world.[7]
Alan Belmont Cobham | |
|---|---|
| Born | November 4, 1927 |
| Died | June 28, 2011 (aged 83) |
| Nationality | American |
| Occupation | Theoretical computer scientist |
| Known for | Defining the class P, Cobham's thesis, Cobham's theorem, inventing priority queues, writing a program to play contract bridge |
Cobham was a student at Oberlin College, the University of Chicago, the University of California, Berkeley, and the Massachusetts Institute of Technology, but did not complete a doctorate. He became an operations researcher for the United States Navy, a researcher for IBM Research at the Thomas J. Watson Research Center, and a professor and founding department chair of the computer science department at Wesleyan University.[1]
Selected publications
edit| A. | Cobham, Alan (February 1954). "Priority assignment in waiting line problems". Journal of the Operations Research Society of America. 2 (1): 70–76. doi:10.1287/opre.2.1.70.
|
| B. | Cobham, Alan (1965). "The intrinsic computational difficulty of functions". In Bar-Hillel, Yehoshua (ed.). Logic, Methodology and Philosophy of Science: Proceedings of the 1964 International Congress. Studies in Logic and the Foundations of Mathematics. Amsterdam: North-Holland. pp. 24–30. MR 0207561.
|
| C. | Cobham, Alan (June 1969). "On the base-dependence of sets of numbers recognizable by finite automata". Mathematical Systems Theory. 3 (2): 186–192. doi:10.1007/BF01746527. MR 0250789. S2CID 19792434.
|
| D. | Cobham, Alan (March 1972). "Uniform tag sequences". Mathematical Systems Theory. 6 (1–2): 164–192. doi:10.1007/BF01706087. MR 0457011. S2CID 28356747.
|
References
edit- ^ a b Shallit, Jeffrey (March 31, 2010). "Alan Cobham". Recursivity. Shallit, Jeffrey (November 12, 2014). "Alan Cobham: An Appreciation". Recursivity.
- ^ Kozen, Dexter C. (2006). Theory of Computation. Springer. p. 4. ISBN 978-1-84628-297-3.
- ^ Ausiello, Giorgio (2018). The Making of a New Science: A Personal Journey Through the Early Years of Theoretical Computer Science. Springer. p. 43. ISBN 978-3-319-62680-2.
- ^ Durand, Fabien; Rigo, Michel (2010). "On Cobham's Theorem" (PDF). In Pin, J.-É. (ed.). Automata: from Mathematics to Applications. European Mathematical Society.
- ^ Rowland, Eric (March 2015). "What is...an automatic sequence?" (PDF). Notices of the American Mathematical Society. 62 (3): 274–276. doi:10.1090/noti1218.
- ^ Miller, Rupert G. Jr. (1960). "Priority queues". Annals of Mathematical Statistics. 31: 86–103. doi:10.1214/aoms/1177705990. MR 0120688.
- ^ Truscott, Alan (October 7, 1984). "Bridge: Playing against computers". The New York Times.
   | This article about an American mathematician is a stub. You can help Wikipedia by expanding it. |