- 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 card 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.

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

--

Posted By Lance to Computational Complexity at 1/05/2009 08:22:00 AM