Richard Statman
Encyclopedia
Richard Statman is an American
computer scientist
whose principal research interest is the theory of computation
, especially symbolic computation. His research involves lambda calculus
, type theory
and combinatory algebra.
from Stanford University
for his Ph.D dissertation, supervised by Georg Kreisel
, entitled Structural Complexity of Proofs. His achievements include the proof that type inhabitation problem
problem in simply typed lambda calculus
is PSPACE-complete
.
United States
The United States of America is a federal constitutional republic comprising fifty states and a federal district...
computer scientist
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
whose principal research interest is the theory of computation
Theory of computation
In theoretical computer science, the theory of computation is the branch that deals with whether and how efficiently problems can be solved on a model of computation, using an algorithm...
, especially symbolic computation. His research involves lambda calculus
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
, type theory
Type theory
In mathematics, logic and computer science, type theory is any of several formal systems that can serve as alternatives to naive set theory, or the study of such formalisms in general...
and combinatory algebra.
Career
In 1974, Statman received his Ph.D.Ph.D.
A Ph.D. is a Doctor of Philosophy, an academic degree.Ph.D. may also refer to:* Ph.D. , a 1980s British group*Piled Higher and Deeper, a web comic strip*PhD: Phantasy Degree, a Korean comic series* PhD Docbook renderer, an XML renderer...
from Stanford University
Stanford University
The Leland Stanford Junior University, commonly referred to as Stanford University or Stanford, is a private research university on an campus located near Palo Alto, California. It is situated in the northwestern Santa Clara Valley on the San Francisco Peninsula, approximately northwest of San...
for his Ph.D dissertation, supervised by Georg Kreisel
Georg Kreisel
Georg Kreisel FRS is an Austrian-born mathematical logician who has studied and worked in Great Britain and America. Kreisel came from a Jewish background; his family sent him to England before the Anschluss, where he studied mathematics at Trinity College, Cambridge and then, during World War...
, entitled Structural Complexity of Proofs. His achievements include the proof that type inhabitation problem
Type inhabitation problem
In type theory, a branch of mathematical logic, in a given typed calculus, the type inhabitation problem for this calculus is the following problem: given a type \tau and a type environment \Gamma, does there exist a \lambda-term M such that \Gamma \vdash M : \tau? With an empty type environment,...
problem in simply typed lambda calculus
Simply typed lambda calculus
The simply typed lambda calculus , a formof type theory, is a typed interpretation of the lambda calculus with only one type constructor: \to that builds function types. It is the canonical and simplest example of a typed lambda calculus...
is PSPACE-complete
PSPACE-complete
In complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be reduced to it in polynomial time...
.