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
Latest stories from i100
Have you tried new the Independent Digital Edition apps?
Independent Dating
and  

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

iJobs Job Widget
iJobs People

Ashdown Group: HR Manager - West London - £50,000

£40000 - £50000 per annum + bonus: Ashdown Group: HR Manager - West London - £...

Recruitment Genius: Recruitment & HR Administrator

£17000 - £18000 per annum: Recruitment Genius: This is an exciting opportunity...

Guru Careers: HR Manager / HR Business Partner

£55 - 65k (DOE) + Benefits: Guru Careers: A HR Manager / HR Business Partner i...

Recruitment Genius: Senior HR Assistant

£23000 - £25000 per annum: Recruitment Genius: The Company's vision is to be t...

Day In a Page

Lionel, Patti, Burt and The Who rock Glasto

Lionel, Patti, Burt and The Who rock Glasto

This was the year of 24-carat Golden Oldies
Paris Fashion Week

Paris Fashion Week

Thom Browne's scarecrows offer a rare beacon in commercial offerings
A year of the caliphate:

Isis, a year of the caliphate

Who can defeat the so-called 'Islamic State' – and how?
Marks and Spencer: Can a new team of designers put the spark back into the high-street brand?

Marks and Spencer

Can a new team of designers put the spark back into the high-street brand?
'We haven't invaded France': Italy's Prime Minister 'reclaims' Europe's highest peak

'We haven't invaded France'

Italy's Prime Minister 'reclaims' Europe's highest peak
Isis in Kobani: Why we ignore the worst of the massacres

Why do we ignore the worst of the massacres?

The West’s determination not to offend its Sunni allies helps Isis and puts us all at risk, says Patrick Cockburn
7/7 bombings 10 years on: Four emergency workers who saved lives recall the shocking day that 52 people were killed

Remembering 7/7 ten years on

Four emergency workers recall their memories of that day – and reveal how it's affected them ever since
Humans: Are the scientists developing robots in danger of replicating the hit Channel 4 drama?

They’re here to help

We want robots to do our drudge work, and to look enough like us for comfort. But are the scientists developing artificial intelligence in danger of replicating the TV drama Humans?
Time to lay these myths about the Deep South to rest

Time to lay these myths about the Deep South to rest

'Heritage' is a loaded word in the Dixie, but the Charleston killings show how dangerous it is to cling to a deadly past, says Rupert Cornwell
What exactly does 'one' mean? Court of Appeal passes judgement on thorny mathematical issue

What exactly does 'one' mean?

Court of Appeal passes judgement on thorny mathematical issue
E L James's book Grey is a reminder of how the phenomenon of the best-seller works

Grey is a reminder of how the phenomenon of the best-seller works

It's hard to understand why so many are buying it – but then best-selling was ever an inexact science, says DJ Taylor
Behind the scenes of the world's most experimental science labs

World's most experimental science labs

The photographer Daniel Stier has spent four years gaining access to some of the world's most curious scientific experiments
It's the stroke of champions - so why is the single-handed backhand on the way out?

Single-handed backhand: on the way out?

If today's young guns wish to elevate themselves to the heights of Sampras, Graf and Federer, it's time to fire up the most thrilling shot in tennis
HMS Saracen: Meeting the last survivor of a submarine found 72 years after it was scuttled

HMS Saracen

Meeting the last survivor of a submarine found 72 years after it was scuttled
7/7 bombings 10 years on: Martine Wright lost both legs in the attack – she explains how her experience since shows 'anything is possible'

7/7 bombings 10 years on

Martine Wright lost both legs in the attack – she explains how her experience since shows 'anything is possible'