3. Lambda-calculus Flashcards
Theoretische vragen bij lambda-calculus
Definitie van Church getallen
cn ≡ λf.λx.(f)^n x
Definitie van de succesor van een Church getal
succ(n) ≡ λn.λf.λx.(f)((n)f)x
Definitie van de optelling van een Church getal
plus ≡ λn.λm.λf.λx.((n)f)((m)f)x
Definitie van de vermenigvuldiging van een Church getal
times ≡ λn.λm.λf.(n)(m)f
Definitie van de booleans in de λ-calculus
true ≡ λt.λf.t en false ≡ λt.λf.f
De definitie van de if-statement in de λ-calculus
if ≡ λc.λd.λe.((c)d)e
De definitie van de cons-combinator in de λ-calculus
cons ≡ λa.λd.λz((z)a)d
De definitie van de car-combinator in de λ-calculus
car ≡ λa.λd.a
De definitie van de cdr-combinator in de λ-calculus
cdr ≡ λa.λd.d
De combinator van fixpunten binnen de λ-calculus
Fixpunt Y ≡ λf.(λx.(f)(x)x) λx.(f)(x)x
Wat is de rol van de 𝛽-gelijkheid?
Het stelt de intuïtieve betekenis van het toepassen van een functie op een actuele parameter voor
formele parameter vervangen door de actuele parameter.
Hoe heet een lambda-expressie zonder vrije variabelen
combinator
Wanneer is een functie λ-definieerbaar?
Bij definitie is een numerieke functie f, λ-definieerbaar als er een combinator F bestaat waarvan het effect op de Church getallen hetzelfde is als de operatie toegepast op de ‘echte’ getallen
Geef de definitie van een lambda-expressie
- Alle variabelen (elementen van V) zijn λ-expressies.
- Als M en N λ-expressies zijn dan is de toepassing (M)N een λ-expressie
- Als x ∈ V en M λ-expressie dan is λx.M een λ-expressie
Wat is de definitie van een fixpunt in de lambdacalculus?
X element van Λ is een fixpunt van F element van Λ als en slechts als de toepassing van F op X, X zelf is.
We zeggen dat x die behoort tot D een fixpunt van een numerieke functie f is als en slechts als f(x) = x.
