Church-Kodierung

Church-Kodierung

Unter Church-Kodierung versteht man die Einbettung von Daten und Operatoren in den Lambda-Kalkül. Die bekannteste Form sind die Church-Numerale, welche die natürlichen Zahlen repräsentieren. Benannt sind sie nach Alonzo Church, der Daten als Erster auf diese Weise modellierte.

Inhaltsverzeichnis

Church-Numerale

Definition

Die Grundidee zur Kodierung beruht auf den Peano-Axiomen, wonach die natürlichen Zahlen durch einen Startwert - die 0 - und einer Nachfolger-Funktion definiert sind. Demnach sind die Church-Numerale wie folgt definiert:

0λf.λx. x
1λf.λx. f x
2λf.λx. f (f x)
3λf.λx. f (f (f x))
...
nλf.λx. fn x

Rechnen mit Church-Numeralen

Im Lambda-Kalkül sind numerische Funktionen durch korrespondierende Funktionen über Church-Numerale darstellbar. Diese Funktionen können in funktionalen Programmiersprachen direkt durch übertragen der Lambda-Ausdrücke implementiert werden.

Die Nachfolger-Funktion wird wie folgt definiert:

succλn.λf.λx.n f (f x)

Die Addition zweier Zahlen n und m ist die m-malige Anwendung der Nachfolger-Funktion auf n:

plusλm.λn.λf.λx. m f (n f x)

Die Multiplikation zweier Zahlen n und m ist die m-malige Anwendung der Addition (+n) auf n:

multλm.λn.λf. n (m f)

Die Vorgänger-Funktion:

predλn.λf.λx. n (λg.λh. h (g f)) (λu. x) (λu. u)

Boolesche Ausdrücke

Analog zu den natürlichen Zahlen lassen sich auch (zweiwertige) Wahrheitswerte im Lambda-Kalkül modellieren.

trueλx.λy. x
falseλx.λy. y

Daraus lässt sich auch eine einfache Kontrollstruktur (IF THEN ELSE) ableiten:

ifthenelseλb.λx.λy.b x y

Dabei ist die Variable b als Bedingung zu verstehen, x als "THEN" und y als "ELSE".


Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Church — ist der Familienname folgender Personen: Albert T. Church, Vize Admiral der US Navy Alonzo Church (1903–1995), US amerikanischer Mathematiker Arthur Herbert Church (1834–1915), britischer Autor, Maler und Chemiker Benjamin Church, General der… …   Deutsch Wikipedia

  • Church-Numeral — Unter Church Kodierung versteht man die Einbettung von Daten und Operatoren in das Lambda Kalkül. Die bekannteste Form sind die Church Numerale, welche die natürlichen Zahlen repräsentieren. Benannt sind sie nach Alonzo Church, der Daten als… …   Deutsch Wikipedia

  • Gödel-Code — Eine Gödelnummer ist eine natürliche Zahl, die einem Wort einer formalen Sprache nach einem gewissermaßen „durchschaubaren“ Verfahren – Gödelisierung – zugeordnet wird und dieses Wort eindeutig kennzeichnet. Alle über die Kodierung von Programmen …   Deutsch Wikipedia

  • Gödel-Isomorphie — Eine Gödelnummer ist eine natürliche Zahl, die einem Wort einer formalen Sprache nach einem gewissermaßen „durchschaubaren“ Verfahren – Gödelisierung – zugeordnet wird und dieses Wort eindeutig kennzeichnet. Alle über die Kodierung von Programmen …   Deutsch Wikipedia

  • Gödel-Isomorphismus — Eine Gödelnummer ist eine natürliche Zahl, die einem Wort einer formalen Sprache nach einem gewissermaßen „durchschaubaren“ Verfahren – Gödelisierung – zugeordnet wird und dieses Wort eindeutig kennzeichnet. Alle über die Kodierung von Programmen …   Deutsch Wikipedia

  • Gödel-Nummer — Eine Gödelnummer ist eine natürliche Zahl, die einem Wort einer formalen Sprache nach einem gewissermaßen „durchschaubaren“ Verfahren – Gödelisierung – zugeordnet wird und dieses Wort eindeutig kennzeichnet. Alle über die Kodierung von Programmen …   Deutsch Wikipedia

  • Gödel-Nummerierung — Eine Gödelnummer ist eine natürliche Zahl, die einem Wort einer formalen Sprache nach einem gewissermaßen „durchschaubaren“ Verfahren – Gödelisierung – zugeordnet wird und dieses Wort eindeutig kennzeichnet. Alle über die Kodierung von Programmen …   Deutsch Wikipedia

  • Gödel-Operator — Eine Gödelnummer ist eine natürliche Zahl, die einem Wort einer formalen Sprache nach einem gewissermaßen „durchschaubaren“ Verfahren – Gödelisierung – zugeordnet wird und dieses Wort eindeutig kennzeichnet. Alle über die Kodierung von Programmen …   Deutsch Wikipedia

  • Gödelisierung — Eine Gödelnummer ist eine natürliche Zahl, die einem Wort einer formalen Sprache nach einem gewissermaßen „durchschaubaren“ Verfahren – Gödelisierung – zugeordnet wird und dieses Wort eindeutig kennzeichnet. Alle über die Kodierung von Programmen …   Deutsch Wikipedia

  • Gödelnummerierung — Eine Gödelnummer ist eine natürliche Zahl, die einem Wort einer formalen Sprache nach einem gewissermaßen „durchschaubaren“ Verfahren – Gödelisierung – zugeordnet wird und dieses Wort eindeutig kennzeichnet. Alle über die Kodierung von Programmen …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”