Narození |
5. ledna 1909 Hartford, Connecticut |
---|---|
Smrt |
25. ledna 1994 Madison, Wisconsin |
Domov | Spojené státy |
Státní příslušnost | americký |
Oblasti | Matematika |
Instituce | University of Wisconsin - Madison |
Diplom | Univerzita Princeton |
Dozorce | Alonzo Church |
Studenti PhD |
John Addison Jr. Paul Axt Douglas Clarke Robert Lee Constable David Kierstead Shih-Chao Liu Joan Moschovakis Yiannis N. Moschovakis Nels Nelson Gene Rose Clifford Spektor Richard Vesley Dick de Jongh (en) |
Známý pro | Teorie rekurze , aritmetická hierarchie , Kleeneova věta |
Ocenění | National Medal of Science , Leroy P. Steele Prize |
Stephen Cole Kleene , narozen dne5. ledna 1909v Hartfordu v Connecticutu a zemřel dne25. ledna 1994v Madisonu (Wisconsin) je matematik a logik USA .
Je známo, že Kleene založil obor matematické logiky, který nese název teorie rekurze , ve spolupráci zejména s Alonzo Church , Kurt Gödel , Emil Post a Alan Turing , a také lambda-kalkulus s Alonzo Church a John Barkley . On je také známý pro vynalézání pojmu regulární výraz a regulární jazyk .
Vytvořením nástrojů k formalizování konceptu vyčíslitelnosti , což umožnilo určit, které problémy lze vyřešit pomocí algoritmů , a na druhé straně vytvořením konceptů umožňujících analyzovat programovací jazyky a popsat nejjednodušší automaty , položil teoretické základy počítačové vědy . Na Kleene hvězda na Kleenova věta se rekurze věta Kleene a věta o pevném bodě Kleene připomenout úlohu, kterou hrál při vytváření těchto pojmů. Přispěl také k intuitivní logice . Jeho vliv se také měří počtem jeho vědeckých potomků. Podle MathGenealogy vedl 13 tezí a prostřednictvím svých studentů má 972 potomků, zejména prostřednictvím Roberta Lee Constable .
Kleene získal titul bakaláře na Amherst College v roce 1930. V roce 1934 získal doktorát z matematiky na Princetonské univerzitě . Jeho práce režírovaná Alonzem Churchem má název „ Teorie pozitivních celých čísel ve formální logice “ . Obsahuje studium vypočítatelných funkcí z hlediska lambda-kalkulu, který je první z charakteristik rekurzivních funkcí . V roce 1934 zůstal Kurt Gödel v Princetonu a představil své slavné věty o neúplnosti . Gödelův důkaz zásadně využívá funkce definované rekurzí. Poté vyvstává otázka rovnocennosti definic vypočítatelných funkcí. Pro Alonzo Church jsou to funkce, které lze definovat v lambda-kalkulu . Kleeneova práce z roku 1934 zkoumá tento návrh. J. Barkley Rosser , další student církve, ukazuje rovnocennost s výpočtem slučovače z Haskell Curry . Nakonec Alan Turing a Emil Post navrhují definici Turingových strojů a Kleene zkoumá definici Gödelových rekurzivních funkcí. Víme, že tyto definice jsou rovnocenné. Od té doby Kleene pracoval na třídě rekurzivních funkcí, které dokazuje zejména věta o normální formě.
V roce 1935 nastoupil na katedru matematiky na University of Wisconsin , kde byl nejprve instruktorem matematiky, poté se v roce 1937 stal odborným asistentem.
V letech 1939 až 1940 byl vyslán do Institutu pro pokročilé studium v Princetonu, kde pomáhal založit teorii rekurze. V letech 1941-1942 působil jako docent na Amherst College. V letech 1942 až 1946 se účastnil druhé světové války jako instruktor amerického námořnictva . Na univerzitu ve Wisconsinu se vrátil jako docent, poté jako řádný profesor v roce 1948.
Později Kleene představil aritmetickou hierarchii , což je hierarchie podmnožin množiny přirozených celých čísel definovatelných v jazyce prvního řádu Peanoovy aritmetiky. S Emilem Postem představil stupeň nerozpustnosti, nazývaný Turingův stupeň (po Alanovi Turingovi) sady přirozených celých čísel, který měří úroveň algoritmické nerozpustnosti sady.
V létě roku 1951 zůstal Kleene v RAND Corporation , kde studoval slavný článek WS McCullocha a Waltera Pittsa na neuronových sítích. Napsal interní zprávu, která byla později publikována v Automata Studies ; zavádí regulární výrazy a dokazuje Kleeneovu větu o ekvivalenci mezi popisem racionálním výrazem a automatem.
Kleene také studuje vztah mezi konstruktivní matematikou ve smyslu Brouwera , vynálezce intuicionistické logiky a rekurzivních funkcí. V roce 1950 využil Guggenheimova stipendia a zůstal v Amsterdamu ve skupině nizozemských intuicionistických matematiků. Se svým studentem Richardem E. Vesleym píše knihu, ve které rozvíjejí koncept „realizovatelného“ pro intuicionismus.
Od roku 1964 do roku 1979 je Kleene držitelem matematického předsedy Cyruse C. MacDuffee a měl také administrativní povinnosti vůči univerzitě: Vede katedru matematiky a výpočetní techniky 1962-1963 a děkan ( děkan ) College of Letters and Science od 1969 do 1974. Z univerzity odešel v roce 1979. V roce 1999 byla na jeho počest přejmenována Matematická knihovna na University of Wisconsin.
Ostřílený horolezec prokázal velkou vášeň pro obranu přírody a životního prostředí.
Jeho příjmení je vyslovováno [kliːniː] nebo[kliːn] . Sám Kleene to vyslovil[kleɪniː] . Jeho syn Kenneth C. Kleene píše: „ Pokud vím, je tato výslovnost ve všech známých jazycích nesprávná. Věřím, že tuto novou výslovnost vymyslel můj otec. " .