Obituary: Professor Stephen Kleene

Stephen Cole Kleene, mathematician: born Hartford, Connecticut 5 January 1909; Research Assistant in Mathematics, Princeton University 1930-35; Instructor, University of Wisconsin 1935- 37, Assistant Professor 1937-41; Associate Professor, Amherst College 1941-42; Associate Professor, University of Wisconsin 1946-48, Professor 1948-64, Cyrus C. McDuffee Professor of Mathematics 1964-74, Dean, College of Letters and Science 1969-74, Professor of Mathematics and Computer Science 1974-79, Emeritus Dean and Emeritus Professor of Mathematics and Computer Science 1979-94; Member, National Academy of Science 1969-94; National Medal of Science 1990; married 1942 Nancy Elliot (died 1970; three sons, one daughter), 1978 Jeanne Steinmetz; died Madison, Wisconsin 25 January 1994.

STEPHEN KLEENE was one of that small group of brilliant researchers, including Alan Turing in Britain, who tried to remake mathematics in the 20th century, by intellectually mapping out the computable world and its boundaries. The physical development of the computer inevitably flowed from the theoretical framework which they provided.

Kleene was the first explorer of the mysterious world of the uncomputable. His extraordinary body of work has become basic to much of theoretical computer science, in which real-world considerations of computational power are incorporated. However, the question first raised by the early pioneers from the 1930s, that of the exact relationship between the solvable and unsolvable problems, has still to be fully answered. The answer promises to have significance far beyond the esoteric confines of contemporary mathematics.

Kleene's early research at Princeton between 1930 and 1935 took place in a period of great excitement following the discoveries of Kurt Godel. Godel's Incompleteness Theorem said that the comprehensiveness of any theory is limited in a very basic way. This had brought into question the earlier 'onward and upward' view of mathematics even more dramatically than Bertrand Russell's paradox in set theory had done 25 years earlier.

Stephen Kleene's father, Gustav Kleene, was a professor of economics, his mother, Alice, a published poet. He grew up in Hartford, Connecticut, spending his summers on a family farm in Maine. He took his doctorate under the eminent mathematician Alonzo Church in 1934, at the height of the Depression. He spent most of his distinguished career as a professor of mathematics at the University of Wisconsin at Madison, where he went in 1935. As many other aspiring logicians will have done, I read with excitement the ideas put forward in his famous book Introduction to Metamathematics, published in 1952, and still in print. He won the National Medal of Science in 1990, having been elected to the US National Academy of Sciences in 1969, a rare honour for a mathematician.

It is hard to give an adequate account of Kleene's work to the non- specialist, highly technical as much of it is. The subject of recursion theory which he founded (along with his New York co-worker Emily Post) is notorious for its ever-increasing complexity, and current workers in the field are often admired for their heroism of intellectual endeavour, but little understood even by their fellow mathematicians. But his interests in the foundations of computability were broad, and after his war service in the US Navy he applied his ideas within intuitionism, a radical and peculiarly European reconstruction of mathematics along constructivist lines. He produced a significant breakthrough in the theory of finite automata while working for the RAND Corporation in the summer of 1951.

Kleene will probably be best remembered for his work in classifying the world of the uncomputable. This involved two different approaches: first, the more traditional hierarchical framework, in which layers of ever less computable objects are built up according to the logical complexity of their descriptions, a process which was ingeniously iterated into the transfinite and extended to very general classes of objects; secondly, the 'degree theoretic' approach, in which the relative solvability (of essentially unsolvable problems) is assessed and given an algebraic structure, using the notion of an 'oracle' (a hypothetical provider of real- world inaccessible data). These two approaches were related in a beautiful and comprehensive fashion, enabling well-known unsolvable problems to be given a precise context relative to each other.

My vividest memory of Stephen Kleene is of a tall, still vigorous 70- year-old climbing the steep hillside at Delphi accompanied by his second wife Jeanne. All that week he had attended every talk at the 1980 Patras conference of the Association of Symbolic Logic, listening attentively to every one. Many youthful contributors will remember their first conference appearance with special pride because of his presence.

(Photograph omitted)

Start your day with The Independent, sign up for daily news emails
ebooks
ebooksAn introduction to the ground rules of British democracy
Latest stories from i100
Have you tried new the Independent Digital Edition apps?
SPONSORED FEATURES
Independent Dating
and  

By clicking 'Search' you
are agreeing to our
Terms of Use.

iJobs Job Widget
iJobs People

East15 Acting School: Finance and Contracts Officer

£20,781 to £24,057 per annum: East15 Acting School: The post involves general ...

Austen Lloyd: Practice / HR Manager - Somerset

Excellent Salary: Austen Lloyd: A rare and exciting opportunity for a Practice...

Recruitment Genius: Human Resources Manager

Negotiable: Recruitment Genius: This company provides global satellite communi...

Austen Lloyd: Practice / HR Manager - Somerset

Excellent Salary: Austen Lloyd: A rare and exciting opportunity for a Practice...

Day In a Page

Turkey-Kurdish conflict: Obama's deal with Ankara is a betrayal of Syrian Kurds and may not even weaken Isis

US betrayal of old ally brings limited reward

Since the accord, the Turks have only waged war on Kurds while no US bomber has used Incirlik airbase, says Patrick Cockburn
VIPs gather for opening of second Suez Canal - but doubts linger over security

'A gift from Egypt to the rest of the world'

VIPs gather for opening of second Suez Canal - but is it really needed?
Jeremy Corbyn dresses abysmally. That's a great thing because it's genuine

Jeremy Corbyn dresses abysmally. That's a great thing because it's genuine

Fashion editor, Alexander Fury, applauds a man who clearly has more important things on his mind
The male menopause and intimations of mortality

Aches, pains and an inkling of mortality

So the male menopause is real, they say, but what would the Victorians, 'old' at 30, think of that, asks DJ Taylor
Man Booker Prize 2015: Anna Smaill - How can I possibly be on the list with these writers I have idolised?

'How can I possibly be on the list with these writers I have idolised?'

Man Booker Prize nominee Anna Smaill on the rise of Kiwi lit
Bettany Hughes interview: The historian on how Socrates would have solved Greece's problems

Bettany Hughes interview

The historian on how Socrates would have solved Greece's problems
Art of the state: Pyongyang propaganda posters to be exhibited in China

Art of the state

Pyongyang propaganda posters to be exhibited in China
Mildreds and Vanilla Black have given vegetarian food a makeover in new cookbooks

Vegetarian food gets a makeover

Long-time vegetarian Holly Williams tries to recreate some of the inventive recipes in Mildreds and Vanilla Black's new cookbooks
The haunting of Shirley Jackson: Was the gothic author's life really as bleak as her fiction?

The haunting of Shirley Jackson

Was the gothic author's life really as bleak as her fiction?
Bill Granger recipes: Heading off on holiday? Try out our chef's seaside-inspired dishes...

Bill Granger's seaside-inspired recipes

These dishes are so easy to make, our chef is almost embarrassed to call them recipes
Ashes 2015: Tourists are limp, leaderless and distinctly UnAustralian

Tourists are limp, leaderless and distinctly UnAustralian

A woefully out-of-form Michael Clarke embodies his team's fragile Ashes campaign, says Michael Calvin
Blairites be warned, this could be the moment Labour turns into Syriza

Andrew Grice: Inside Westminster

Blairites be warned, this could be the moment Labour turns into Syriza
HMS Victory: The mystery of Britain's worst naval disaster is finally solved - 271 years later

The mystery of Britain's worst naval disaster is finally solved - 271 years later

Exclusive: David Keys reveals the research that finally explains why HMS Victory went down with the loss of 1,100 lives
Survivors of the Nagasaki atomic bomb attack: Japan must not abandon its post-war pacifism

'I saw people so injured you couldn't tell if they were dead or alive'

Nagasaki survivors on why Japan must not abandon its post-war pacifism
Jon Stewart: The voice of Democrats who felt Obama had failed to deliver on his 'Yes We Can' slogan, and the voter he tried hardest to keep onside

The voter Obama tried hardest to keep onside

Outgoing The Daily Show host, Jon Stewart, became the voice of Democrats who felt the President had failed to deliver on his ‘Yes We Can’ slogan. Tim Walker charts the ups and downs of their 10-year relationship on screen