wife but did some teaching at Erie
Community College. She taught English for a number of years.
How did you make the decision to at-
tend Michigan in 1957?
My parents were alumni and they
met there. Some other relatives also attended Michigan. My mother grew up
I take it you knew that the mathematics
and computer science programs were
strong at Michigan at that point?
Not especially. I knew that Michigan was generally good academically. I
was not thinking of computer science
when I went to Michigan. Computers
were pretty new then. This was 1957.
what were you thinking about doing
when you went to Michigan?
Engineering, actually. I enrolled
in the College of Engineering in Engineering Science, and I had quite
an interest in electronics. Clarence,
NY, is where we were living at the
time, and Clarence had, and still has,
a prominent citizen named Wilson
Greatbatch. Greatbatch was inducted
into the National Inventors Hall of
Fame for inventing the first implant-able artificial cardiac pacemaker.
[Greatbatch, who held more than 325
patents and was a recipient of the
Lemelson–MIT Prize, passed away
September 27, 2011. –Ed.] He was developing the electronics for it while
I was in high school so I learned and
worked with him, just helping him
solder up circuits. This was the early
days of transistors, so I got quite interested in electronics.
He recommended Michigan?
No, it was just my parent’s alma ma-
i think there was
a feeling that
there were certain
problems that just
seemed to be hard.
ter. My older brother had also gone to
I don’t know too many people who
were at Michigan at that time. did you
study with Bernie Galler?
Yes, absolutely. I took a course from
him my very first year. It was a one-hour
credit course in programming—that
was my introduction to programming.
He said you did very well. I took the
liberty of asking him about you. He
remembers you. were you learning
Not SNOBOL, but it was a Michigan product. I remember the Graham-Arden compiler. I can’t remember the
programming language. There was a
homegrown algebraic programming
was it Mad, the Michigan algorithmic
That sounds right. That might have
do you remember any of your other
mentors from those days?
At Michigan, the math guy was
Nicholas Kazarinoff. I was in engineering science and I took a calculus course
where I performed well and he noticed
me. That was really my best subject all
along. He encouraged me to jump into
a third-year course the second term and
so I took an accelerated mathematics
program. Eventually I transferred into
the Bachelor of Math and Science degree program after two and a half years,
and majored in mathematics.
was it difficult to make that adjustment?
Yes. It was clear that mathematics was my real area. Of course, I was
good in mathematics in high school,
but I didn’t know any mathematicians.
I didn’t really know what mathematicians did.
who made the recommendation that
you study at Harvard upon graduation?
That was one of the great mathematics departments. I applied at other
places too, like Princeton and Berkeley.
I don’t remember exactly why I ended
up at Harvard.
was alan cobham already at Harvard
at this time?
Well, no. Before I got there he was
a graduate student in the mathematics department and was close to getting his Ph.D. He wrote a thesis, but he
didn’t bother to complete the minor
thesis requirement. Instead, he just
went off to work for IBM Research in
did you have a major professor in mind
when you went to Harvard?
No, and I didn’t really know what I
wanted to do either. I put down algebra as my area. I got more interested
in computers when I took a course
with my eventual advisor, Hao Wang.
He wasn’t in the mathematics department; he was in applied physics.
what was your thesis topic?
We didn’t have a real master’s thesis. The master’s degree was something
you picked up, just course work really.
so it was just a stepping-stone?
In one of your lectures you talk about
cobham’s question, “Is multiplication harder than addition?” as being
inspirational to you. was that a turning
That was one thing. Yes, he wrote
this interesting paper on the intrinsic computational difficulty of functions, which I read. That was an influential paper for sure. There were
other things around too. Michael
Rabin was interested in the same
kind of problems and he had written
articles, and then there were other
papers. I think I mention them in my
Turing Award article.a
Right. were Princeton faculty and stu-
dents visiting Harvard in those days, or
were you going down to Princeton?
No, I never went to Princeton. James
Bennett’s thesis was quite influential,
but I never met him. In fact I think he
dropped out of the academic picture
as soon as he got his degree. I did meet
Bob Ritchie. I think he came up to visit,
I think that was the only Princeton connection I can remember.
But you were reading their papers?
a Cook, S.A. An overview of computational complexity. Commun. ACM 26, 6 (June 1983), 401–408.