Wednesday, March 31, 2010

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 (an) 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 (an). 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.


Anonymous said...

Given the timing: is there an April fool's joke embedded in there? For example do you actually really need 3 bases instead of 2?

FTFKDad said...

Reminds me that I was once lucky enough to attend a class at MIT led by Jay Forrester who was introduced as "one of the few profs who don't need a PhD to teach at MIT". He was also one of the founders of modern computer science and also founded the field of System Dynamics (I think I am right on both). Mr. Cobham also seems to exist on that plane above mere mortals.

Michael Lee said...

Alan Belmont Cobham Nov 24, 1927 - June 28, 2011. Alan passed away after a long illness.