Wem entspricht das Tippen in einer Turingmaschine?

8

Ich hoffe, meine Frage macht Sinn: Ausgehend von der Annahme, dass der untypisierte Kalkül der Leistung einer Turing-Maschine entspricht, was entspricht in einer Turing-Maschine das Hinzufügen von Typen zum \ Lambda- Kalkül? Gibt es eine Art Automaten analog zur Eingabe, ob statisch oder dynamisch?λλ

turing-machines lambda-calculus type-theory church-turing-thesis BlueBomber
quelle
3
Ich empfehle Ihnen, die vereinfachende Idee aufzugeben, dass TMs λ -calculus entsprechen. Es ist irreführend. In der Church-Turing-These finden Sie Kodierungen zwischen allen vernünftigen Rechenrahmen. TMs entsprechen nicht mehr λ -calculus als Conways Spiel des Lebens oder semi-Thue-Systemen oder Prolog oder ... Wir können Codierungen zwischen all diesen Systemen finden. Die Codierungen haben oder fehlen Eigenschaften (z. B. Zusammensetzung), und das kann in einer bestimmten Anwendung eine gute Sache sein oder auch nicht.
Martin Berger
1
Wenn es so irreführend ist, sollten dann nicht Leute (insbesondere Professoren) aufhören, es zu betonen? Es scheint ein wichtiges - in der Tat grundlegendes - Ergebnis in der Informatik zu sein. Warum sollten Menschen also nicht nach anderen Verbindungen zwischen den beiden Systemen suchen und diese erwarten?
BlueBomber
@BlueBomber, Es ist aus historischen Gründen wichtig / grundlegend: Dies waren zwei der wichtigsten vorgeschlagenen Formalisierungen der Berechnung (zusammen mit Rekursion) zu einer Zeit, als nicht bekannt war, wie die Berechnung "richtig" aussehen würde . Die Entdeckung der Tatsache, dass jeder den anderen simulieren konnte, war eine große Sache. Dies bedeutet jedoch nicht unbedingt, dass sie eine speziellere Verbindung haben als zwei andere Formalisierungen der Berechnung. μ
Usul

Antworten:

4

Ich kann Ihnen keine direkte Antwort für Automaten geben, sondern für Funktionen auf Zahlen.

Der untypisierte Lambda-Kalkül entspricht rekursiven Funktionen .μ

Bei typisierten Systemen variiert dies natürlich für verschiedene Systeme.

Ein interessantes ist System F , auch bekannt als polymorpher Lambda-Kalkül. Es gibt einen Satz, der das sagt

Eine Funktion (auf natürlichen Zahlen) kann in System F genau dann ausgedrückt werden, wenn in der Peano-Arithmetik zweiter Ordnung bewiesen werden kann, dass die Funktion total ist.

Dies bedeutet, dass Sie in System F grundsätzlich alle vorstellbaren Gesamtfunktionen ausdrücken können.

Es gibt ein etwas schwächeres System, Gödels System T, für das es einen sehr ähnlichen Satz für die Peano-Arithmetik erster Ordnung gibt. (Dieses System ist jedoch nicht so schön wie System F. In System F können Sie natürliche Zahlen, Boolesche Werte usw. nativ darstellen, während System T als einfach typisierter Lambda-Kalkül mit extern hinzugefügten Naturwerten und Booleschen Werten konstruiert ist. Auch System F weist Typpolymorphismus auf , was es in vielen Fällen viel eleganter macht.)

Siehe auch:

Petr Pudlák
quelle
2

Ich werde sagen, dass das Tippen für Turing Machines nichts entspricht. Hier ist meine Argumentation: Das Tippen hat eigentlich nichts mit Berechnung zu tun, und Turing Machines modelliert nur Berechnungen.

Zum größten Teil haben die Programmtypen keinen Einfluss darauf, wie dieses Programm ausgeführt wird. Vielmehr handelt es sich um Tools zur Kompilierungszeit, die aus einem von zwei Gründen verwendet werden. Eine besteht darin, schlecht typisierte Programme nicht kompilieren zu lassen. Dies ist eine Operation zur reinen Kompilierungszeit, die keinen Einfluss darauf hat, wie die resultierende Berechnung ausgeführt wird.

Die zweite besteht darin, dass mehrere Funktionen denselben Namen haben. Dies wirkt sich nicht wirklich auf die zugrunde liegende Berechnung aus, sondern lässt uns nur Programme auf eine Weise schreiben, die leichter zu verstehen ist.

Typen sind kein Berechnungswerkzeug. Sie können für Beweise verwendet werden, um Programme zu verstehen, um sie auf eine Weise zu strukturieren, die leichter zu verstehen ist, aber ihre Anwesenheit ändert nichts an der grundlegenden Art und Weise, wie wir die Berechnung durchführen.

jmite
quelle