|
|
| Line 1: |
Line 1: |
| In [[type theory]], a branch of [[mathematical logic]], in a given typed calculus, the '''type inhabitation problem''' for this calculus is the following problem:<ref>{{cite journal |title=Inhabitation in Typed Lambda-Calculi (A Syntactic Approach) |author=Pawel Urzyczyn |journal=Lecture Notes in Computer Science |pages=373–389 |year=1997 |publisher=Springer |url=http://www.springerlink.com/index/tg515q64xn434l70.pdf}}</ref> given a type <math>\tau</math> and a [[typing environment]] <math>\Gamma</math>, does there exist a <math>\lambda</math>-term M such that <math>\Gamma \vdash M : \tau</math>? With an empty type environment, such an M is said to be an inhabitant of <math>\tau</math>.
| | Not much to say about myself really.<br>Finally a part of wmflabs.org.<br>I just hope Im useful in one way . |
| | |
| == Relationship to logic ==
| |
| | |
| In the case of [[simply typed lambda calculus]], a type has an inhabitant if and only if its [[Curry-Howard|corresponding]] proposition is a [[tautology (logic)|tautology]] of minimal implicative logic. Similarly, a [[System F]] type has an inhabitant if and only if its [[Curry-Howard|corresponding]] proposition is a tautology of [[second-order logic]].
| |
| | |
| == Formal properties ==
| |
| | |
| For most typed calculi, the type inhabitation problem is very [[PSPACE-hard|hard]]. [[Richard Statman]] proved that for [[simply typed lambda calculus]] the type inhabitation problem is [[PSPACE-complete]]. For other calculi, like [[System F]], the problem is even [[decision problem|undecidable]].
| |
| | |
| == See also ==
| |
| * [[Curry–Howard isomorphism]]
| |
| | |
| ==References==
| |
| {{reflist}}
| |
| | |
| [[Category:Lambda calculus]]
| |
| [[Category:Type theory]]
| |
| | |
| | |
| {{type-theory-stub}}
| |
Latest revision as of 21:54, 26 April 2014
Not much to say about myself really.
Finally a part of wmflabs.org.
I just hope Im useful in one way .