Obituary: Professor Stephen Kleene
Thursday 10 February 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.
- 1 Half of young women unable to ‘locate vagina’ and 65% find it difficult to say the word
- 3 Saudis risk new Muslim division with proposal to move Mohamed’s tomb
- 4 A teacher speaks out: 'I'm effectively being forced out of a career that I wanted to love'
- 5 Mexican woman becomes world’s 'oldest person' at 127
Perez Hilton apologises for publishing Jennifer Lawrence naked 4Chan photos
Jennifer Lawrence 'nude photo hacker' claims there are hundreds more celebrity images to come
Victoria Justice on naked photo leak: 'Let me nip this in the bud right now – pun intended'
Ariana Grande nude photos leak: Pictures are completely fake, say representatives
Saudis risk new Muslim division with proposal to move Mohamed’s tomb
Rotherham child sex abuse scandal: Labour Home Office to be probed over what Tony Blair's government knew - and when
What do immigrants really think of Britain? Polish immigrant's Reddit post goes viral
Ashya King: Parents of five-year-old boy refused permission to visit him in hospital and denied bail at Spanish court
With Douglas Carswell joining Ukip, my party has taken another giant step forward
When elitism grips the top of British society to this extent, there is only one answer: abolish private schools
Ashya King: 'Cruel NHS has not given us the treatment we need', says father of five-year-old with brain tumour who fled to Spain
£32000 - £40000 per annum + bonus: Ashdown Group: HR Manager (Generalist) -Old...
£45000 - £50000 per annum: Ashdown Group: Talent / Learning & Development Mana...
Up to £40,000: Ashdown Group: Standalone HR Manager role for an SME business b...
£350 - £400 per day: Orgtel: HR Analyst - Banking - Bristol - £350 - £400 per ...