Welchen Beitrag leistet die Lambda-Rechnung auf dem Gebiet der Berechnungstheorie?

85

Ich lese gerade über Lambda-Kalkül nach, um "es kennenzulernen". Ich sehe es als alternative Form der Berechnung im Gegensatz zur Turing-Maschine. Es ist eine interessante Art, Dinge mit Funktionen / Reduzierungen zu tun (grob gesagt). Einige Fragen quälen mich jedoch immer wieder:

Was ist der Sinn von Lambda-Kalkül? Warum all diese Funktionen / Reduzierungen durchlaufen? Was ist der Zweck?
Infolgedessen muss ich mich fragen: Was genau hat die Lambda-Rechnung getan, um die Theorie der CS voranzutreiben? Was waren die Beiträge, die es mir ermöglichen würden, einen "Aha" -Moment zu haben, um die Notwendigkeit seiner Existenz zu verstehen?
Warum wird die Lambda-Rechnung in Texten zur Automatentheorie nicht behandelt? Der übliche Weg besteht darin, verschiedene Automaten, Grammatiken, Turing-Maschinen und Komplexitätsklassen zu durchlaufen. Lambda-Kalkül ist nur im Lehrplan für Kurse im SICP-Stil enthalten (vielleicht nicht?). Aber ich habe selten gesehen, dass es Teil des Kerncurriculums von CS ist. Bedeutet das, dass es nicht so wertvoll ist? Vielleicht nicht und mir fehlt hier vielleicht etwas?

Mir ist bewusst, dass funktionale Programmiersprachen auf der Lambda-Rechnung basieren, aber ich betrachte das nicht als gültigen Beitrag, da es viel vor unserer Einführung von Programmiersprachen erstellt wurde. Also, was ist wirklich der Sinn des Wissens / Verstehens der Lambda-Rechnung, bezüglich ihrer Anwendungen / Beiträge zur Theorie?

soft-question big-picture lambda-calculus ho.history-overview PhD
quelle

6

Eine verwandte Reihe von Antworten erklärt den Unterschied in der Leistung zwischen dem Kalkül und TMs: cstheory.stackexchange.com/questions/1117/…

λ

$\lambda$

Suresh Venkat

4

Vielleicht ist auch die Diskussion historischer Gründe für die Einführung von Turing Machine als primäres Berechnungsmodell von Interesse.

Martin Berger

5

In gewisser Weise war sein Beitrag , das Feld zu schaffen . Vergessen Sie nicht, dass Church zuerst eine Lambda-Rechnung entwickelte, die jedoch zunächst nicht als universelles Rechenmodell angesehen wurde.

Dan Hulme

In meinen Kernstudien hatte ich Functional Programmingüber Haskell und ein bisschen Lisp gesprochen. Der Nachfolger war Principles of Programming Languages, der ML verwendete und Lambda-Kalkül einführte. Wie einige Antworten zeigen, gehört der Lambda-Kalkül

genau dahin

Diese Frage ist eine ähnliche Beziehung zwischen TMs & Lambda-Kalkül & diskutiert auch Lambda-Kalkül historischen Vorrang

vzn

96

Kalkül hat zwei Schlüsselrollen. $\lambda$

Es ist eine einfache mathematische Grundlage für sequentielles, funktionales Rechenverhalten höherer Ordnung.
Es ist eine Darstellung von Beweisen in konstruktiver Logik.

Dies wird auch als Curry-Howard-Korrespondenz bezeichnet . Gemeinsam hat die doppelte Sicht auf Kalkül als Beweis und als (sequentielle, funktionale, höherwertige) Programmiersprache, gestärkt durch das algebraische Gefühl von Kalkül (das von Turing-Maschinen nicht geteilt wird), zu einem massiven Technologietransfer geführt zwischen Logik, den Grundlagen der Mathematik und der Programmierung. Diese Übertragung dauert noch an, beispielsweise in der Homotopietypentheorie . Insbesondere die Entwicklung von Programmiersprachen im Allgemeinen und von Typisierungsdisziplinen im Besonderen ist ohne nicht denkbar $\lambda$ $\lambda$ $\lambda$ -Infinitesimalrechnung. Die meisten Programmiersprachen sind Lisp und ML zu verdanken (z. B. wurde die Garbage Collection für Lisp erfunden), die direkte Nachkommen des Kalküls sind. Ein zweiter Arbeitsstrang, der stark vom Kalkül beeinflusst wird, sind interaktive Proof-Assistenten . $\lambda$ $\lambda$

Muss man Kalkül kennen, um ein kompetenter Programmierer oder gar ein Theoretiker der Informatik zu sein? Nein. Wenn Sie sich nicht für Typen, Überprüfungs- und Programmiersprachen mit Funktionen höherer Ordnung interessieren, ist dies wahrscheinlich ein Rechenmodell, das für Sie nicht besonders nützlich ist. Insbesondere wenn Sie sich für Komplexitätstheorie interessieren, ist Kalkül wahrscheinlich kein ideales Modell, da der grundlegende Reduktionsschritt mächtig ist: Er kann eine beliebige Zahl bilden von Kopien auf , also $\lambda$ $\lambda$

(λ x . M) N \to_{β} M [N / X]

$(\lambda x.M) N \rightarrow_{\beta} M[N/x]$

N

$N$

\to_{β}

$\rightarrow_{\beta}$ ist ein unrealistischer Grundbegriff für die Berücksichtigung der mikroskopischen Berechnungskosten. Ich denke, dies ist der Hauptgrund, warum Theorie A nicht so verliebt in

Kalkül ist. Umgekehrt sind Turing-Maschinen für die Entwicklung von Programmiersprachen nicht besonders inspirierend, da es keine natürlichen Vorstellungen von der Maschinenkomposition gibt, wohingegen mit

Kalkül, wenn

und

Programme sind,

tut . Diese algebraische Sicht der Berechnung bezieht sich natürlich auf in der Praxis verwendete Programmiersprachen, und ein großer Teil der Sprachentwicklung kann als Suche und Untersuchung nach neuartigen Programmkompositionsoperatoren verstanden werden.

λ

$\lambda$

λ

$\lambda$

M

$M$

N

$N$

M N

$MN$

Für einen enzyklopädischen Überblick über die Geschichte des Kalküls siehe Geschichte des Lambda-Kalküls und der kombinatorischen Logik von Cardone und Hindley . $\lambda$

Martin Berger
quelle

8

Das ist eine sehr schöne Antwort.

Suresh Venkat

9

β

$\beta$

β

$\beta$

β

$\beta$

P

$\mathsf P$

5

@DamianoMazza Da es sich um ein neues Ergebnis handelt, hätte es keinen Einfluss auf die Geschichte von Theorie A haben können. Außerdem denke ich, dass dies nur für einige Begriffe der Reduktion gilt. IIRC Aspertis Arbeit P = NP, bis hin zum Teilen, zeigt, dass P und NP zusammenbrechen, wenn Sie eine "optimale" Reduktionsstrategie im Sinne von J.-J. Erheben.

Martin Berger

6

β

$\beta$

β

$\beta$

β

$\beta$

27

$\lambda$ $\lambda$

$\lambda$ $\mu$
$\lambda$
$\mu$ $\lambda$

Bruno
quelle

20

$\lambda$

Was genau hat der Lambda-Kalkül getan, um die Theorie der CS voranzutreiben?

$\lambda$ $\lambda$ $\lambda$

$\lambda$

Damiano Mazza
quelle

2

λ

$\lambda$

λ

$\lambda$

π

$\pi$

π

$\pi$

5

Wenn ich mich selbst klonen könnte, würde ich ein Duplikat erstellen, um P / NP mit BLL und Realisierbarkeit zu untersuchen. Logische Beziehungen scheinen keine "natürlichen Beweise" zu sein, die lineare Typdisziplin stellt sicher, dass Sie nicht relativieren können, und die Polyzeit-Vollständigkeitstheoreme von BLL lassen Sie vermeiden, sich Gedanken darüber zu machen, ob es Klassen von Algorithmen gibt, die Sie verpasst haben oder nicht. Die Beziehung zwischen Linearität und Darstellungstheorie legt auch Verbindungen zur GCT nahe. Ich nehme an, das alles ist der Grund, warum Sie verärgert und frustriert sind. :)

Neel Krishnaswami

1

Hey @NeelKrishnaswami, könnten Sie mich bitte auf das Lesen von Material hinweisen, das BLL (begrenzte lineare Logik) und natürliche Beweise in Beziehung setzt?

Martin Berger

Zu B vs. A: Bei der Lambda-Berechnung geht es nur darum, die gleichen Berechnungen besser zu strukturieren, kann aber beispielsweise keine besseren Algorithmen erzeugen. Durch Cut-Elimination und die Subformula-Eigenschaft auf dem Ergebnis kann jedes Programm mit einem Typ erster Ordnung ohne erstklassige Funktionen geschrieben werden. Die Ausschneidung entspricht jedoch der Vervielfältigung von Code: Wir stellen also erneut fest, dass Sie keine Funktionen höherer Ordnung benötigen, wenn Sie bereit sind, genügend Kopien einzufügen. (Durch die Defunktionalisierung von Reynolds können Sie sogar das Einfügen von Kopien vermeiden, es handelt sich jedoch um eine globale Transformation, sodass es besser einem Compiler überlassen bleibt.)

Blaisorblade

Anekdotisch ist mein Kommentar durch das Programmieren mit einem Algorithmus motiviert - er ist großartig, aber er scheint viel weniger zu abstrahieren, als ich wünschenswert finde. Ich behaupte nicht, dass dies allgemein ist, aber ich behaupte, dass Abstraktion im Code beim Schreiben von Algorithmen oft nicht benötigt / betont wird. (Überlegen Sie, wie viele QuickSort-Implementierungen in der Partitionsfunktion enthalten sind - ich finde das inakzeptabel).

Blaisorblade

13

Ihre Fragen können von vielen Seiten beantwortet werden. Ich möchte die historischen und philosophischen Aspekte beiseite lassen und auf Ihre Hauptfrage eingehen, für die ich Folgendes halte:

Was ist der Sinn von Lambda-Kalkül? Warum all diese Funktionen / Reduzierungen durchlaufen?

Was ist der Sinn der Booleschen Algebra oder der relationalen Algebra oder der Logik erster Ordnung oder der Typentheorie oder eines anderen mathematischen Formalismus / einer anderen mathematischen Theorie? Die Antwort ist, dass sie keinen inhärenten Zweck haben, auch wenn ihre Designer sie für den einen oder anderen Zweck erschaffen haben. Leibniz hatte bei der Errichtung der Grundlagen der Booleschen Algebra ein bestimmtes philosophisches Projekt im Sinn; Boole studierte es aus seinen eigenen Gründen. de Morgans Arbeit zur relationalen Algebra war auch durch verschiedene Projekte von ihm motiviert; Peirce und Frege hatten ihre eigenen Motive für die Schaffung moderner Logik.

Der Punkt ist: Aus welchem Grund auch immer Church Lambda-Kalkül erstellt hat, der Punkt der Lambda-Kalkül variiert von einem Praktizierenden zum anderen.

Für jemanden ist es eine bequeme Notation, um über Berechnungen zu sprechen. eine Alternative zu Turing Machines und so weiter.
Zum anderen ist es eine solide mathematische Basis, auf der eine komplexere Programmiersprache (z. B. McCarthy, Stanley) aufgebaut werden kann.
Für eine dritte Person ist es ein strenges Werkzeug, um die Semantik von natürlichen und Programmiersprachen (z. B. Montague, Fitch, Kratzer) zu vermitteln.

Ich denke, Lambda-Kalkül ist eine formale Sprache, die es wert ist, um ihrer selbst willen studiert zu werden. Sie können die Tatsache lernen, dass wir in der untypisierten Lambda-Rechnung diese kleinen Bestien haben, die 'Y-Kombinatoren' genannt werden, und wie sie uns helfen, rekursive Funktionen zu definieren und den Beweis der Unentscheidbarkeit so elegant und einfach zu machen. Sie können die erstaunliche Tatsache lernen, dass es eine enge Entsprechung zwischen einfach getippter Lambda-Rechnung und einer Art intuitionistischer Logik gibt . Es gibt viele andere interessante Themen zu untersuchen (zB wie sollen wir die Semantik der Lambda-Rechnung angeben? Wie können wir die Lambda-Rechnung in ein deduktives System wie FOL umwandeln?)

Eine Einführung finden Sie in Hindley & Seldins Einführung in Kombinatoren und in λ – Calculus . Barendregt's The Lambda Calculus ist die Bibel. Wenn Sie sich also für Hindley & Seldin interessieren, gibt es viele semantische und syntaktische Themen zu erforschen.

Hunan Rostomyan
quelle

6

Ich kaufe dieses Argument nicht "um seiner selbst willen". Der Sinn eines mathematischen Formalismus besteht darin, unser Verständnis eines bestimmten Konzepts zu erläutern. Was aufgeklärt wird, kann sich im Laufe der Zeit entwickeln, aber wenn uns ein Formalismus nicht hilft, klarer über eine Idee nachzudenken, stirbt sie normalerweise aus. In diesem Sinne gilt es zu fragen, wie Lambda-Kalkül das Konzept der Berechnung auf eine Weise erklärt, die von TMs nicht subsumiert wird.

Sasho Nikolov

1

Ich denke, man kann Lambda-Kalkül studieren, ohne jemals an Reduktion und Substitution als Berechnung zu denken. Wenn ich recht habe und das tatsächlich möglich ist, können wir Interesse an Lambda-Berechnungen haben, auch wenn wir überhaupt kein Interesse an Berechnungen haben. Aber danke für deinen Kommentar; Ich werde versuchen, meine Antwort entsprechend zu bearbeiten, sobald ich eine Chance habe.

Hunan Rostomyan

@SashoNikolov - "auf eine Weise, die von TMs nicht subsumiert wird." Per Definition ist das unmöglich, da LC und TMs gleichwertig sind. Alles, was Sie mit einem ausdrücken oder beweisen können, können Sie mit dem anderen (und umgekehrt). Sie machen sich gegenseitig überflüssig (wie sie es mit der allgemeinen rekursiven Theorie und einem weiteren TM-äquivalenten Formalismus tun). Bedeutet das, dass wir alle TM-äquivalenten Systeme außer TM selbst wegwerfen sollten? Das würde ich nicht sagen, da Dinge manchmal einfacher in LC auszudrücken sind als in TM oder umgekehrt. Es ist nur eine andere Art, über Berechenbarkeit zu sprechen.

Gabriel L.

1

@ GabrielL. Wenn Sie den ganzen Satz lesen, heißt es : „Wie funktioniert Lambda - Kalkül erläutern das Konzept der Berechnung in einer Weise , die nicht von TMs aufgeht“. Zwei mathematische Definitionen, die formal gleichwertig sind, können das gleiche zugrunde liegende Konzept auf unterschiedliche und komplementäre Weise erläutern. Mein Kommentar bedeutete, dass es vernünftig ist zu fragen, welche Klarheit gewonnen wird, wenn man die Berechenbarkeit in Lambda-Berechnungen anstatt in TMs ausdrückt. Hier geht es überhaupt nicht um formale Äquivalenz.

Sasho Nikolov

Verstanden - es ist mir irgendwie gelungen, das Schlüsselwort dort zu übersehen. Danke für die Antwort.

Gabriel L.

12

Turing argumentierte, dass Mathematik auf eine Kombination von Lese- / Schreibsymbolen reduziert werden kann, die aus einer endlichen Menge ausgewählt werden und zwischen einer endlichen Anzahl von mentalen 'Zuständen' wechseln. Er bestätigte dies in seinen Turing-Maschinen, in denen Symbole in Zellen auf einem Band aufgezeichnet sind und ein Automat den Zustand verfolgt.

Die Maschinen von Turing sind jedoch kein konstruktiver Beweis für diese Reduzierung. Er argumentierte, dass jede "effektive Prozedur" von einer Turing-Maschine implementiert werden kann, und zeigte, dass eine universelle Turing-Maschine alle diese anderen Maschinen implementieren kann, gab jedoch nicht wirklich eine Reihe von Symbolen, Zuständen und Aktualisierungsregeln an, die Mathematik implementieren auf die Art und Weise, wie er argumentierte. Mit anderen Worten, er schlug keine "Standard-Turing-Maschine" mit einem Standardsymbolsatz vor, mit dem wir unsere Mathematik aufschreiben können.

Genau das ist die Lambda-Rechnung. Church versuchte speziell, die Notationen zu vereinheitlichen, die zum Aufschreiben unserer Mathematik verwendet wurden. Sobald gezeigt wurde, dass LC und TM gleichwertig sind, könnten wir LC als unsere 'Standard Turing Machine' verwenden und jeder könnte unsere Programme lesen (na ja, theoretisch;)).

Nun könnten wir uns fragen, warum LC eher als primitiver als als als TM-Dialekt behandelt wird. Die Antwort ist, dass die Semantik von LC denotational ist : LC-Terme haben eine "intrinsische" Bedeutung. Es gibt kirchliche Ziffern, es gibt Funktionen für Addition, Multiplikation, Rekursion usw. Dadurch ist LC sehr gut auf die Art und Weise abgestimmt, wie (formale) Mathematik praktiziert wird, weshalb viele (funktionale) Algorithmen immer noch direkt in LC dargestellt werden.

Andererseits ist die Semantik von TM-Programmen funktionsfähig : Die Bedeutung wird als das Verhalten der Maschine definiert. In diesem Sinne können wir keinen Bandabschnitt ausschneiden und "this is addition" sagen, da dies kontextabhängig ist. Das Verhalten der Maschine hängt vom Zustand der Maschine, den Längen / Offsets / etc. der Argumente, wie viel Band für das Ergebnis verwendet wird, ob eine vorherige Operation diesen Bandabschnitt beschädigt hat usw. Dies ist eine schreckliche Arbeitsweise ("Niemand möchte eine Turing-Maschine programmieren"), weshalb dies so ist Viele (imperative) Algorithmen werden als Pseudocode dargestellt.

Warbo
quelle

5

Andere Antworten sind gut. Hier ist ein weiterer Gesichtspunkt / Grund für die Überlegung, dass das Ineinandergreifen mit anderen möglicherweise noch eindeutiger ist, es jedoch schwieriger sein kann, dies klar im Auge zu behalten, da die alten Ursprünge im Sand der Zeit etwas verloren gehen:

historischer Vorrang!

Lambda-Kalkül wurde mindestens schon 1932 in der folgenden Literaturstelle eingeführt:

A. Church, "Eine Reihe von Postulaten zur Begründung der Logik", Annals of Mathematics, Series 2, 33: 346–366 (1932).

Die Turing-Maschine wurde ~ 1936 eingeführt . Lambda Calculus datiert also mehrere Jahre vor dem Erscheinen der TM!

Turing, AM (1936). Msgstr "Über berechenbare Nummern, mit einer Anwendung auf das Entscheidungsproblem". Verfahren der London Mathematical Society. 2 (1937) 42: 230–265. doi: 10.1112 / plms / s2-42.1.230

Mit anderen Worten, eine grundlegende Antwort ist, dass Lambda Calculus in vielerlei Hinsicht das ultimative Legacy-System von TCS ist. Es ist immer noch in der gleichen Weise wie Cobol, auch wenn in der Sprache nicht so viel Neues passiert! Es scheint das früheste eingeführte Berechnungssystem von Turing Complete zu sein und geht sogar der Grundidee von Turing Completeness voraus. Erst eine spätere retrospektive Analyse ergab, dass Lambda-Kalkül, Turing-Maschinen und das Post-Correspondence-Problem gleichwertig waren, und führte das Konzept der Turing-Äquivalenz und die Church-Turing-These ein .

Lambda - Kalkül ist einfach die Art und Weise Berechnung aus einer Studie Logik-centric pov mehr in Bezug auf mich als mathematische Theoreme darstellen und logische Formel Herleitungen und so weiter. es zeigt auch die tiefe Beziehung zwischen Rechnen und Rekursion und die weitere enge Kopplung mit der mathematischen Induktion .

Dies ist ein bemerkenswertes Faktoid, da es darauf hindeutet, dass die (zumindest theoretischen ) Ursprünge des Rechnens in vielerlei Hinsicht auf Logik / Mathematik zurückzuführen sind. Diese These wurde von Davis in seinem Buch Engines of Logic / Mathematicians und den Ursprüngen von der Computer . (Natürlich verstärken die Ursprünge und die fundamentale Rolle der Booleschen Algebra auch diesen konzeptuellen historischen Rahmen.)

daher könnte man dramatisch sagen, dass Lambda-Kalkül ein bisschen wie eine pädagogische Zeitmaschine ist, um die Ursprünge des Rechnens zu erforschen!

vzn
quelle

1

Nachtrag, Lambda-Kalkül scheint auch stark von Principia mathematica von Whitehead / Russell beeinflusst worden zu sein, was auch eine wichtige Inspiration für Godels thm war . Ein Teil dieser Forschung wurde auch von Hilberts 10. Problem um die Jahrhundertwende inspiriert, das nach einer algorithmischen Lösung fragte, bevor "Algorithmus" genau (mathematisch) definiert wurde, und in der Tat ist diese Suche größtenteils der Grund für die spätere genaue technische Definition.

vzn

btw / Klärung / iiuc es tatsächlich war Beitrag kanonische Systeme , die erste von Post und anscheinend die einfachere wurden untersucht Beitrag Korrespondenzproblem ist ein Sonderfall. es war auch Kleene, die maßgeblich zur Entwicklung des Konzepts der Turing-Vollständigkeit (nicht unter diesem Namen genannt) beitrug, indem sie dazu beitrug, alle drei Hauptsysteme als austauschbar / äquivalent (TM, Lambda-Kalkül, postkanonisches System) zu beweisen.

VZN

siehe auch Geschichte der

kirchentürkischen

4

Beim Cobol-Vergleich fällt es mir schwer, nicht beleidigt zu sein.

Neil Toronto

-2

Ich bin gerade auf diesen Beitrag gestoßen, und obwohl mein Beitrag ziemlich spät am Tag (im Jahr!) Ist, dachte ich, dass vielleicht der Wert meines "Pennys" von Nutzen sein könnte.

Während ich das Fach an der Universität studierte, hatte ich ähnliche Gedanken zu diesem Thema. Daher stellte ich dem Dozenten die Frage nach dem "Warum" und die Antwort lautete: "Compiler". Sobald sie es erwähnte, machten die Macht der Reduktion und die Kunst, zu beurteilen, wie man es am besten manipuliert, plötzlich den ganzen Zweck aus, warum es ein potentiell nützliches Werkzeug war und immer noch ist.

Das war sozusagen mein "Aha" -Moment.

Meiner Meinung nach halten wir Hochsprachen, Muster, Automaten, Algorithmuskomplexität usw. oft für nützlich, weil wir sie mit der jeweiligen "Aufgabe" in Beziehung setzen können. wohingegen lamdba-kalkül ein bisschen zu abstrakt erscheint. Es gibt jedoch immer noch Leute, die mit Sprachen auf niedrigem Niveau arbeiten - und ich stelle mir vor, Lambda-Kalkül, Objektkalkül und andere verwandte Formalisierungen haben ihnen geholfen, neue Theorien und Technologien zu verstehen und vielleicht zu entwickeln, von denen der durchschnittliche Programmierer dann profitieren kann. In der Tat ist es wahrscheinlich kein Kernmodul aus diesem Grund, aber (aus den von mir genannten Gründen) gibt es einige wenige - außer Akademikern -, die es für einen integralen Bestandteil ihres gewählten Karrierewegs im Computerwesen halten.

user30412
quelle

Was war das "Aha" auf Compilern ?

PhD

Ihr letzter Absatz scheint völlig spekulativ zu sein und Sie erklären nie, warum das eine Wort "Compiler" die Frage beantwortet.

David Richerby

@PhD: Beta-Reduction & Substitution werden beim Ausführen von Programmen nicht verwendet, sondern in optimierenden Compilern. Das ist nicht die Hauptbedeutung von Lambda-Kalkül, aber es ist eine sehr konkrete Anwendung.

Blaisorblade

Welchen Beitrag leistet die Lambda-Rechnung auf dem Gebiet der Berechnungstheorie?

Antworten: