Stephen Kleene: Not A Regular Guy

The great logician Stephen Kleene was born one hundred years ago today in Hartford, Connecticut. No single person affected a typical introductory theoretical computer science course more than Kleene. Kleene gave us

• Regular expressions and their equivalence to langugages accepted by finite automata. That's why we call them Regular Languages.
• Kleene Closure, the * operator in regular expressions. L^* is the set of all finite concatenations of strings in L. Source of great homework problems, for example: Show P is closed under Kleene closure.
• A recursive definition of Turing's languages, the reason they are often called Recursive Languages (though not without controversy).
• The terminology Church's thesis that we now call the Church-Turing thesis (though more controversy).
• The arithmetic hierarchy, a forerunner of our polynomial-time hierarchy.
• The S_mn theorem that one can uniformly hardwire part of the input into the code of a Turing machine.
• The recursion theorem (sometimes called the Kleene fixed point theorem) that informally says no matter how nasty the virus, some program remains unscathed.

and much more.

Klenne passed away January 25, 1994 in Madison, Wisconsin where he spent most of his academic career.