Alan Cobham

Alan Belmont Cobham (b. November 4 1927, San Francisco) is a mathematician and theoretical computer scientist. He was an undergraduate at Oberlin College and the University of Chicago, and later went on to do graduate work at both Berkeley and MIT, although he never got a Ph. D. He worked at IBM Yorktown Heights, and for a while was chair of the computer science department at Wesleyan University in Middletown, Connecticut. He still lives in Middletown. I recently had a chance to talk briefly with Alan Cobham at his home, and took the picture above.

He is known for several achievements. He was one of the first people to bring attention to the complexity class P, in a paper entitled "The intrinsic computational difficulty of functions", where he proposed studying the functions computable in polynomial time.

In 1969, he wrote the first of two papers on what are now called "automatic sequences" (he called them "uniform tag sequences"). An automatic sequence (a_n) is one in which the nth term can be calculated by expressing n in some base k, feeding it into a deterministic finite automaton, and then looking at the state reached at the end. An output function converts the state name into (a_n). In this paper Cobham proved a subtle and beautiful result: if a sequence is generated by two automata that accept inputs expressed in multiplicatively independent bases, then it is ultimately periodic. There is still no really simple proof of this result.

In 1972, he wrote a very influential paper entitled "Uniform tag sequences", where the theory of automatic sequences was developed in great detail. This paper has led to hundreds of others exploring the theory of automatic sequences and generalizing them.