Lambdacalculus

Ongetypeerde lambdacalculus De ongetypeerde lambdacalculus is de lambdacalculus zoals ze in 1936 werd geïntroduceerd door Church en Kleene.

Abstractie is een operatie binnen de lambdacalculus waarin een term "gegeneraliseerd" wordt naar een bepaalde variabele.

Deze functies zijn voorbeelden van hoe eenvoudige arithmetische operaties in de lambdacalculus gedefinieerd kunnen worden.

Het probleem dat zich aandient voor de lezer die hetzelfde wil proberen, is dat het bovenstaande niet eindig uit te drukken is in de lambdacalculus.

Naast deze uitdrukkingen toonde Barendregt aan dat het met zijn notatie mogelijk is alle mogelijkheden van de functionele programmeertalen direct te modelleren in de lambdacalculus.

Zoals eerder uiteengezet, is het in de lambdacalculus mogelijk zowel de selectie- als de herhalingsfunctie van de turingmachine te modelleren.

De rest van dit artikel gaat over de (oorspronkelijke) ongetypeerde lambdacalculus.

Hierin onderscheiden zij zich van functionele programmeertalen, die het Churchmodel van functietoepassing gebruiken als model van berekening (zie ook Lambdacalculus).

Combinatorische logica is de basis voor een bepaalde stijl van functionele programeertalen en de kracht van combinatorische logica is vergelijkbaar met de lambdacalculus van Alonzo Church.

Applicatie Applicatie binnen de lambdacalculus is de analogie van het toepassen van een functie op een argument.

Bij Landin was dat de lambdacalculus die uitgebreid werd met een paar operaties, zoals het toekennen van waarden (assignatie).

Het ontbeert de ongetypeerde lambdacalculus dus aan een manier om aan te geven dat bepaalde termen niet van toepassing zijn op bepaalde andere termen.

In tegenstelling tot de verwachtingen bleek het slechte nieuws van Park en Landin het begin van een geheel nieuwe tak van lambdacalculus die niet alleen wel een accuraat model van berekening bleek, maar zelfs veelzijdiger was dan de al bekende calculus.

Barendregt is bekend van verhandelingen over lambdacalculus en typetheorie, met name zijn The Lambda Calculus: Its Syntax and Semantics (1984), dat geldt als het standaardwerk op dit gebied.

De lambdacalculus, soms ook als λ-calculus geschreven, is een formeel systeem dat in de wiskunde en theoretische informatica wordt gebruikt om het definiëren en uitvoeren van berekenbare functies te onderzoeken.

Een aantal voorbeelden: Een applicatie van een abstractie op een andere term is eigenlijk een speciale situatie in de lambdacalculus.

Formele calculi zoals de lambdacalculus en de combinatorische logica worden nu bestudeerd als geïdealiseerde programmeertalen.

Hij deed dit door uit te gaan van de soorten dingen die een taal moet bevatten om dergelijke uitdrukkingskracht te bezitten en deze zaken in de lambdacalculus in te voeren als bruikbare termen.

In 1969 publiceerden David Park en Scott Landin echter een vervolg waarin zij demonstreerden dat de lambdacalculus inherent een bijzonder grove fout bevat waardoor het geen goed model van berekening is.

Lambdacalculus als model van berekening Leibniz en het Entscheidungsproblem Wiskunde is sinds de eerste dagen der mensheid een onderdeel van de kennisbundel van de mensheid geweest.