Typ obydlí - Type inhabitation

v teorie typů, pobočka matematická logika, v daném zadaném počtu, problém osídlení typu pro tento počet je následující problém:^[1] daný typ ${ displaystyle tau}$ a a prostředí pro psaní ${ displaystyle Gamma}$, existuje a ${ displaystyle lambda}$- termín M takový ${ displaystyle Gamma vdash M: tau}$? S prázdným typem prostředí je takový M považován za obyvatele ${ displaystyle tau}$.

Vztah k logice

V případě jednoduše zadaný lambda kalkul, typ má obyvatele právě tehdy, je-li jeho odpovídající návrh je a tautologie minimální implikativní logiky. Podobně, a Systém F typ má obyvatele právě tehdy, je-li jeho odpovídající propozice je tautologie logika druhého řádu.

Girardův paradox ukazuje, že obydlení typu silně souvisí s konzistencí typového systému s korespondencí Curry – Howard. Aby byl takový systém zdravý, musí mít neobydlené typy.

Formální vlastnosti

U většiny typovaných kamenů je problém osídlení typu velmi tvrdý. Richard Statman dokázal, že pro jednoduše zadaný lambda kalkul problém obydlení typu je PSPACE - kompletní. Pro ostatní kameny, jako Systém F, problém je vyrovnaný nerozhodnutelný.

Viz také

• Curry – Howardův izomorfismus

Reference

${ displaystyle Gamma vdash x: { text {Int}}}$

Tento teorie programovacího jazyka nebo teorie typů související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.