Der Lambda-Kalkül

...als weiteres Berechnungsmodell,

(vgl. Termersetzungssysteme, Turingmaschine, Random-Access-Maschine)

Syntax: die Menge der Lambda-Terme Λ ist

• jede Variable ist ein Term: v∈V⇒v∈Λ
• Funktionsanwendung (Applikation):

  F∈Λ, A∈Λ⇒(FA)∈Λ

• Funktionsdefinition (Abstraktion):

  v∈V, B∈Λ⇒(λv.B)∈Λ

Semantik: eine Relation →_β auf Λ

(vgl. →_R für Termersetzungssystem R)