Niettypeerbaarheid

Niettypeerbaarheid is een begrip uit de type theorie en verwijst naar de eigenschap van een term die geen typering kan krijgen binnen een bepaald type systeem. In woorden: er bestaat geen type T waarvoor de term volgens de regels van het systeem een geldige typetoekenning heeft. Ofwel, er is geen afleiding die aantoont dat de term een geldig type heeft.

In de context van de lambda-calculus wordt vaak gesproken over het eenvoudig-typed lambda-calculus (STLC). Een bekend voorbeeld van niet-typeerbaarheid in dit systeem is een term die zichzelf als argument toepast, zoals λx. x x. Bij toepassing van x op x vereist de typering dat x een type heeft dat zowel als functie als invoer kan dienen, wat leidt tot een cyclische of oneindige type-relatie. Omdat dergelijke finite types niet toestaan, kan λx. x x geen type krijgen in STLC. Een ander klassiek voorbeeld is het Y-combinator, een vaste-punt-operator, die in het STLC geen typering kan krijgen en zo niet-typeerbaar is in dat systeem.

Niettypeerbaarheid hangt af van het gekozen type systeem. In ruimere of meer expressieve systemen (bijvoorbeeld met polymorfe typen of recursieve typen) kunnen meer termen wel typeerbaar zijn, maar ook in dergelijke systemen kan een term nog steeds niet-typeerbaar blijven. Het concept is nuttig om de grenzen van wat een type systeem veilig en computatief mogelijk maakt te begrijpen en om afwegingen te maken bij de ontwerpkeuzes van programmeertalen en logische systemen.