Diskussion:Lambda-Kalkül

gebundenen Variablen als Mengendifferenz

Die Definition der gebundenen Variablen als Mengendifferenz zwischen vorkommenden und freien Variablen eines Lambda-Terms ist doch quatsch, oder? Weil ja dann, wenn eine Variable sowohl frei, als auch gebunden vorkommt, sie automatisch nur noch in FV ist... --Syon 00:10, 9. Jun 2006 (CEST)

stimmt - gut, dass du das anmerkst!!! die Menge der gebundenen Variablen B(T) muss auch induktiv berechnet werden!!!

B(v) = {}

B((e e')) = (B e) U (B e')

B(\v.e) = (B e) U v

Weitere Beispiele

Habe unter "Weitere Beispiele" die Herleitung der Resultate für wahr und falsch eingefügt. Vielleicht kann sie noch jemand auf Korrektheit überprüfen. --Chiccodoro 13:38, 23. Jun 2006 (CEST)

Unverständlich

Nichts gegen die mathematischen und vielleicht nur für Mathematiker verständlichen Erläuterungen. Zusätzlich eine Beschreibung, die allgemeinverständlich ist, wäre super. --Arcy 10:57, 16. Mär. 2007 (CET)

mach Dir nix draus, aber selbst für die Genannten ist das λ-Kalkül ein harter Brocken. Keine Ahnung, ob es allgemeinverständlich erklärbar ist! Ich denke eher nicht! --88.70.247.183 19:23, 17. Apr. 2007 (CEST)

Also, ich lese mir das ganze gerade ohne irgendwelche Vorkenntnisse durch. Der Artikel wäre einfacher zu verstehen wenn die Reiehenfolge der Dinge Anders gewählt wäre. Die "Einführung" setzt zum Beispiel vorraus, dass man grundsätzlich weiß, was so ein Lambda-Kalkül ist. Vielleicht sollte man die Einführung rausschmeißen und dafür hinter die Formale Definition ein paar Beispiele setzen? -- Björn Keil 17:56, 20. Apr. 2007 (CEST)

Ich habe mal am Einführungssatz gedreht - gefällts euch jetzt besser? --SonniWP2 14:25, 31. Jul. 2007 (CEST)

ich habe immer noch nicht verstanden worum es geht. 03:25, 31. Jul. 2009 (CEST) (ohne Benutzername signierter Beitrag von 77.176.63.111 (Diskussion | Beiträge) )

Peinlich, aber ich muß mich hier anschließen, obwohl ich wirklich genug Mengenlehre etc. hatte. Die einzelnen Formeln kann ich größtenteils nachvollziehen, aber mir erschließt sich einfach der Nutzen nicht. Was kann ich damit machen, was ich sonst nicht machen könnte ? Kann vielleicht jemand zur Informatik ein praktisches Beispiel einfügen, daß zum einen praxisrelevant ist (also nicht abgehoben theoretische "Selbstbefriedigung") und zum anderen über Lambda besser, klarer, effizienter oder gar überhaupt nur geht ? Weil es auf den ersten Blick für mich schnuppe ist, ob ich nun f(x) oder lambda.x oder fx schreibe ;-). Ich gehe davon aus, daß ich das Ding verstünde, wenn ich nen halben Tag drauf investierte, aber von einer Enzyklopädie erwarte ich eigentlich weniger Details und dafür mehr "Zugang", also "was hab ich davon" ... JB. --92.195.75.59 20:06, 4. Aug. 2016 (CEST)

Regelwidrige Anwendung der β-Konversion

In der Einführung heißt es: "Denn mit der β-Kongruenzregel sind die Ausdrücke (λ x. λ y. x - y) 7 2, (λ y. 7 - y) 2 und 7 - 2 äquivalent."

Bei Beachtung der Regel der β-Konversion, die weiter unten steht, ist das aber Quatsch. Diese Regel operiert "von außen nach innen". Das heißt in dem Ausdruck (λ x. λ y. x - y)(7)(2) wird x durch 2 ersetzt und dann y durch 7, ergibt 2-7. Das Argument, auf das die Funktion angewendet wird steht rechts außen, nicht irgendwo im Lambda-Term.

Außerdem fehlen auch die Klammern um die einzusetzenden Argumente. Überhaupt ist die Notation der Lambda-Ausdrücke im ganzen Artikel inkonsistent. Man sollte sich mal entscheiden, ob man "(λ y. 7 - y) 2" oder "λ y.7 - y (2)" oder "((λ y. 7 - y) 2)" oder "(λ y.7-y)(2)" schreibt. Ich würde letzteres vorziehen. In dieser Schreibweise wird auch völlig klar, dass diese Vertauschung der einzusetzenden Argumente nicht zulässig ist: (λ x.(λ y.x-y)(7))(2) wird somit NICHT konvertiert nach 7-2

Allerdings scheint dieser Fehler der "Argumentanhebung" aus dem Lambda-Ausdruck an die rechte äußere Stelle allgemein verbreitet, sodass man bei der β-Konversionsregel hinzufügen könnte, dass mehrere Argumente als Liste angefügt werden können und von links nach rechts abgearbeitet werden. 217.225.224.193 14:18, 18. Sep. 2007 (CEST)

Äquivalenz

Der Begriff "Äquivalenz von Ausdrücken" wird mehrfach verwendet aber nicht definiert. Ich finde "Äquivalenz" schlecht gewählt, denn der Name ist schon sehr überladen (z.B. Äquivalenz von Formeln oder Äquivalenzrelationen). Wie wäre es mit semantischer Gleichheit, Bedeutungsgleichheit oder $\alpha \beta \eta$-Kongruenz?

Folgender Satz ist mir nicht ganz klar:

Es ist entscheidbar, ob ein untypisierter Term sich typisieren lässt, selbst wenn die Umgebung Γ unbekannt ist
(eine Variante mit Typvariablen und Typkonstruktoren ist Milners Algorithm W).

Ist damit gemeint, dass die Frage entscheidbar ist, ob eine Umgebung existiert, in der der Ausdruck typisierbar ist? "Term" und "Ausdruck" sollten übrigens nicht als synonym angenommen werden. --AlfonsGeser 19:30, 13. Jun. 2008 (CEST)

Unverständliche Einführung

Beim Abschnitt Der untypisierte Lambda-Kalkül stehen unter Einführung die beiden Sätze: "Um den Lambda-Kalkül auf ein Problem anzuwenden, konstruiert man Ausdrücke, die sich wie das Problem verhalten – so wie man beim Lösen von Textaufgaben in der Mathematik auch vorgehen kann. Der Lambda-Kalkül kann auf vielfältigere Probleme angewandt werden wie beispielsweise die auch bei Nicht-Mathematikern weit verbreiteten Rechenmethoden." Das verstehe ich überhaubt nicht. Ich denke man sollte das ersatzlos streichen. --B-greift 21:06, 27. Jan. 2011 (CET)

ZOMG. Was für ein Müll. Es ist nicht mal ansatzweise erkennbar, was uns der Autor damit sagen will. Kann weg. --Daniel5Ko 21:22, 27. Jan. 2011 (CET)

Und weg. --Mussklprozz 23:22, 27. Jan. 2011 (CET)

Habe die Einführung zum untypisierten Lambda-Kalkül nochmal ganz überarbeitet und sie Motivation genannt. Einen Aspekt habe ich herausgenommen und ihn nach unten zu Anmerkungen verschoben. --B-greift 22:02, 5. Feb. 2011 (CET)

Hmmm, ehrlich gesagt hat mir der nun offenbar gelöschte Text deutlich MEHR gegeben als das Zeugs was im Moment auf der Seite steht. Schade. Aber hier wurde genau DAS gelöscht, dessen Fehlen ich oben unter "Unverständlich" moniert habe. JB. --92.195.75.59 20:09, 4. Aug. 2016 (CEST)

$\beta$-Reduktion

Was heißt eigentlich von "links nach rechts angewandt". Müßte es nicht "von Innen nach Außen" heißen oder von "Außen nach Innen". Zweite Frage: Braucht man den Begriff $\beta$-Reduktion in Abgrenzung zu $\beta$-Konversion überhaubt? --B-greift 21:53, 7. Feb. 2011 (CET)

Also nach meinem Wissen:

• Beta-Reduktion: irgendwo in einem Teilterm ((λ V. E ) E' ) durch E [V←E' ] ersetzen.
• Beta-Konversion: Beta-Reduktion vorwärts oder rückwärts anwenden, ggf. beliebig oft. (Hier geht's um eine Äquivalenzrelation)
• Normalform: (falls existent) das Endergebnis, das erreicht wird, wenn man Beta-Reduktionen solange durchführt, bis es nicht mehr geht. Hierfür gibt es mehrere Möglichkeiten bei der Wahl der Reihenfolge der Reduktionen, und einige führen unnötigerweise zu Endlosschleifen. Aber falls eine Normalform existiert, ist sie eindeutig und durch die Strategie, immer den left-most, outer-most Redex zu wählen, garantiert erreichbar.

Ja, der Artikel stellt das nicht besonders gut dar. Das unter Weblinks als "Einführung in den λ-Kalkül" verlinkte Dokument tut das sehr gut, wenn ich mich recht erinnere. Beim Ausbessern vielleicht davon inspirieren lassen. :) --Daniel5Ko 22:49, 7. Feb. 2011 (CET)

Mathematische Operationen im Lambda-Kalkül

Ist es wirklich sinnvoll den Lambda-Kalkül hier nur in Zusammenhang mit mathematischen Begrifflichkeiten zu bringen? Wenn ich mir mal den englischen Artikel angucke sehe ich, dass der Lambda-Kalkül auch als Programmiersprache verwendet werden kann. Das fließt hier nicht ein. In diesem Sinne ist es dann verboten herkömmliche mathematische Operationen innerhalb von Lambda-Ausdrücken zu verwenden. Nur durch dieses Verbot tritt die wahre Anwendbarkeit und Mächtigkeit des Lambda-Kalküls zu Tage. Vielleicht sollte man diese Aspekte noch mitberücksichtigen. (nicht signierter Beitrag von Wandynsky (Diskussion | Beiträge) 18:37, 3. Mai 2012 (CEST))

Ja das fehlt. Zummindest mal eine Liste von Programmiersprachen, die von ihrer Konzeption her klar zum Lambda-Kalkül Bezug nehmen. -- B-greift (Diskussion) 23:06, 4. Mai 2012 (CEST)

Lambda-Funktionen in Python

Um die von B-greift vorstehend vorgeschlagene Liste mal mit einer populären Sprache zu füttern, hier ein paar Beispiele in Python, das (von Haskell inspiriert) ein Schlüsselwort lambda hat:

Python	entspricht	Pseudocode
lambda x: x+2	$\lambda x\;.\;x+2$ (Motivation)	def lambda(x): return x+2
lambda x: x	$\lambda x\;.\;x$ (Identität)	def lambda(x): return x

Der Pseudocode in der dritten Spalte wäre in Python nicht gültig, weil lambda ein Schlüsselwort ist, verdeutlicht aber, wie Python es versteht: Es handelt sich um anonyme Funktionen, die lediglich einen Ausdruck auswerten und das Ergebnis zurückgeben. Alternativ ist es stets möglich, eine normale Funktion (wie in der Pseudocode-Spalte, aber mit einem gültigen Namen) zu verwenden (in Zuweisungen, als Funktionsargument oder natürlich zum direkten Aufruf).

Es ließen sich sicher leicht viele weitere Beispiele aus dem Artikel entsprechend nach Python übersetzen ... Ich wüßte nämlich wirklich gern, wie sich dieses Python-Sprachkonstrukt zum Lambda-Kalkül verhält. Anhand des (Verzeihung) mathematikchinesischen Artikels kapiere ich das nämlich nicht wirklich.

Ich kann mir sogar vorstellen, daß die Verständlichkeit des Artikels durch eine ausführlichere Betrachtung, wie die praktische Umsetzung in der Informatik aussieht, stark gewinnen könnte. --Tobias (Diskussion) 10:59, 18. Jan. 2014 (CET)

Gewissermaßen ist ja jede Bildung einer Funktion in einer Programmiersprache ein Art Lambda-Konstrukt. Z.B: function (x) { return x + 2 } Zusätzlich bieten aber manche Sprachen die Möglichkeit Funktionen selbst als Daten anzusehen. Sie können dann anderen Funktionen als Parameter übergeben werden, und dort (anonym) zur Anwendung kommen. Und der Rückgabewert einer Funktion könnte auch wieder eine Funktion sein. Nur wenn das beides gegeben ist, kann man davon sprechen, dass ein Bezug zum Lambda-Kalkül gegeben ist. --B-greift (Diskussion) 23:08, 18. Jan. 2014 (CET)

Ich nehme an, das bezieht sich auf seiteneffektfreie Funktionen, die also keine globalen Variablen verwenden.

In Python sind jedenfalls Funktionen "First-Class-Objekte", und sie können also auch Funktionen zurückgeben. --Tobias (Diskussion) 17:07, 25. Jan. 2014 (CET)

Ich denke, es ist nicht relevant, ob eine Funktion Seiteneffekte hat. Die Interpreter oder Compiler machen da wohl keine Einschränkung. Eventuell stört das aber die Vergleichbarkeit zum Lambda-Kalkül. Dabei sind aber nicht die Effekte der Funktionen auf äußeren Objekte relevant, sondern die Frage, wie der Zustand äußerer Gegebenheiten auf die Wirkung der Funktionen Einfluss hat. (Mein Background ist dabei Javascript und Perl) --B-greift (Diskussion) 21:33, 30. Jan. 2014 (CET)

Sprachlicher Fehler

Momentan (Permalink) steht folgendes im Artikel:

Die Menge der freien Variablen FV kann induktiv über der Struktur der λ-Terme wie folgt definiert werden:

1. FV(a) = {a}, falls der Term eine Variable a
2. FV(T1 T2) = FV(T1) ∪ FV(T2) für Applikationen, und
3. FV(λ a. T) = FV(T)\{a}, falls der Term eine Abstraktion ist, sind seine freien Variablen die freien Variablen von T außer a.

Die Menge der gebundenen Variablen B(T) eines Terms T errechnet sich auch induktiv:

Offensichtlich ist der erste Punkt sprachlich nicht korrekt. Da fehlt "hat" oder "beinhaltet" oder etwas ähnliches. Aber selbst dann ist nicht klar, wass mit "der Term" gemeint ist.

Leider kann ich das nicht selbst beheben, da ich mich gerade erst in das Thema einlese.

Viele Grüße, --Martin Thoma 13:52, 2. Mär. 2014 (CET)

Nicht "hat" sondern "ist". Ich denke es muß heißen: "falls der Term a eine Variable ist". --B-greift (Diskussion) 21:39, 18. Mär. 2014 (CET)

man

Besteht die Möglichkeit das Füllwort man, kommt im Text 24mal vor, ersetzen? Ich habe in der Schule gelernt, dass Mathematik eine exakte Wissenschaft ist und ich finde man ist sehr schwammig. (nicht signierter Beitrag von 217.91.137.111 (Diskussion) 09:20, 19. Feb. 2015 (CET))

Das kann man sicherlich ersetzen. Du könntest es zum Beispiel machen.

Mathematik ist exakt (oder kann zumindest exakt betrieben werden). Das hat aber nichts mit "man" zu tun. Das Ersetzen von "man" durch eine passive Ausdrucksweise ist keine inhaltlich relevante Änderung. --Martin Thoma 10:54, 19. Feb. 2015 (CET)

Wie waers mit dem Aktiv: "... das man mit einer Turing-Maschine ausdruecken kann" wird zu "... das eine Turing-Maschine ausdruecken kann". Dann ist der Text weniger lang. Da es im Text um Logik und eben auch Ausdruck geht, ist die verwendete Grammatik ein implizites Beispiel der Problematik. Ich mag irren doch, die Entmannung des Textes gleicht einer Beta-Reduktion. Vielleicht mach ich da mal was dran. 91.66.4.64 (21:16, 22. Sep. 2015 (CEST), Datum/Uhrzeit nachträglich eingefügt, siehe Hilfe:Signatur)

λ oder $\lambda$

Im Artikel werden an verschiedenen Stellen auf verschiedene Weise griechische Buchstaben verwendet. Dort wo die Buchstaben einzeln und insbesondere nicht als mathematische Variablen (also als Formeln) vorkommen, wie in λ-Kalkül, α-, β- η-Konversion, soll gemäß typographischen Regeln keine Formel verwendet werden. An den meisten Stellen ist dies korrekt umgesetzt, ich werde die übrigen Stellen korrigieren. Alles andere wäre schlicht typographisch inkonsistent. Spezialist^D 23:19, 27. Feb. 2015 (CET)

Weblinks

Es fehlt ein sachlicher Grund, Aehlig und Fischbachers "Einführung in den λ-Kalkül" nicht zu verlinken. Vor allem, da der Text sehr viel sinnvoller und lehrreicher ist als zum Beispiel Fabian Nilius' "Das gefürchtete Lambda-Kalkül" oder die "Alligator-Eggs!". Gruß, --84.129.36.77 03:21, 29. Aug. 2015 (CEST)

Schon mal was von Copyright gehört? Die Autoren werden schon ihren Grund haben, dass sie ihr Skript nicht mehr zum Download anbieten. Wenn du nicht einer der Autoren bist oder von ihnen die Erlaubnis zur Veröffentlichung bekommen hast, solltest du das Skript schleunigst wieder von deinen privaten Seiten löschen. Grüße, --Quartl (Diskussion) 05:23, 29. Aug. 2015 (CEST)

Was erzählst denn du jetzt für einen Schwachsinn von meinen privaten Seiten? So wird nicht argumentiert. Wenn es die um Copyright geht (das war bisher nicht zu erkennen), hätte dir vielleicht auch der Alternativ-Link auffallen können, den IInterspecies in seiner Zusammenfassungszeile angegeben hat. An ihm ist unschwer zu erkennen, dass mindestens einer der Autoren das Dokument zum Download anbieten will. (Im Übrigen kann man das Gegenteil, nämlich den Willen der Autoren, etwas nicht mehr anzubieten, an dem nicht-mehr-verfügbar-Werden einer Internet-Resource überhaupt nicht erkennen.)

Ich trage den Link jetzt ein und sehe das damit als erledigt an. --84.129.36.77 11:45, 29. Aug. 2015 (CEST)

Weitere Beispiele: Und ist unvollstaendig

Kann jemand die Elipsen in den Gleichungen zum Beispiel fuer \UND = \x\y(x y falsch) auffuellen? Das ist so vielleicht eindeutig, aber schlechter nachvollziehbar, wenn man das Prinzip noch nicht verstanden hat. Fuer mich scheint diese Gleichung auf den ersten Blick aussagekraeftiger als das meiste aus den Abschnitten davor, deshalb. Anderen helfen die Zwischenschritte bestimmt auch beim Einpraegen des Prinzips der Beta Reduktion (Wiederholung). Man koennte denken, da war jemand einfach nur schreibfaul :P 91.66.4.64 (21:16, 22. Sep. 2015 (CEST), Datum/Uhrzeit nachträglich eingefügt, siehe Hilfe:Signatur)