Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenDonnerstag, 24. April 2014 

Lambda-Kalkül


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Der Lambda-Kalkül ist eine formale Sprache zur Untersuchung Funktionen . Er wurde von Alonzo Church und Stephen Kleene in den 30er Jahren eingeführt. Church benutzte den Lambda-Kalkül um eine negative Antwort auf das Entscheidungsproblem zu geben. Mittels des Kalküls kann klar definieren was eine berechenbare Funktion ist. Die Frage ob zwei Lambda-Ausdrücke äquivalent sind kann i.a. nicht algorithmisch entschieden Der Lambda-Kalkül hat die Entwicklung funktionaler Programmiersprachen insbesondere LISPs wesentlich beeinflusst.

Die übliche Notation einer mathematischen Funktion im Beispiel

 f(x) = x*x + 2*x +  

ist in dem Sinne doppeldeutig dass klar ist ob man die ganze Funktion all ihren Funktionswerten meint oder nur die an der Stelle x.

Um dies eindeutig anzugeben wird die genannte lambda-Notation (griechischer kleiner Buchstaben l) verwendet

 λx [ x*x + 2*x + ]  

Alonzo Church hat 1941 diese Notation eingeführt.

Gemeinsam mit weiteren Syntax- und Umformungsregeln diese Notation den Lambda-Kalkül : ein vollständiges System zur Beschreibung und mathematischer Berechnungen und Verfahren das im Sinne Konzepts der Berechenbarkeit ebenso mächtig ist wie beispielsweise die Programmiersprachen oder die Turing-Maschine .

Konrad Zuse hat Ideen aus dem Lambda-Kalkül 1942 - 1946 in seinen Plankalkül einfließen lassen. John McCarthy hat sie der fünfziger Jahre verwendet und damit die Funktionen der LISP -Programmiersprache definiert.

Um die oft erwähnte schlichte Eleganz Lambda-Kalkül zu verdeutlichen wird hier kurz auf Grundlagen eingegangen. Man beachte dass diese Beschreibung ein Turing-vollständiges System ist.

Inhaltsverzeichnis

Ungetypter Lambda-Kalkül

In seiner einfachsten dennoch vollständigen Form gibt es im Lambdakalkül drei von Termen (T) hier in Backus-Naur-Form :

T := a (Atom) | (T (Applikation) | λa.T (Lambda)

wobei a für ein beliebiges Symbol einer mindestens abzählbar-unendlichen Menge steht sowie zwei

  • α= (Umbenennung) ist die Substitution aller Auftreten eines Atoms in einem durch ein frisches (bisher unbenutztes) Atom.
  • β> (Reduktion) ist die Ersetzung eines der Form (λx.T S) durch T wobei mit S substituiert wird.

Wenn durch β> ein Lambda in anderes eingesetzt wird die sich beide auf Atom beziehen muß mit einem von beiden vor der Operation α= durchgeführt werden.

Anmerkungen

  • Jeder Term die Bedingung der β-Regel wird β-Reduzibel genannt.
  • β> ist i.A. nicht eindeutig.
  • Wenn mehrere Folgen von β-Reduktionen möglich und mehrere davon zu einem nicht-β-reduziblen Term so sind diese Terme bis auf α=
  • Wenn jedoch eine Reihenfolge der β einem nicht-β-reduziblen Term (einem Ergebnis) führt so dies auch die Standard Reduction Order bei der das im Term erste zuerst verwendet wird.

Beispiele

  • λx.x ist die Identitätsfunktion. (λx.x a) a
  • Wenn λx.λy.x wahr ist und λx.λy.y falsch dann bildet λx.λy.((x y) wahr ) die logische Funktion und .

Siehe auch

Berechenbarkeitstheorie



Bücher zum Thema Lambda-Kalkül

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Lambda-Notation.html">Lambda-Kalkül </a>