WikiDer > Lambda-Kalkül

Das Lambda-Kalkül, manchmal auch als λ-Kalkül geschrieben, ist ein formales System das in der Mathematik und Theoretische Informatik wird verwendet, um berechenbares zu definieren und auszugeben Funktionen zu untersuchen. Er wurde in 1936 durch Alonzo-Kirche und Stephen Kleene im Rahmen ihrer Erforschung der Grundlagen der Mathematik, wird aber jetzt hauptsächlich bei der Untersuchung verwendet Berechenbarkeit. Der Lambda-Kalkül kann als eine Art minimale Programmiersprache angesehen werden, die in der Lage ist, Algorithmus beschreiben. Der Lambda-Kalkül ist Turingkomplett und bildet die Grundlage des Paradigmas für funktionale Programmiersprachen.

Der Rest dieses Artikels befasst sich mit dem ursprünglichen, nicht typisierten Lambda-Kalkül, bei dem es keine Einschränkungen bei der Funktionsanwendung gibt. Der untypisierte Lambda-Kalkül hat keine Vorstellung von a Domain einer Funktion. Die meisten Anwendungen des Lambda-Kalküls verwenden jedoch Varianten mit einer Typenbezeichnung.

Untypisierte Lambda-Kalküle und Berechnungsprinzip

Der untypisierte Lambda-Kalkül ist der Lambda-Kalkül, wie er 1936 von Church und Kleene eingeführt wurde. Dieser Lambda-Kalkül beschreibt eine Berechnung als Folge von Begriffen (auch Ausdrücke genannt). Der erste Begriff stellt die anfängliche Beschreibung des Problems, ob als Algorithmus zu verstehen oder nicht, und eine Eingabe für diesen Algorithmus dar. Der Lambda-Kalkül besteht aus einer Sammlung gültiger Ausdrücke, die umgeschrieben (sprich: vereinfacht) werden können. Dieser Kalkül ist also a System umschreiben: ein Begriff ${Anzeigestil T}$ kann über feste Regeln in einen Begriff umgeschrieben werden ${Anzeigestil T'}$. Das hört auf, wenn wir den Begriff mit den Regeln nicht mehr umschreiben können. Das Ziel ist oft, jedes berechenbare Problem in Form eines Anfangsterms zu schreiben (zu modellieren), damit die Berechnung in endlich vielen Schritten abgeschlossen werden kann.

Der Lambda-Kalkül ist also ein System, das nur aus gültigen λ-Ausdrücken besteht, die durch ein festes System in (hoffentlich) einfachere Ausdrücke umgewandelt werden können. Das Schreiben eines Ausdrucks in eine einfachere, aber äquivalente Form heißt die Ermäßigung. Eine Kürzung erfolgt oft durch in einem Begriff ${Anzeigestil T}$ Teil ${Anzeigestil E}$ durch ein anderes Teil ersetzt werden ${Anzeigestil E'}$ für so einen Begriff ${Anzeigestil T'}$ werden. Wir schreiben das als

${Displaystil [E'/E]T=T'}$

Durch Meta-Ausdrücke, die wir können Über Argumentation der Lambda-Kalküle. Beispiele sind die Substitutionsoperator${Anzeigestil [./.].}$ und ${Anzeigestil VV(E)}$, um den Satz von zu erhalten freie Variablen in einem Ausdruck ${Anzeigestil E}$ aufzeigen. Wir verwenden hier also die Meta-Operation für die Ersetzung.Wenn diese Gleichheit von links nach rechts angewendet wird, was normalerweise der Fall ist, schreiben wir auch also

${displaystyle Tlongrightarrow T'}$

Ist der Übergang von t zu T' aus einer beliebigen Anzahl von Reduktionen (d. h. keine, genau eine oder mehr als eine) schreiben wir es wie folgt:

${displaystyle Tlongrightarrow ^{*}T'}$

Beispiel

Betrachten wir als Beispiel für eine Berechnung durch Reduktionen zunächst einen einfachen arithmetischen Term:

${displaystyle { egin{matrix}(10 8*4)-(6/3) longrightarrow (10 32)-(6/3) longrightarrow 42-(6/3) longrightarrow 42-2 longrightarrow 40end{matrix}}}$

Also können wir auch schreiben ${displaystyle (10 8*4)-(6/3)longrightarrow ^{*}40}$ und auch ${Anzeigestil(10 8*4)-(6/3)=40}$.

Wir hätten auch eine andere Reihenfolge wählen können:

${displaystyle { egin{matrix}(10 8*4)-(6/3) longrightarrow (10 8*4)-2 longrightarrow (10 32)-2 longrightarrow 42-2 longrightarrow 40end{matrix}}}$

Eine Laufzeit kann daher manchmal auf mehrere Arten gekürzt werden. Außerdem kann ein Weg viel einfacher und schneller sein als ein anderer.

Grundlegendes Konzept

Begriffe (Ausdrücke)

Terme innerhalb des Lambda-Kalküls werden konstruiert, indem zwei grundlegende Operationen (Abstraktion und Anwendung) auf Variablen von a . angewendet werden unendliche Sammlung. Im Folgenden werden wir Variablen in Lambda-Begriffen mit einigen typischen Namen bezeichnen, wie z ${Anzeigestil x,y,z,v,v',w,ldots}$.

Sie V eine Menge von Variablen, dann ist die Menge von Lambda-Termen (auch Lambda-Ausdrücke genannt) Λ wie folgt definiert:

• Eine Variable ist ein Lambda-Ausdruck: ${Displaystilflosse VRrechte Pfeilflosse Lambda }$
• Sein ich und Nein Lambda-Terme, dann die Anwendung von ich auf Nein ein Lambda-Ausdruck: ${displaystyle M,Nin Lambda Rechtspfeil (MN)in Lambda }$ (Anwendung);
• Ist X eine Variable und ich ein Lambda-Term, dann ist die Abstraktion beendet X von ich ein Lambda-Ausdruck: ${displaystyle xin Vland Min Lambda Rechtspfeil (lambda x.M)in Lambda }$ (Abstraktion).

Durch diese Definition lässt sich jeder mögliche Algorithmus als Lambda-Term im Lambda-Kalkül darstellen. Ein Ausdruck, der mit den obigen Regeln nicht konstruiert werden kann, ist Nein gültiger Lambda-Ausdruck.

Zum letzten Punkt ist anzumerken, dass ${Anzeigestil x}$ nicht in ${Anzeigestil M}$ müssen auftreten; ${Anzeigestil Lambda x.y}$ ist auch ein gültiger Lambda-Ausdruck, der eine Abstraktion über ist ${Anzeigestil x}$ im Lambda-Term ${Anzeigestil y}$ (wir werden weiter unten sehen, dass dieser Begriff als Konstante verstanden werden kann).

Oft wird die Standardnotation abgekürzt oder die Leute verwenden ihre eigene, alternative Notation. Dies ist möglich, sofern man die eigene Notation systematisch anwendet, um Verwechslungen zu vermeiden.

Um die Notation klarer zu machen, werden häufig folgende Konventionen verwendet:

• Die äußeren Klammern entfallen. Einer schreibt ${Anzeigestil MN}$ Anstatt von ${Anzeigestil (MN)}$.
• Bewerbung ist links assoziativ. Also kann man ${Anzeigestil ((MN)P)}$ abkürzen zu ${Anzeigestil MNP}$. Der Begriff ${displaystyle (lambda f.lambda g.fgx)FG}$ wird daher gelesen als ${displaystyle (((lambda f.lambda g.fgx)F)G)}$ und nicht wenn ${displaystyle (lambda f.lambda g.fgx)(FG)}$. Der Begriff reduziert sich daher auf ${Anzeigestil FGx}$ und nicht zu ${Anzeigestil Lambda g.(FG)gx}$.
• Mehrere aufeinanderfolgende Abstraktionen werden zusammengeführt:${Anzeigestil Lambda x.lambda y.M}$ wird wie ${Anzeigestil Lambda xy.M}$ geschrieben.
• Abstraktion ist rechtsassoziativ. Also kann man ${ Anzeigestil Lambda x.(Lambda y.(Lambda z.(xyzzyx)))}$ schreibe als ${Anzeigestil Lambda x.lambda y.lambda z.xyzzyx}$.
• Klammern können weggelassen werden, wenn dies nicht zu mehrdeutigen Begriffen oder Fehlern führt. So kann man im Begriff ${Anzeigestil (MN)}$ lassen Sie die Klammern weg, aber in ${Anzeigestil M(NP)}$ nicht.

Es ist klar, dass Lambdaterme immer nach einer bestimmten Struktur aufgebaut sind. Dies ist auch die Grundlage vieler beweisen bezüglich der Lambda-Kalküle, die Methode von Strukturinduktion basiert auf der Existenz dieser Struktur.

Beispiele für Lambda-Begriffe sind${Anzeigestil v}$;${displaystyle v'w}$;${Anzeigestil Lambda f.lambda y.fy}$;${displaystyle (lambda w.fw)q}$ und${displaystyle q(lambda w.fw)}$.

Anwendung

Die Anwendung innerhalb des Lambda-Kalküls ist die Analogie zum Anwenden einer Funktion auf ein Argument. Im Lambda-Kalkül können wir nur einen Term auf einen anderen Term anwenden, da der Lambda-Kalkül nur aus Termen besteht.

Die Verwendung von ${Anzeigestil M}$ auf ${Displaystil N}$ wird im Lambda-Kalkül geschrieben als ${Anzeigestil MN}$. Wir können ${Displaystil N}$ sehen als Argument für ${Anzeigestil M}$.

Die Bewerbung erfolgt durch Auswechslung wie von der vorgeschrieben β-Reduktion/ das Beta-Axiom.

Abstraktion

Abstraktion ist eine Operation innerhalb des Lambda-Kalküls, bei der ein Begriff auf eine bestimmte Variable "verallgemeinert" wird. Mit anderen Worten, wir konstruieren die Vorschrift einer neuen Funktion. Anstatt eine feste (oder konstante) Variable zu sein, wird eine Variable als (formaler) Parameter bezeichnet: Der abstrahierte Lambda-Term kann dann (über β-Reduktion) reduziert werden, indem der formale Parameter durch einen Wert ersetzt wird.

Um anzugeben, welche Variable die Sonderstellung innerhalb des Lambdaterms einnimmt, wird der Sonderoperator Lambda (λ) verwendet. Sie ich einer im Allgemeinen von X abhängiger Ausdruck. Dann ist ${Displaystil Lambda x.M}$ das Bild${displaystyle xmapsto M(x)}$. Beispielsweise, ${Anzeigestil Lambda x.x}$ das Identitätsfunktion${Anzeigestil I(x)=x}$. Schließlich wird das Argument bei der Anwendung immer zurückgegeben (siehe β-Gleichheit).

Wir sagen, dass der λ-Operator eine Variable innerhalb eines Terms bindet: Jedes Vorkommen dieser Variable innerhalb des Lambda-Terms ist eine Referenz auf die vom λ-Operator benannte Variable. Eine solche Variable wird als gebundene Variable bezeichnet. Im obigen Beispiel ist die Variable ${Anzeigestil x}$ eine gebundene Variable.

Freie und gebundene Variablen

Das Anwenden einer Funktion auf ein Argument wird im Lambda-Kalkül als Ersetzen des Formalparameters durch einen Aktualparameter dargestellt. Dafür wird Substitution verwendet. Wir müssen jedoch bei der Verwendung von Substitutionen vorsichtig sein, genauso wie es in Programmiersprachen vorkommen kann Schatten von Variablen auftreten.

Das Auftreten von freien Variablen innerhalb des Lambda-Kalküls ist wie der Kalkül selbst induktiv definiert. Für einen Lambda-Term ${Anzeigestil M}$ gilt, dass die freien Variablen, bezeichnet als ${Displaystil VV(M)}$ (oder wenn ${Displaystil FV(M)}$), sind wie folgt definiert:

• ${Anzeigestil für alle xin V:VV(x)={x}}$
• ${Anzeigestil VV (MN) = VV (M) Tasse VV (N)}$
• ${Anzeigestil VV(lambda x.M)=VV(M)setminus {x}}$

Abstraktion bindet Parameter. Im ${Displaystil Lambda x.M}$ wird die Variable ${Anzeigestil x}$ gebunden in ${Anzeigestil M}$. Eine nicht gebundene Variable wird als freie (oder ungebundene) Variable bezeichnet.

Von einem Lambda-Term ${Displaystil Lambda x.M}$ Sie sagen, dass

• ${Anzeigestil Lambda x}$ ist eine Bindung von ${Anzeigestil x}$ im ${Anzeigestil M}$;
• die Reichweite der Bindung ${Anzeigestil M}$ ist. Dies bedeutet, dass alle ungebundenen Vorkommen von ${Anzeigestil x}$ im ${Anzeigestil M}$ an diese Abstraktion gebunden.

Ist eine Begrenzung des gebundenen Termes erforderlich, erfolgt dies mit Klammern um den gesamten Term; also im folgenden Beispiel die ${Anzeigestil x}$ innerhalb Klammern gebunden, dass außen frei ist:

${displaystyle(lambda x.x)x}$

Übrigens ist es innerhalb der Lambda-Kalküle üblich, dies nicht zu tun – das ist verwirrend. Aus diesem Grund wird vereinbart, dass für gebundene Variablen niemals die gleichen Namen wie für freie Variablen verwendet werden. Dies wird gemeinhin als bezeichnet Barendregta-Termin erwähnt. Um diese Konvention zu erfüllen, kann es manchmal erforderlich sein, den Namen einer Variablen zu ändern, bevor Sie mit der Berechnung fortfahren. Diese Namensänderungen werden nur auf gebundene Variablen angewendet und können mit der sogenannten α-Reduktion gelöst werden.

Ein Term ohne freie Variablen wird geschlossener Term oder Kombinator genannt.

Auswechslung

Ein Funktionsaufruf, auch Funktionsanwendung genannt, wird realisiert, indem die Formalparameter (die in der Funktionsdefinition verwendeten Variablen) in der Funktionsregel durch die Aktualparameter (die aktuellen Werte der Formalparameter) ersetzt werden, wie in der Beschreibung beschrieben Beta-Axiom. Zum Beispiel, wenn wir ${displaystyle (lambda y.R)E}$ wollen trainieren, wir müssen rein ${Anzeigestil R}$ jedes Auftreten von ${Anzeigestil y}$ das ist gebunden an ${Anzeigestil Lambda y}$ wird ersetzt durch ${Anzeigestil E}$, mit anderen Worten, wir müssen ${Anzeigestil R}$ die freien Auftritte von ${Anzeigestil y}$ ersetzt durch den Ausdruck ${Anzeigestil E}$. Wir vermerken dies als ${displaystyle [E/y]R}$ und ist somit die Substitution von ${Anzeigestil y}$ vor dem ${Anzeigestil E}$ im ${Anzeigestil R}$. Wir müssen jedoch aufpassen, dass keine freien Vorkommen von Variablen in ${Anzeigestil E}$ bind, da dies zu einem Fehler führen würde.

Sie ${Anzeigestil E}$, ${Anzeigestil P}$ und ${Anzeigestil R}$ gültige Lambda-Bedingungen und ${Anzeigestil a}$, ${Anzeigestil y}$ und ${Anzeigestil z}$ Variablen aus ${Anzeigestil V}$. Dann definieren wir die Substitution von ${Anzeigestil y}$ vor dem ${Anzeigestil E}$ im ${Anzeigestil R}$, oder ${displaystyle [E/y]R}$, wie folgt:

1. ${displaystyle [E/y]y=E}$
2. ${Anzeigestil [E/y]z=z}$ wenn y von z . verschieden ist
3. ${Anzeigestil [E/y](RP)=([E/y]R)([E/y]P)}$
4. ${displaystyle [E/y]lambda y.R=lambda y.R}$
5. ${displaystyle [E/y]Lambda z.R=Lambda z.[E/y]R}$ wenn ${Anzeigestil y}$ unterscheidet sich von ${Anzeigestil z}$ und ${Anzeigestil z}$ keine freie Variable ist in ${Anzeigestil R}$
6. ${displaystyle [E/y]lambda z.R=lambda a.[E/y][a/z]R}$ wenn ${Anzeigestil y}$ unterscheidet sich von ${Anzeigestil z}$, ${Anzeigestil z}$ eine freie Variable ist in ${Anzeigestil R}$ und wenn ${Anzeigestil a}$ keine freie Variable ist in ${Anzeigestil R}$

Die dritte Zeile besagt, dass in einer Anwendung die Ersetzung auf beide Teilausdrücke angewendet werden muss.
Die vierte Regel besagt, dass wir nichts tun sollten, wenn wir eine Variablenersetzung auf eine Bindung dieser Variablen anwenden müssen. Alle ${Anzeigestil y}$'s im zu ersetzenden Ausdruck sind tatsächlich gebunden.
Die letzte Regel stellt sicher, dass wir nicht versehentlich freie Variablen extrahieren ${Anzeigestil R}$ zu binden. Dann führen wir zunächst eine weitere Substitution durch, bei der wir eine Variable umbenennen, um die Bindung dieser Variablen zu verhindern. In der letzten Zeile wird auch die Anwendung der Alpha-Axiom um zu sehen.

Curry

Aus der Definition eines Lambda-Ausdrucks folgt, dass eine Funktion im Lambda-Kalkül nur einen Parameter haben kann, es ist jedoch möglich, den λ-Operator so zu definieren, dass er mehrere Variablen gleichzeitig binden kann. Wir sprechen dann von einer Grenze Vektor von Variablen. Dies wird jedoch oft unterlassen, da sowohl Schönfinkel als auch Haskell-Curry runden 1934 bewiesen, dass es sich bei dieser Vektorbindung tatsächlich um einen mehrfach abstrahierten Begriff handelt. Currys Beweis führt zu einem Beschreibungsprozess für einen solchen Vektor, der noch Currying genannt wird. Mit anderen Worten, ein Term der Form ${Anzeigestil Lambda xyz.xyzzyx}$ unterscheidet sich nicht von dem Begriff ${Anzeigestil Lambda x.lambda y.lambda z.xyzzyx}$. Es ist hier nützlich zu beachten, dass die Abstraktion als Operator rechtsassoziativ ist und dass das Vorstehende daher gelesen werden sollte als ${ Anzeigestil Lambda x.(Lambda y.(Lambda z.(xyzzyx)))}$.

Betrachten wir dies etwas anders. Wir können immer eine Funktion von n Variablen als Funktion von n-1 Variablen betrachten, was als Ergebnis eine Funktion von 1 Variable hat. Um die Funktion aufzurufen, rufen wir sie mehrmals auf, wobei jedes Mal ein Argument übergeben wird.

Currying ist im Lambda-Kalkül möglich, da der Lambda-Kalkül es Funktionen ermöglicht, als Ergebnis eine Funktion zurückzugeben. Mit anderen Worten, es gibt Unterstützung für Funktionen höherer Ordnung.

Currying kann auch in der Informatik verwendet werden, um eine Teilauswertung anzuwenden, wenn nicht alle Argumente einer Funktion verfügbar sind.

Äquivalenz und Reduktion

Der Lambda-Kalkül ist ein Rewrite-System, das nur aus wohlgeformten Lambda-Ausdrücken besteht. Die Bedeutung dieser Ausdrücke hängt davon ab, wie sie auf einfachere Ausdrücke reduziert werden können.

Wir unterscheiden 3 Arten der Reduzierung:

• α-Umwandlung: Ändern von gebundenen Variablen;
• β-Reduktion: Anwendung einer Funktion auf ihre Argumente:
• η Umwandlung: erklärt den Begriff von Dehnbarkeit Fest.

Der Lambda-Kalkül kann daher als eine Theorie angesehen werden, die die Ähnlichkeit zwischen Lambda-Termen untersucht. Um ein Semester zu gehen trainieren, kann man die β-Gleichheit (notiert als ${displaystyle =_{eta }}$), eine Reihe von Axiomen, auf denen die obigen Reduktionstypen basieren.

Die Beziehung ${displaystyle =_{ eta }Teilmenge Lambda imes Lambda }$ wird durch die folgenden Axiome definiert:

β	${displaystyle (lambda x.M)N=_{eta}[N/x]M}$	Die β-Reduktion drückt den Anwendungsgedanken aus: Ersetzen der formalen Parameter durch die tatsächlichen Parameter. Dies ist das grundlegende Axiom des Lambda-Kalküls.
α	${displaystyle Lambda x.P=_{ eta }Lambda y.[y/x]P}$ wenn ${Anzeigestil Jot in VV(P)}$	Das Alpha-Axiom weist darauf hin, dass der Name des Formalparameters in einer Funktionsdefinition unwichtig ist und ersetzt werden kann.
reflexiv	${displaystyle M=_{ eta }M}$
transitiv	${displaystyle M=_{ eta }Nwedge N=_{ eta }LRrightarrow M=_{ eta }L}$
symmetrisch	${displaystyle M=_{ eta }NRRechtspfeil N=_{ eta }M}$
kongruent	${displaystyle M=_{ eta }M'Rightarrow lambda x.M=_{ eta }lambda x.M'}$	In einer Abstraktion können wir die Vorschrift reduzieren.
kongruent	${displaystyle M=_{ eta }M'Rightarrow MP=_{ eta }M'P}$	Wir können den ersten Teilausdruck einer Anwendung reduzieren, bevor wir die Anwendung selbst reduzieren.
kongruent	${displaystyle P=_{ eta }P'Rechtspfeil MP=_{ eta }MP'}$	Wir können den ersten Teilausdruck einer Anwendung reduzieren, bevor wir die Anwendung selbst reduzieren.

Die β-Gleichheit ist a Äquivalenzrelation, wie durch die Eigenschaften angegeben Reflexivität, Transitivität und Symmetrie und wird notiert als ${displaystyle =_{eta }}$. Bei der Anwendung des Alpha-Axioms kann man sich entscheiden, genauer zu sein und dies mit . zu schreiben ${displaystyle =_{alpha }}$. Die η-Reduktion kann analog erfolgen wie ${displaystyle =_{eta }}$ geschrieben sein.

Die Axiome, die die Äquivalenzrelation bestimmen (insbesondere Reflexivität, Transitivität und Symmetrie) gehören nicht wirklich dazu Biene die β-Gleichheit und werden als Gleichheitsaxiome bezeichnet, nicht zu verwechseln mit α-, β- und η-Gleichung. Auch die Kongruenzregeln (auch Kompatibilitätsregeln genannt) gehören nicht wirklich dazu Biene die β-Gleichheit, sondern sind unabhängige Axiome, die die Basis für die η-Reduktion bilden. Dennoch werden diese Axiome wie oben oft mit der β-Gleichheit erwähnt. Wir können daher die Notation ${displaystyle =_{eta }}$ benutzen.

α-Umwandlung

Alpha-Konvertierung ermöglicht das Umbenennen von gebundenen Variablen. Wir können zum Beispiel ${Anzeigestil Lambda x.x}$ ändern ${Anzeigestil Lambda q.q}$. Lambda-Ausdrücke, die nach Anwendung einer oder mehrerer α-Umwandlungen gleich werden, werden als α-Äquivalent bezeichnet.

Bei der α-Wandlung sind die bestehenden Anleihen zu berücksichtigen. Nur die Vorkommen der Variablen, die durch eine bestimmte Bindung (Abstraktion) gebunden sind, müssen umbenannt werden. Außerdem ist eine α-Umwandlung nur dann möglich, wenn keine freien Variablen gebunden wären.

Auswechslung im Lambda-Kalkül verwendet die α-Konvertierung, um zu vermeiden, dass freie Variablen gebunden werden.

β-Reduktion

Das Beta-Axiom wird als grundlegendes Axiom des Lambda-Kalküls angesehen und beschreibt die Anwendung einer Funktionsanwendung.

In der Informatik wird die Funktionsanwendung dadurch realisiert, dass die Formalparameter in der Funktionsanweisung durch die Aktualparameter ersetzt werden. Wir können dies anhand eines Beispiels aus der Mathematik konkret darstellen: Nehmen wir die Quadratfunktion ${Anzeigestil f(x)=x^{2}}$. Der Formalparameter in dieser Funktion ist ${Anzeigestil x}$ (in der Mathematik wird dies als veränderlich oder variabel bezeichnet). Nun wollen wir diese Funktion auf den Wert anwenden ${Anzeigestil 4}$ (der aktuelle Parameter), dann tragen wir diesen Wert in die Funktionsregel ein. Wir bekommen ${Anzeigestil f(4)=4^{2}=16}$. Das Beta-Axiom spiegelt diese Situation wider: ${displaystyle (lambda x.M)N=_{eta}[N/x]M}$ ermöglicht die Anwendung der Funktion (im Lambda-Kalkül können wir nicht wirklich von einer Funktion sprechen, sondern nur von einem Lambda-Term) ${Anzeigestil M}$ auf der Streit (gleich) ${Displaystil N}$ für wo ${Anzeigestil x}$ ist der Formalparameter.

Einige Beispiele:

${displaystyle (lambda x.x)M=_{eta}M}$	Wenn wir ${Anzeigestil xx}$ sollte ersetzt werden durch ${Anzeigestil M}$, natürlich bekommen wir ${Anzeigestil M}$.
${displaystyle (lambda f.fa)(lambda g.gb)=_{eta}(lambda g.gb)a=_{eta}ab}$	Dieses Beispiel zeigt, dass im Lambda-Kalkül jeder Begriff auf jeden (anderen) Begriff angewendet werden kann, unabhängig von der Bedeutung dieser Begriffe. Schließlich hat der Lambda-Kalkül keine Vorstellung von Bedeutung und kennt nur Lambda-Begriffe. Es heißt, dass Funktionen erste Klasse (Bürger) sind: Sie sind nicht nur anwendbare (Sprach-)Komponenten, sondern auch eigenständige Objekte, die für Berechnungen verwendet werden können.
${displaystyle (lambda x.y)M=_{eta}y}$	Die Reduzierung eines Redex bedeutet nicht immer, dass das Argument Teil des resultierenden Ausdrucks ist. Die reduzierte Funktion ist eine konstante Funktion, die immer ${Anzeigestil y}$ kehrt zurück. beachten Sie, dass ${displaystyle(lambda x.y)M}$ sollte nicht einfach geschrieben werden als ${Anzeigestil y}$! Dies ist nur zulässig, nachdem die Anwendung der Funktion auf ein Argument reduziert wurde.

Die Anwendung einer Abstraktion auf einen anderen Begriff ist eigentlich eine Sondersituation im Lambda-Kalkül. In diesem Fall wird ein Begriff erzeugt, der als Redex bezeichnet wird (als Abkürzung von rotKabel ExDruck) und auf die eine Kürzung angewendet werden kann. In diesem Fall wird eine solche Reduktion als β-Reduktion bezeichnet. Der Redex reduziert sich dann auf den gebundenen Term der Abstraktion (z. ${Anzeigestil M}$ im ${Displaystil Lambda x.M}$) enthält die gebundene Variable (de ${Anzeigestil x}$ im ${Displaystil Lambda x.M}$) durch den Begriff ersetzt, auf den die Abstraktion angewendet wurde. Dabei kommt es auf Folgendes an:

${displaystyle (lambda x.M)N=_{eta}[N/x]M}$.

Dies wird auch als Grundaxiom des Lambda-Kalküls bezeichnet.

η Umwandlung

Ètaconversion defines fängt den Begriff der Extensionalität ein, mit anderen Worten, dass zwei Funktionen gleich sind dann und nur dann, wenn sie liefern für jedes mögliche Argument das gleiche Ergebnis.

Darstellung der Datentypen

Obwohl der Lambda-Kalkül nur Lambda-Terme kennt, ist er dennoch so ausdrucksstark wie die gewöhnliche Mathematik. Für jeden darstellbaren Datentyp (zB Zahlen und boolesche Werte) lassen sich zwei Arten von Termen unterscheiden: Zum einen die Lambda-Terme (Kombinatoren), die die Werte eines Datentyps selbst repräsentieren, zum anderen die Andererseits gibt es Kombinatoren, die die Operationen an diesen Datenwerten durchführen. Mittels -Reduktion kann die Korrektheit dieser Kombinatoren leicht überprüft werden. Mit diesem System können die Datentypen und die Operationen auf diesen Datentypen simuliert werden. Oft sind jedoch mehrere Datendarstellungen möglich. In diesem Abschnitt geben wir einige Beispiele für Datentypen und wie sie im Lambda-Kalkül codiert werden können, sowie einige Beispiele für Operationen mit diesen Datentypen.

Eines ist jedoch zu beachten: Der hier verwendete Lambda-Kalkül ist nicht typisiert. Es kann also nicht verlangt werden, dass ein bestimmter Ausdruck nur auf bestimmte andere Ausdrücke angewendet werden kann. Dies erfordert ein gewisses System. So können wir den Kombinator perfekt nutzen ${displaystyle PLUS}$ auf zwei Boolesche Werte anwenden, aber das Ergebnis ist nutzlos. Es ist also durchaus möglich, Datentypen mit Lambda-Termen darzustellen, aber die verwendeten Kombinatoren haben eigentlich keine feste Bedeutung an sich und können für alles Mögliche verwendet werden. Nur weil wir bestimmten Kombinatoren eine bestimmte Semantik zuweisen, sind die generierten Datentypen und die Operationen mit diesen Datentypen nützlich.

Boolesche Werte

Eine häufig verwendete Darstellung für boolesche Werte (${displaystyle WAHR}$ und ${displaystyle FALSE}$) sind die Booleschen Werte der Kirche. Diese sind wie folgt definiert:

${displaystyle TRUEequiv lambda t.lambda f.t}$
${displaystyle FALSEequiv lambda t.lambda f.f}$

${displaystyle WAHR}$ ist eine Funktion, die bei zwei Argumenten immer ihr erstes Argument zurückgibt, ${displaystyle FALSE}$ ist eine Funktion, die immer ihr zweites Argument zurückgibt.

Mit diesen Darstellungen können die Booleschen Operatoren wie folgt dargestellt werden:

• Logische Konjunktion

${displaystyle ANDequiv lambda b_{1}lambda b_{2}.b_{1} b_{2} FALSE}$

• Logische Disjunktion

${displaystyle ORequiv Lambda b_{1}.lambda b_{2}.b_{1} TRUE b_{2}}$

• Logische Negation

${displaystyle NOTEquiv Lambda b.b FALSE TRUE}$

Die Operationen auf booleschen Werten machen sich die Tatsache zunutze, dass ${displaystyle WAHR}$ und ${displaystyle FALSE}$ immer ein bestimmtes Argument zurückgeben.

Paare

Auch Paare (zwei Tupel) lassen sich im Lambda-Kalkül leicht darstellen. Ein Paar ist ein Datentyp, der konstruiert werden kann mit ${displaystyle CONS}$. Diese Funktion verwendet zwei Argumente und generiert ein Tupel, wobei das erste Argument an der ersten Position und das zweite Argument an der zweiten Position des Tupels steht. Mit Hilfe von Projektionen lassen sich diese Argumente dann aus dem Tupel zurückgewinnen. In einigen Programmiersprachen, wie zum Beispiel planen, wird zur ersten Projektion ${Display-Stil AUTO}$ genannt und die zweite Projektion ${Displaystil-CDR}$.

• Datenkonstruktor

${displaystyle CONSequiv lambda f.lambda s.lambda b.b f s}$

• Erste Projektion

${displaystyle CARequiv Lambda p.p. TRUE}$

• Zweite Projektion

${displaystyle CDRequiv Lambda p.p FALSE}$

In dieser Darstellung kann man sich ein Paar als Funktion eines Arguments vorstellen, das bei einem gegebenen booleschen Wert diesen booleschen Wert verwendet, um das richtige Element aus dem Paar zurückzugeben. Die Projektionsfunktionen liefern den korrekten booleschen Wert. Es ist daher beabsichtigt, dass ${displaystyle CONS}$ nur die ersten beiden Argumente werden für die Konstruktion eines Paares übergeben. Diese Teilanwendung wird durch Currying ermöglicht.

Natürliche Zahlen

In der Lambda-Kalküle natürliche Zahlen meist durch sogenannte Kirchennummern, auch Kirchennummern genannt, dargestellt. Mit diesen von Alonzo Church entwickelten Kirchenziffern ist es einfach, die Grundrechenarten im Lambda-Kalkül zu demonstrieren.

Eine natürliche Zahl wird durch einen bestimmten Begriff dargestellt, ${Anzeigestil s}$ (Nachfolger), mehrfach auf einen Basisterm anzuwenden ${Anzeigestil z}$ (Null).

Lass für jeden ${displaystyle n}$, ${Anzeigestil (.)^{n}.}$ eine Metaoperation sein, die zwei Ausdrücke benötigt (zum Beispiel ${Anzeigestil F}$ und ${Anzeigestil M}$) und erlaubt die Verwendung des Begriffs ${displaystyle FFFFldots FM}$ kurz schreiben als ${Anzeigestil (F)^{n}M}$, bei welchem ${Anzeigestil F^{0}(M)=M}$ und ${Anzeigestil F^{n 1}(M)=F(F^{n}(M))}$.

Mit dieser Notation können die Kirchennummern wie folgt definiert werden:

${displaystyle c_{n}äquiv Lambda s.lambda z.(s^{n})z}$, mit ${displaystyle nin mathbb {N} }$.

Die ersten natürlichen Zahlen sehen dann so aus:
${displaystyle 0equiv lambda s.lambda z.z}$
${displaystyle 1equiv Lambda s. Lambda z.s z}$
${displaystyle 2equiv lambda s.lambda z.s(s z)}$
...

Bei dieser numerischen Darstellung können mehrere Operatoren definiert werden. Es gibt verschiedene Möglichkeiten, diese Operatoren zu definieren. Die Konstruktion dieser Operatoren sorgt dafür, dass das Ergebnis nach der Anwendung wieder eine Kirchennummer ist.

• Die Nachfolgefunktion: ${displaystyle succ(n)=n 1}$

${displaystyle SUCCequiv lambda n.lambda s.lambda z.s(n s z)}$

• Die Zugabe: ${displaystyle plus(m,n)=mn}$

${displaystyle PLUSequiv lambda m.lambda n.lambda s.lambda z.m s (n s z)}$

• Die Multiplikation: ${displaystyle mult(m,n)=mcdot n}$

${displaystyle MULTequiv Lambda m.lambda n.m (PLUS n) 0}$

• Die Vorgängerfunktion: ${displaystyle pred(n)=n-1}$ mit ${displaystyle pred(0)=0}$

${displaystyle Zequiv PAAR 0 0}$

${displaystyle Sequiv Lambda p.CONS(CDR p)(PLUS 1(CDR p))}$

${displaystyle PREDequiv Lambda n.CAR(n S Z)}$

• Der Abzug: ${Anzeigestil min(m,n)=m-n}$ wenn ${displaystyle n$, dann ist ${Anzeigestil min(m,n)=0}$.

${displaystyle MINequiv lambda m.lambda n.n PRED m}$

Diese Funktionen sind Beispiele dafür, wie einfache arithmetische Operationen im Lambda-Kalkül definiert werden können. Mit Ausnahme von ${Anzeigestil PRED}$ Diese Funktionen sind ganz einfach.

${Anzeigestil PRED}$ verwendet Paare, um den Vorgänger einer Zahl zu berechnen. Dies funktioniert iterativ. Jedes Paar enthält zwei Zahlen, an erster Stelle steht der Vorgänger der Zahl an zweiter Stelle. Nach dem ${displaystyle n}$ mal durch Erhöhen der zweiten Stelle und Verschieben des alten Wertes an die erste Stelle des Paares, an der ersten Stelle des Paares findet man die notwendige Zahl, nämlich ${Anzeigestil n-1}$.

Standard-Combiner und Barendregt-Arithmetik

Im vorherigen Abschnitt haben wir gesehen, dass wir im Lambda-Kalkül mit natürlichen Zahlen in Form von Kirchenzahlen rechnen können. Wir haben gesehen, dass es möglich ist, Begriffe zu definieren, die es ermöglichen, bestimmte arithmetische Operationen an Kirchenziffern durchzuführen.

Kirchenzahlen sind clever, aber ein bisschen schwierig zu handhaben, wenn man über das reine Rechnen mit natürlichen Zahlen hinausschauen möchte. Im 1979 eingeführt Henk Barendregt eine neue Schreibweise für die Berechnung innerhalb des Lambda-Kalküls, die sich leichter für andere Berechnungsformen eignet. Um das Gefühl weiterzuentwickeln, dass man mit dem untypisierten Lambda-Kalkül in jede Richtung gehen kann, werden wir einige Begriffe diskutieren, die Barendregt auf diese Weise erfunden hat.

Zunächst definieren wir einige Kombinatoren, Lambda-Terme ohne freie Variablen, die beim Rechnen mit Lambda-Termen nach Barendregt wichtig sind:

• ${displaystyle {mathfrak {I}}=_{eta}lambda x.x}$: der Identitätskombinierer; gilt für jeden Lambdaterm M ${displaystyle {mathfrak {I}}M=_{eta}M}$
• ${displaystyle {mathfrak {K}}=_{eta}lambda xy.x}$: die linke Funktion; gilt für alle Lambdaterme M und N ${displaystyle {mathfrak {K}}MN=_{eta}M}$
• ${displaystyle {mathfrak {K}}_{*}=_{eta}lambda xy.y}$: die richtige Funktion; gilt für alle Lambdaterme M und N ${displaystyle {mathfrak {K}}_{*}MN=_{eta}N}$
• ${displaystyle {mathfrak {S}}=_{eta}lambda xyz.xz(yz)}$

Eine ganz besondere Stellung im System von Barendregt nimmt zudem der Fixpunkt-Combiner ein. De introductie van de dekpuntcombinator heeft de gehele lambdacalculus veranderd. We zullen de dekpuntcombinator hier alleen maar introduceren; verderop zullen we hem uitgebreid bespreken, samen met een beschouwing van wat het bestaan ervan betekent voor de lambdacalculus. De dekpuntcombinator Y is als volgt gedefinieerd:

• ${displaystyle mathbb {Y} =_{eta }lambda f.(lambda x.f(xx))(lambda x.f(xx))}$

Barendregt heeft met de bovenstaande combinatoren een redelijk gemakkelijk te begrijpen systeem van termen geïntroduceerd die in uitdrukkingskracht bewijsbaar gelijk zijn aan de turingmachine. 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.

De twee soorten termen die nodig zijn om een taal te maken die evenveel uitdrukkingskracht heeft als een turingmachine, zijn de repetitie en de selectie. De repetitie is een term die subtermen herhaalt, een loop in termen van een imperatieve programmeertaal. De selectie is een term die een keuze maakt tussen twee mogelijke deeltermen.

Op de repetitie komen we verderop terug. Voor de selectie bedacht Barendregt het volgende, gebaseerd op de veelvoorkomende vorm van een selectie bij de imperatieve talen: als B dan M anders N. Hierin is B een criterium dat evalueert tot een element van de bekende verzameling van George Boole${displaystyle {True,False}}$. Als B evalueert tot true wordt M gekozen, als B evalueert tot false wordt N gekozen. Barendregt bedacht dus dat de codering hiervan in de lambdacalculus de volgende vorm moest hebben:

${displaystyle lambda f.fMN}$

die hij afkortte tot het geordende paar

${displaystyle [M,N]}$.

Barendregt bedacht hiermee dat hij een criterium dat tot True evalueert zou coderen als een term die, gevoed met twee andere termen, als resultaat de eerste van zijn twee argumenten op zou leveren. En een criterium dat tot False evalueert zou dan het tweede op moeten leveren. Gegeven de speciale aandacht die we hebben gegeven aan de bovengenoemde combinatoren, zal het de oplettende lezer niet verbazen dat Barendregt True codeerde als de term ${displaystyle {mathfrak {K}}}$ en de term "False" als ${displaystyle {mathfrak {K}}_{*}}$. Immers:

${displaystyle [M,N]True =_{ eta } (lambda xy.x)MN =_{ eta } M}$

${displaystyle [M,N]False =_{ eta } (lambda xy.y)MN =_{ eta } N}$

Hoe handzaam deze notatie is, blijkt uit de grote hoeveelheid zaken die ermee weergegeven kunnen worden. Zo bedacht Barendregt dat hij natuurlijke getallen kon coderen met deze notatie, analoog aan de eerder besproken Churchnumeralen. In plaats van algemene termen f en x te gebruiken, gebruikte Barendregt echter een vaste terminologie voor de herhaalde f en de x:

Afkorting: ${displaystyle lceil nceil }$ staat voor de weergave in Barendregtnotatie van het cijfer n

${displaystyle lceil 0ceil ={mathfrak {I}}}$

${displaystyle lceil n 1ceil =[{mathfrak {K}}_{*},lceil nceil ]}$

Om aan te geven hoe veelzijdig deze notatie van Barendregt is en om het gevoel te kweken dat het een notatie is met een enorme uitdrukkingskracht, zullen we een drietal operaties bespreken die Barendregt op zijn notatie bedacht heeft. Twee van deze notaties zijn rekenkundig, om aan te geven dat Barendregts notatie voor natuurlijke getallen rekenen toestaat. De derde is een term die vaststelt of een bepaald getal gelijk is aan 0, een booleaanse functie dus, die true of false oplevert.

• Optelling in Barendregts notatie gaat met de term ${displaystyle S^{ }}$ (successor), een term zo dat ${displaystyle S^{ }lceil nceil =lceil n 1ceil }$. Deze term is ${displaystyle S^{ }=_{eta }lambda x.[{mathfrak {K}}_{*},x]}$; dat dit inderdaad de optelling is, is triviaal zichtbaar.
• Aftrekken in Barendregts notatie gaat met de term ${displaystyle P^{-}}$ (predecessor), een term zo dat ${displaystyle P^{-}lceil n 1ceil =lceil nceil }$. Deze term is ${displaystyle P^{-}=_{eta }lambda x.x{mathfrak {K}}_{*}}$; immers, False als argument aan een tupel geven levert de rechterterm van dat tupel op en de rechterterm van een getal in Barendregts notatie is de directe voorganger van dat getal. Merk ook op dat het niet werkt voor 0; dit klopt ook precies, want 0 heeft geen voorganger in de natuurlijke getallen.
• De functie ZERO van Barendregt is een term zo dat ${displaystyle ZEROlceil 0ceil =True}$ en ${displaystyle ZEROlceil n 1ceil =False}$. Deze term is ${displaystyle ZERO=_{eta }lambda x.x{mathfrak {K}}}$; immers
  • ${displaystyle ZEROlceil 0ceil =_{ eta }(lambda y.y){mathfrak {K}}=_{ eta }{mathfrak {K}}=_{eta }True}$
  • ${displaystyle ZEROlceil n 1ceil =_{ eta }[{mathfrak {K}}_{*},lceil nceil ]{mathfrak {K}}=_{ eta }{mathfrak {K}}_{*}=_{eta }False}$

Naast een mechanisme om een keuze te maken tussen twee deeltermen gebruikte Barendregt ook een termenmechanisme dat herhaling van deeltermen mogelijk maakt. Hiermee breidde hij zijn notatiesysteem uit tot het bereik qua uitdrukkingskracht van de turingmachine. Barendregt maakte daarvoor gebruik van een bijzonder soort herhaling, die binnen de lambdacalculus echter vaak gebruikt wordt: de recursie, het definiëren van een term A waarbij A een deelterm is van zichzelf.

Als voorbeeld hiervan bespreken we een mogelijkheid om twee natuurlijke getallen op te tellen, die bestaat uit een recursieve functie. Stel dat we de getallen A en B bij elkaar op willen tellen. Nemen we aan dat ${displaystyle Bot =0}$, dan kunnen we deze twee getallen optellen door B over te hevelen naar A; als ${displaystyle Bot =0}$, dan:

${displaystyle A B=(A 1) (B-1)}$

Is B wel gelijk aan 0, dat is de uitkomst A en zijn we klaar. We zouden dus als volgt een optelalgoritme kunnen maken:

ADD.A.B = ALS B = 0 DAN A ANDERS ADD.(A 1).(B-1)

Barendregt introduceerde herhaling in zijn lambdacalculus door gebruik te maken van dit soort recursie.

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. Na een paar vertalingen met behulp van η-gelijkheid zal de lezer meemaken dat zijn vertaling van voren af aan begint. Als directe vertaling toegepast wordt, wordt de vertaling dus een oneindig lange rij lambda's. Een vertaling is echter wel mogelijk als we opmerken dat we op zoek zijn naar een uitdrukking dusdanig dat

ADD = ALS.ADD

waarbij we de lambdanotatie een beetje misbruiken; we zoeken dus een uitdrukking dusdanig dat ADD een term is gelijk aan de ALS-term toegepast op ADD. Om redenen die we verderop uiteen zullen zetten, kan een dergelijke term uitgerekend worden; zij is gelijk aan

${displaystyle ADD XY=_{eta }mathbb {Y} {mbox{ALS Y = 0 DAN X ANDERS a }}(S^{ }X)(P^{-}Y)}$

waarmee ook het enorme belang van de dekpuntcombinator binnen de lambdacalculus duidelijk wordt.

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. Niet alleen de basisbewerkingen, maar ook datastructuren als lijsten en de bijbehorende bewerkingen passen op natuurlijke wijze in dit schema.

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. Beginnend bij de dagen dat het nodig werd zakken graan te tellen tot aan het in een bepaalde windrichting richten van tempels en piramiden, van het voorspellen van overstromingen van de Nijl tot aan de prachtigste architectuur, wiskunde heeft altijd een rol gespeeld.

Sinds de hoogtijdagen van de oude, Griekse beschavingen zijn er ook mensen geweest die niets anders deden dan zich intellectueel richten op de uitbreiding van de wiskundige kennis en het begrijpen van hoe het rekenen in zijn werk gaat: de wiskundigen. Hun inspanningen waren echter tot aan het einde van de 17e eeuw niet aan te merken als een verbonden geheel – het was meer een lappendeken van losse inspanningen en hier en daar een paar inzichten.

Vanaf 1675 begon dat allemaal te veranderen met de publicaties van Gottfried Leibniz. Hij begon voor het eerst vragen te stellen over de diepere structuur van de wiskunde, te zoeken naar een systeem in het geheel van inzichten en kennis dat zo langzamerhand opgebouwd was. Hij stelde als ideaalbeeld een universele taal voor waarin alle wiskundige problemen uitgedrukt konden worden en een universele methode waarmee al deze problemen opgelost konden worden. Leibniz stierf in 1716 en zijn opvolgers, waaronder George Boole, bleven druk zoeken naar antwoorden op zijn vragen.

Rond 1877 publiceerde Georg Cantor zijn werk over verzamelingenleer. Het was het begin van een serie aardverschuivingen in de wiskunde die tot 1950 zou duren en het wezen van de wiskunde voor eeuwig zou veranderen. Met de verzamelingenleer, na aanpassingen door Ernst Zermelo en Adolf Fraenkel, was Leibniz' universele taal geboren.

Het vraagstuk van de universele methode bleef echter langer open. David Hilbert nam het vraagstuk der berekening op in zijn lijst van uitdagingen aan de wiskunde van 1900. In 1931 maakte Kurt Gödel een ruw einde aan Leibniz' droom door te bewijzen dat sommige dingen niet berekenbaar zijn in de universele taal van de wiskunde. Sterker nog, hij bewees dat in iedere, universele taal zaken moeten zitten die onberekenbaar zijn.

Na Gödels onthutsende ontdekking maakte het probleem van berekening plaats voor het probleem van beslisbaarheid, inmiddels bekend als het Entscheidungsproblem: het probleem van het bepalen of iets berekenbaar is of niet. Dit probleem kon niet direct beantwoord worden, want eerst moest bepaald worden hoe een berekening precies plaatsvond.

Lambdacalculus en de turingmachine

In 1936 volgden twee antwoorden op het openstaande probleem van berekenbaarheid: de turingmachine van Alan Turing en de lambdacalculus van Alonzo Church. Beide zijn absolute modellen van berekening.

Zoals eerder uiteengezet, is het in de lambdacalculus mogelijk zowel de selectie- als de herhalingsfunctie van de turingmachine te modelleren. Ook is het mogelijk, door middel van het doorgeven van argumentwaarden van de ene functieaanroep naar de volgende, de toestand bij te houden. Hiermee wordt de lambdacalculus in uitdrukkingskracht gelijk aan de turingmachine, die in feite niets anders doet dan het eindeloos herhalen van de slag "lees de toestand uit, kies een reactie om uit te voeren, voer hem uit, ga verder".

De turingmachine werd rond 1936 ontwikkeld door Alan Turing als antwoord op het Entscheidungsproblem van Leibniz, Hilbert en Gödel: het is een model van berekening waarin bepaald kan worden of een probleem opgelost kan worden of niet. Sindsdien is het algemeen geaccepteerd dat de uitdrukkingskracht van deze machine overeenkomt met hetgeen berekenbaar is, hoewel dat niet bewijsbaar is. Vrijwel onmiddellijk na de introductie van de Machine begon er een trans-Atlantisch touwtrekken tussen Turing en Alonzo Church, bedenker van de lambdacalculus, om wiens mechanisme het meest algemeen was. De briefwisseling tussen de twee nam de vorm aan van A stuurt B een algoritme uitgedrukt in zijn mechanisme, B reageert met een equivalente uitwerking in zijn mechanisme. In 1938 was Turing het zat en publiceerde hij een algemeen mechanisme om turingmachines te vertalen in lambdacalculus en omgekeerd. Sindsdien twijfelt niemand er meer aan dat de beide mechanismen totaal verschillend en geheel equivalent zijn.

Tegelijkertijd zijn beide mechanismen een bedroevend antwoord op het beslissingsprobleem: niet alle problemen zijn beslisbaar. Het antwoord van Turing was een machine die oneindig door zou kunnen lopen, het antwoord van Church een term die eindeloos groter wordt, of een die gelijk van grootte blijft, en nooit convergeert tot een eindterm:

1. ${displaystyle (lambda x.xx)(lambda x.xx)Rightarrow _{ eta }(lambda x.xx)(lambda x.xx)}$
2. ${displaystyle (lambda x.xxx)(lambda x.xxx)Rightarrow _{ eta }(lambda x.xxx)(lambda x.xxx)(lambda x.xxx)}$

De equivalentie van de twee mechanismen heeft grote gevolgen gehad. Met name van belang voor de lambdacalculus is dat zij niet verdwenen is toen het turingmodel het model van de algemeen bekende computer werd. De elegantie in combinatie met kracht van de lambdacalculus zorgt er niet alleen voor dat er voortgaand onderzoek aan gedaan wordt en dat de lambdacalculus zich een plaats heeft gewonnen als achterliggend model voor een hele klasse van eigen programmeertalen naast de op de turingmachine gebaseerde talen, maar dat de lambdacalculus naast de turingmachine een basis is geworden voor het menselijk begrip van berekenbaarheid, uitdrukkingsmechanisme en van het wezen van de wiskunde als geheel. Uiteenlopend van de basisrekenkunde tot de formalismen van taalvorming en beschouwingen over compleetheid en consistentie van de formele talen is de lambdacalculus een mechanisme waarop wetenschappers steeds weer teruggrijpen om hun begrip aan op te hangen en om hen door het onbekende gebied van het wiskundig onderzoek te leiden naar nieuwe inzichten en dieper begrip van de wiskundige realiteit.

Tarski en Knaster

In 1955 publiceerden Alfred Tarski en Bronislaw Knaster een cruciaal gebleken artikel over dekpunten. Hun werk maakte het voor onderzoekers in de lambdacalculus mogelijk een hoge vlucht te nemen door recursie in de lambdacalculus te integreren als model van berekening.

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. Daarvoor baseerden zij zich op de dekpunten van Tarski en Knaster. 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.

De dekpuntcombinator

Gegeven is een functie ${displaystyle f:Vightarrow V}$.Een dekpunt van f is een element ${displaystyle vin V}$ zo dat ${displaystyle f(v)=v}$.

In 1955 bewezen Tarski en Knaster het volgende:

Zij ${displaystyle V}$ een partieel geordende verzameling

Zij ${displaystyle f:Vightarrow V}$ een functie die de ordening op V in stand houdt

Zij het ook zo dat iedere, eindige deelverzameling van V een supremum en een infimum heeft

Dan is de verzameling van dekpunten van f in V een verzameling

die niet leeg is

die partieel geordend is

waarvan iedere, eindige deelverzameling een supremum en een infimum heeft.

Het belang hiervan voor de lambdacalculus is evident en in het voorgaande al gedemonstreerd: voor een interessante klasse van termen is het mogelijk een dekpunt te vinden en zo een recursieve functie te definiëren.

In 1969 kwamen Park en Landin met onthutsend nieuws, dat in eerste instantie niet zo slecht leek. In de lambdacalculus bestonden er namelijk wel veel meer dekpunten dan beschreven door Tarski en Knaster. Sterker nog, Park en Landin bewezen dat in de lambdacalculus voor iedere term F een dekpunt bestond:

${displaystyle forall _{Fin Lambda }(exists _{Xin Lambda }:(FX=_{ eta }X))}$

Bewijs:

Definieer ${displaystyle W=_{eta }lambda x.F(xx)}$ en ${displaystyle X=_{eta }WW}$

Dan ${displaystyle X=_{eta }WW=_{eta }(lambda x.F(xx))W=_{ eta }F(WW)=_{eta }FX}$

Sterker nog, er is een combinator die, voor iedere term F, een dekpunt oplevert:

Definieer ${displaystyle Y=_{eta }lambda f.(lambda x.f(xx))(lambda x.f(xx))}$

Dan ${displaystyle forall _{Fin Lambda }(F(YF)=_{ eta }YF)}$

Bewijs:Schrijf de rechterkant uit – uit de voorgaande stelling volgt dan deze stelling

Merk op dat de dekpuntcombinator de droom is van iedereen die met recursie werkt: vul een functie of vergelijking in en hij wordt recursief opgelost.

Op zich klinkt hier niets slechts aan. Sterker nog, het bovenstaande klinkt als geweldig nieuws: alles wat je maar bedenken kunt, is op te lossen. Echter, Park en Landin wezen erop dat hun dekpuntcombinator een zeer onaangename eigenschap van de lamdacalculus aantoonde. Beschouw namelijk de functie

${displaystyle succ:mathbb {R} ightarrow mathbb {R} }$

${displaystyle succ(r)=r 1}$

Intuïtief zal duidelijk zijn: deze functie heeft geen dekpunt. Er is geen reëel getalr zo dat r 1 = r. Met de dekpuntcombinator is een dergelijke waarde er echter wel.

Het is nu verleidelijk te zeggen dat dit betekent dat de lambdacalculus dus te veel kan. Maar de realistische kijk op de ontdekking van Park en Landin is niet dat de lambdacalculus te sterk is, maar dat de lamdacalculus bepaalde dingen gewoon verkeerd doet. Bepaalde aspecten van de lambdacalculus zijn onwenselijk. De lambdacalculus is geen goed model van berekening.

Het probleem

Het probleem dat door Landin en Park aan de oppervlakte gebracht werd, heeft kort door de bocht de volgende oorzaak: de lambdacalculus heeft geen concept van het idee dat bepaalde termen niet op andere termen mogen worden toegepast.

Blijven we even bij het voorbeeld van de successorfunctie van hierboven, dan merken we op dat de dekpuntcombinator voor deze functie een dekpunt oplevert. Kijken we wat indringender naar dit dekpunt, bijvoorbeeld met behulp van de eerder gegeven definitie van succ, dan merken we het volgende op: het gevonden dekpunt is weliswaar een dekpunt gegeven de definitie van succ, maar het dekpunt is niet een getal zoals wij getallen gedefinieerd hadden. Het was nooit onze bedoeling succ toe te passen op een term van de vorm van het gevonden dekpunt.

Het ontbeert de ongetypeerde lambdacalculus dus aan een manier om aan te geven dat bepaalde termen niet van toepassing zijn op bepaalde andere termen. Of, omgekeerd, om aan te geven op welke termen een gegeven term wel toegepast mag worden.

Het antwoord op het probleem van Park en Landin kwam al snel, met de introductie van nieuwe soorten lambdacalculus, calculi die wel een manier hadden om aan te geven welke combinaties wel en niet toegestaan zijn. Deze calculi maken gebruik van schema's om, bij een term, de vorm van toegestane argumenten aan te geven. Er zijn veel specifieke soorten van dit soort schema's, maar als verzamelnaam worden deze schema's typesystemen genoemd. Hun combinatie met de lambdacalculus resulteerde in wat wij tegenwoordig de getypeerde lambdacalculus noemen.

Externe bronnen

• Henk Barendregt & Erik Barendsen, Introduction to Lambda Calculus, Revised edition October 1994
• Henk Barendregt & Erik Barendsen, Introduction to Lambda Calculus, Revised edition December 1998, March 2000
• Mark Scheffer, The theory of the foundations of mathematics – 1870 to 1940, maart 2002