Beziehung zwischen Turingmaschine und Lambda-Kalkül?

49

Gibt es eine Beziehung zwischen der Turing-Maschine und dem Lambda-Kalkül - oder sind sie zufällig etwa zur selben Zeit entstanden?

computability lambda-calculus turing-machines Falkenauge
quelle

7

Können Sie Ihre Frage näher erläutern? Beide Modelle haben die gleiche Rechenleistung (beide können die Familie der rekursiven Funktionen ausdrücken), das heißt, sie sind vollständig. Siehe: en.wikipedia.org/wiki/Turing_completeness

Joel Rybicki

verwandt: Realisierbarkeitstheorie: Leistungsunterschied zwischen Lambda-Kalkül und Turing-Maschinen

Kaveh

Das ist eine schöne Frage!

Tayfun Pay

31

Die Lambda-Rechnung ist älter als Turings Maschinenmodell und stammt offenbar aus der Zeit von 1928 bis 1929 (Seldin 2006). Sie wurde erfunden, um den Begriff einer schematischen Funktion zusammenzufassen, die Church für eine von ihm entwickelte Grundlogik benötigte. Es wurde nicht erfunden, um den allgemeinen Begriff der berechenbaren Funktion zu erfassen, und tatsächlich hätte eine schwächere typisierte Version seinen Zwecken besser gedient.

Es scheint nur zufällig zu sein, dass der Zweck des Kalküls, den Church erfand, sich als vollständig herausstellte, obwohl Church später den Lambda-Kalkül als Grundlage für das verwendete, was er als effektiv berechenbare Funktionen bezeichnete (1936), worauf Turing in seinem Aufsatz abzielte .

Die einfache Typentheorie von Church (1940) bietet eine moderatere, typisierte Funktionstheorie, die ausreicht, um die Syntax der Logik höherer Ordnung auszudrücken, aber nicht alle rekursiven Funktionen ausdrückt. Diese Theorie kann als mehr im Einklang mit der ursprünglichen Motivation der Kirche gesehen werden.

Verweise

Kirche (1936). Ein unlösbares Problem in der Elementarzahlentheorie. American Journal of Mathematics 58: 345–363.
Kirche (1940). Eine Formulierung der einfachen Typentheorie . Journal of Symbolic Logic 5 (2): 56—68.
Seldin (2006). Die Logik von Curry und Church . In Handbook of the History of Logic, Band 5: Logik von Russell bis Church , S. 819–874. Nordholland: Amsterdam.

Hinweis Diese Antwort wurde aufgrund von Einwänden von Kaveh und Sasho grundlegend überarbeitet. Ich empfehle die Wikipedia-Zeitleiste, die Kaveh vorschlug, " History of the Church-Turing Thesis" , die einige ausgewählte Zitate aus wegweisenden Artikeln enthält.

Charles Stewart
quelle

2

Church machte die Behauptung geltend, dass Lambda-Kalkül die intuitive Notation berechenbarer Funktionen vor Turings Aufsatz erfasst, weshalb es als Church's Thesis bezeichnet wird. Die Idee, den allgemeinen Begriff der berechenbaren Funktionen einzufangen, geht weiter zurück (z. B. Godels allgemeine rekursive Funktionen), und Church versuchte, ihn einzufangen.

Kaveh

5

Ich finde es irreführend zu sagen, dass die Gleichwertigkeit der Modelle ein völliger Unfall ist. Es scheint mir, dass Church und Turing sich vorgenommen haben, verwandte Begriffe zu erfassen, auch wenn es nicht sofort offensichtlich war, dass die Begriffe tatsächlich verwandt waren. Würden Sie sagen, dass Riemanns Integration und Antidifferenzierung eng miteinander verbunden sind?

Sasho Nikolov

@Kaveh: Nach Seldin (2006) Die Logik von Church and Curry , die Ziele und die Syntax des Lambda-Kalküls wurden in den Jahren 1928 bis 1929 entwickelt, lange bevor Church den allgemeinen Begriff der rekursiven Funktion kannte. Meine Antwort würde von einer Zeitleiste profitieren, aber ich habe momentan keine Zeit, diese zusammenzustellen.

Charles Stewart

1

λ

$\lambda$

1

@Charles, wie ich schrieb, stimme ich zu, dass die ursprüngliche Motivation von Church darin bestand, ein Fundament (so etwas wie Freges System) (AFAIK) zu bauen, aber er betrachtete es auch als Rechenmodell vor Turings Arbeit. Ich denke nicht, dass die Antwort gelöscht werden muss, eine Überarbeitung des zweiten Absatzes sollte es in Ordnung bringen. (Der Grund, den ich bemerkte, ist, dass ich das Gefühl habe, dass in letzter Zeit die Arbeit der Kirche hinsichtlich der Berechenbarkeit unterbewertet wird.)

Kaveh,

26

Ich möchte nur darauf hinweisen, dass der Lambda-Kalkül und die Turing-Maschine zwar beide dieselbe Klasse von zahlentheoretischen Funktionen berechnen, aber nicht in jeder erdenklichen Weise genau gleichwertig sind. In der Realisierbarkeitstheorie gibt es zum Beispiel Aussagen, die von einer Turing-Maschine aber nicht von einer Lambda-Rechnung realisiert werden können. Eine solche Aussage ist die formale These der Kirche, die besagt:

\forall f : n a t \to n a t \exists e \forall n \exists k (T (e, n, k) \land U (k, f (n)))

$\forall f : \mathbf{nat} \to \mathbf{nat} \ \exists e \ \forall n \ \exists k \ \big( \mathbf{T}(e, n, k) \land \mathbf{U}(k,f(n)) \big)$

$\mathbf{T}$ $c$ $f$ $e$ $f$ $f$ $c$ $c$ $f$ . Dies ist nicht möglich (ich kann erklären, warum, wenn Sie es als separate Frage stellen).

Andrej Bauer
quelle

4

T_{E} X

$T_EX$

Andrej, der Wikipedia-Artikel verwendet eine andere Reihenfolge von Parametern, die Sie verwenden, das zweite Argument ist die Eingabe und das dritte ist der Code zum Anhalten der Berechnung, das erste Argument ist der Code der Maschine. Ich vermute, Sie geben CT an, ich habe es basierend auf vDT88 bearbeitet.

Kaveh

f

$f$

λ

$\lambda$

f

$f$

λ

$\lambda$

@Kaveh: Ich denke, es war umgekehrt, aber ich frage mich auch, warum es nicht natürlich ist, auch eine Ausgabe des gleichen Typs wie die Eingabe im Fall von Lambda-Kalkül zu haben.

Abel Molina

1

f : R \to R

$f : \mathbb{R} \to \mathbb{R}$

2^{N}

$2^\mathbb{N}$

N^{N}

$\mathbb{N}^\mathbb{N}$

11

Sie sind sowohl mathematisch als auch historisch verwandt.

Der Lambda-Kalkül wurde 1928 - 1929 von Alonzo Church (veröffentlicht 1932) entwickelt.

Die Turing-Maschine wurde 1935 - 1937 von Alan Turing (veröffentlicht 1937) entwickelt.

Alan Turing war Ph.D. der Alonzo Church. Student in Princeton von 1936 - 1938.

Turingmaschinen und die Lambda-Rechnung sind in ihrer Rechenleistung gleichwertig: Sie können sich effizient gegenseitig simulieren.

Matt Might
quelle

6

Entscheidungsproblem ist eines der 23 bekannten Probleme, die der Mathematiker David Hilbert vorgeschlagen hat.

In den Jahren 1936 und 1937 veröffentlichten Alonzo Church und Alan Turing unabhängige Veröffentlichungen, die zeigten, dass es unmöglich ist, algorithmisch zu entscheiden, ob Aussagen in der Arithmetik wahr oder falsch sind, und daher eine allgemeine Lösung des Entscheidungsproblems unmöglich ist.

Dies wurde von Alonzo Church im Jahr 1936 mit dem Konzept der "effektiven Berechenbarkeit" auf der Grundlage seines λ-Kalküls und von Alan Turing im selben Jahr mit seinem Konzept der Turing-Maschinen durchgeführt. Es wurde später erkannt, dass dies äquivalente Berechnungsmodelle sind. - Wikipedia

So Lambda - Kalkül und Turing - Maschinen nicht nur eng miteinander verwandt , aber sie sind gleichwertige Berechnungsmodelle .

Vielleicht möchten Sie auch The Annotated Turing lesen : Eine Führung durch Alan Turings historisches Papier über Berechenbarkeit und die Turing-Maschine von Charles Petzold . Dieses Buch enthält einige interessante Informationen zum Thema.

Pratik Deoghare
quelle

4

Turingmaschinen und Lambda-Kalkül sind zwei Modelle, die den Begriff des Algorithmus (mechanische Berechnung) erfassen. Die Lambda-Rechnung wurde von Church erfunden, um Berechnungen mit Funktionen durchzuführen. Es ist die Basis für funktionale Programmiersprachen. Grundsätzlich ist jedes von Turing-Maschinen berechenbare (entscheidbare) Problem auch mit der Lambda-Rechnung berechenbar. Sie sind also zwei äquivalente Berechnungsmodelle (bis auf Polynomfaktoren) und beide versuchen, die Leistung jeder mechanischen Berechnung zu erfassen.

Mohammad Al-Turkistany
quelle

Beziehung zwischen Turingmaschine und Lambda-Kalkül?

Antworten:

Verweise