Warum sind funktionale Sprachen vollständig?

Vielleicht ist mein begrenztes Verständnis des Themas falsch, aber das ist, was ich bis jetzt verstehe:

• Die funktionale Programmierung basiert auf Lambda-Kalkül, das von Alonzo Church formuliert wurde.

• Die imperative Programmierung basiert auf dem Turing-Maschinenmodell, das von Alan Turing, dem Studenten der Kirche, erstellt wurde.

• Lambda-Kalkül ist so leistungsfähig und fähig wie die Turing-Maschine,
  was bedeutet , dass sie hinsichtlich der Rechenleistung äquivalent sind.

Wenn die Funktionsprogrammierung auf Lambda Calculus und nicht auf der Turing-Maschine basiert, warum werden dann einige (oder alle) als Turing vollständig und nicht als Lambda vollständig oder so ähnlich beschrieben? Ist der Begriff "Turing-Vollständigkeit" in irgendeiner Weise etwas Besonderes für Turing-Maschinen, oder ist er nur ein Wort?

Wenn zwingende Sprachen auf der Turing-Maschine basieren und Computer im Grunde genommen Turing-Maschinen ohne unendlichen Speicher sind, bedeutet das dann, dass sie auf unseren modernen PCs eine bessere Leistung als funktionale Programmiersprachen erbringen?

Wenn dies der Fall ist, was entspricht dann einer Lambda-Rechenmaschine?

Ich weiß, dass dies drei verschiedene Fragen zu sein scheinen, aber sie sind alle eng miteinander verwandt, und jede hängt davon ab, dass die vorherige Frage zunächst eine gültige Frage ist.

Kurz gesagt :

Was zwingende Programmiersprachen als nahe an Turing-Maschinen und an gewöhnlichen Computern wie PCs (selbst näher an RAM-Maschinen als an Turing-Maschinen) auszeichnet, ist das Konzept eines expliziten Speichers , der zum Speichern geändert werden kann (Zwischenergebnisse) ). Hierbei handelt es sich um eine automatische Ansicht der Berechnung mit einem Konzept eines Zustands (das sowohl die Steuerung des endlichen Zustands als auch den Speicherinhalt umfasst), das sich im Verlauf der Berechnung ändern kann.

Die meisten anderen Modelle sind abstrakter. Obwohl sie die Berechnung als Folge von Transformationsschritten einer ursprünglichen Struktur ausdrücken können, werden diese Transformationen in einer Art intemporalem Universum mathematischer Bedeutungen angewendet. Dadurch bleiben möglicherweise Eigenschaften wie die referenzielle Transparenz erhalten, die die mathematische Analyse vereinfachen können. Es ist jedoch weit entfernt von natürlichen physischen Modellen, die sich auf das Gedächtnis konzentrieren.

Somit gibt es keine natürlichen Funktionsmaschinen, außer im weiter unten erläuterten Sinne, da Software nicht wirklich von Hardware trennbar ist.

Der Hinweis auf Turing als Maßstab für die Berechenbarkeit ergibt sich wahrscheinlich aus der Tatsache, dass sein Modell, die Turing-Maschine, dieser physikalischen Realisierbarkeitsbeschränkung am nächsten kam, was sie zu einem intuitiveren Berechnungsmodell machte.

Weitere Überlegungen :

Es gibt viele Berechnungsmodelle, die entworfen wurden, um das Konzept einer Berechnung auf möglichst allgemeine Weise zu erfassen. Dazu gehören Turing-Maschinen, die eigentlich in vielen verschiedenen Geschmacksrichtungen erhältlich sind, Lambda-Kalkül (auch Geschmacksrichtungen), Semi-Thue-Umschreibungssysteme, teilweise rekursive Funktionen und kombinatorische Logik.

Sie alle erfassen einige Aspekte der verschiedenen Techniken, die von Mathematikern zum Ausdrücken oder Durchführen von Berechnungen verwendet werden. Und die meisten wurden in gewissem Umfang als Grundlage für das Design von Programmiersprachen verwendet (z. B. Snobol für Umschreibsysteme, APL für Kombinatoren, Lisp / Schema für Lambda-Kalkül) und können in modernen Programmiersprachen häufig auf verschiedene Arten kombiniert werden.

Ein wesentliches Ergebnis ist, dass alle diese Rechenmodelle als gleichwertig erwiesen wurden, was zu der These von Church-Turing führte, dass kein physikalisch realisierbares Rechenmodell mehr leisten kann als eines dieser Modelle. Ein Berechnungsmodell wird als vollständig bezeichnet, wenn nachgewiesen werden kann, dass es einem dieser Modelle und damit allen Modellen entspricht.

Der Name hätte anders sein können. Die Wahl der Turing-Maschine (TM) als Referenz beruht wahrscheinlich auf der Tatsache, dass es sich wahrscheinlich um das einfachste dieser Modelle handelt, das die Art und Weise, wie ein Mensch rechnet, genau nachahmt und relativ einfach zu implementieren ist (in einer begrenzten endlichen Form) ) als physisches Gerät, so dass Turing-Maschinen mit Lego-Sets gebaut wurden . Die Grundidee erfordert keine mathematische Raffinesse. Es ist wahrscheinlich die Einfachheit und Realisierbarkeit des Modells, die ihm diese Referenzposition gegeben hat.

Zum Zeitpunkt der Erstellung seines Computergeräts durch Alan Turing lagen weitere Vorschläge zur formalen Definition der Berechenbarkeit vor, die für die Grundlagen der Mathematik von entscheidender Bedeutung ist (siehe Entscheidungsproblem ). Der Turing-Vorschlag wurde von den damaligen Experten als die überzeugendste bekannte Arbeit zur Berechenbarkeit angesehen (siehe Computability and Recursion , RI Soare, 1996, siehe Abschnitt 3.2). Die verschiedenen Vorschläge erwiesen sich als gleichwertig, aber Turings überzeugender. _{[aus Kommentaren von Yuval Filmus]}

Es ist zu beachten, dass unsere Computer aus Hardware-Sicht keine Turing-Maschinen sind, sondern sogenannte Random Access Machines (RAM) , die ebenfalls vollständig Turingen.

Rein imperative Sprache (was auch immer das bedeuten mag) sind wahrscheinlich die Formalismen, die für die grundlegendsten Modelle wie Turing-Maschinen verwendet werden, oder die Assemblersprache (Überspringen der binären Codierung) von Computern. Beide sind notorisch unlesbar und es ist sehr schwierig, mit ihnen signifikante Programme zu schreiben. Tatsächlich verfügt sogar die Assemblersprache über einige Funktionen höherer Ebenen, um die Programmierung ein wenig zu vereinfachen, verglichen mit der direkten Verwendung von Maschinenanweisungen. Grundlegende imperative Modelle sind den physikalischen Welten verschlossen, aber nicht sehr brauchbar.

Dies führte schnell zur Entwicklung übergeordneter Berechnungsmodelle, die eine Vielzahl von Rechentechniken, wie Unterprogramm- und Funktionsaufrufe, Benennung des Speicherorts, Festlegung von Namen, Quantifizierung und Dummy-Variablen, die bereits in irgendeiner Form verwendet wurden, einmischten in Mathematik und Logik und sogar sehr abstrakte Konzepte wie Reflexion ( Lisp 1958).

Die Einteilung von Programmiersprachen in Programmierparadigmen wie imperative, funktionale, logische, objektorientierte basiert auf dem Vorrang einiger dieser Techniken beim Entwurf der Sprache und dem Vorhandensein oder Nichtvorhandensein einiger Rechenfunktionen, die bestimmte Eigenschaften für Programme erzwingen oder Programmfragmente in der Sprache geschrieben.

Einige Modelle eignen sich für physische Maschinen. Einige andere eignen sich besser für eine allgemeine Beschreibung von Algorithmen, die von der Art des zu beschreibenden Algorithmus abhängen kann. Einige Theoretiker verwenden sogar nicht deterministische Spezifikationen von Algorithmen, und sogar diese können in konventionellere Programmierbegriffe übersetzt werden. Es gibt jedoch kein Mismatch-Problem, da wir eine ausgeklügelte Compiler / Interpreter-Technologie entwickelt haben, mit der jedes Modell nach Bedarf in ein anderes übersetzt werden kann (was auch die Grundlage der Church-Turing-These ist).

Nun sollten Sie Ihren Computer niemals als Rohhardware betrachten. Es enthält eine Boolesche Schaltung, die eine sehr elementare Verarbeitung durchführt. Aber ein Großteil davon wird von Mikroprogrammen im Computer gesteuert, von denen Sie nie etwas erfahren. Dann haben Sie das Betriebssystem, das Ihren Computer sogar anders aussehen lässt als die Hardware. Darüber hinaus verfügen Sie möglicherweise über einen virtuellen Computer, der Bytecode ausführt, und anschließend über eine Hochsprache wie Pyva und Jathon oder Haskell , oder OCaml, die in Bytecode kompiliert werden können.

Auf jeder Ebene sehen Sie ein anderes Berechnungsmodell. Es ist sehr schwierig, die Hardware-Ebene von der Software-Ebene zu trennen, um einer Maschine ein bestimmtes Rechenmodell zuzuweisen. Und da sie alle unübersetzbar sind, ist die Idee eines ultimativen Hardware-Berechnungsmodells so ziemlich eine Illusion.

Die Lambda-Kalkül-Maschine existiert tatsächlich: Es ist ein Computer, der Lambda-Kalkül-Ausdrücke reduzieren kann. Anzeige, die leicht gemacht wird.

Über spezialisierte Maschinenarchitekturen

Als Ergänzung zu Peter Taylors Antwort und nach der Verflechtung von Hardware und Software wurden spezielle Maschinen entwickelt, die besser an ein bestimmtes Paradigma angepasst sind, und deren Basissoftware in einer auf diesem Paradigma basierenden Programmiersprache geschrieben wurde.

Diese schließen ein

• Die Burroughs B5000 und ihre Nachfolger (1960er Jahre), die für eine effiziente Implementierung der Rekursion angepasst wurden, wurden zu dieser Zeit durch die Sprache Algol 60 repräsentiert .

• Die Western Digital WD / 9000 Pascal MicroEngine , eine Maschine, die auf einem mikroprogrammierten Bytecode basiert und auf die Programmiersprache Pascal spezialisiert ist .

• Mehrere Marken von Lisp Machines in den 1980er Jahren.

Grundsätzlich sind dies auch zwingende Hardwarestrukturen, die jedoch durch spezielle Hardware-Funktionen oder mikroprogrammierte Interpreter gemildert werden, um sich besser an das beabsichtigte Paradigma anzupassen.

Tatsächlich scheint Hardware, die auf bestimmte Paradigmen spezialisiert ist, auf lange Sicht nie erfolgreich gewesen zu sein. Der Grund dafür ist, dass die Kompilierungstechnologie zur Implementierung eines Paradigmas auf Vanille-Hardware immer effektiver wurde, sodass keine spezielle Hardware mehr benötigt wurde. Darüber hinaus verbesserte sich die Leistung der Harware schnell, aber die Kosten für Verbesserungen (einschließlich der Weiterentwicklung der Basissoftware) konnten auf Vanille-Hardware leichter amortisiert werden als auf Spezialhardware. Spezialisierte Hardware konnte auf Dauer nicht mithalten.

Trotzdem und obwohl ich keine genauen Daten dazu habe, würde ich vermuten, dass diese Unternehmungen einige Ideen hinterlassen haben, die die Entwicklung der Architektur von Maschinen, Erinnerungen und Befehlssätzen beeinflusst haben.

Turing-Complete ist nur ein Name. Sie können es Abdul-komplett nennen, wenn Sie wollen. Namen werden historisch entschieden und oft nach "falschen" Personen benannt. Es ist ein soziologischer Prozess, der keine klaren Kriterien hat. Der Name hat über die offizielle Semantik hinaus keine Bedeutung.

Imperative Sprachen basieren nicht auf Turing-Maschinen. Sie basieren auf RAM-Maschinen. Ihr Computer ist ein RAM-Computer. Turing-Maschinen sind ein schönes theoretisches Modell, aber sie sind kein sehr gutes Modell für tatsächliche Computer.

Programmiersprachen, die auf anderen Paradigmen basieren, können sehr erfolgreich sein, auch wenn die zugrunde liegende CPU sie nicht von Haus aus unterstützt. Drucker führen beispielsweise eine Stapelsprache aus. Programmierung ist mehr als nur Maschinencode.

Weil "Turing-komplett" nur "es kann berechnen, was eine Turing-Maschine berechnen kann" bedeutet.

Eine Ihrer Fragen scheint noch nicht beantwortet worden zu sein:

Wenn dies der Fall ist, was entspricht dann einer Lambda-Rechenmaschine?

Eine Lisp-Maschine . Hardware, die speziell für das LISP-Berechnungsmodell entwickelt wurde. Der Wikipedia-Artikel handelt von kommerziellen Produkten, aber mein Studienleiter an der Universität hatte ein handgefertigtes in seinem Büro.

Die von Church erfundenen funktionalen Sprachen in Form von Lambda-Kalkül erwiesen sich als vollständig. Dies ist ein tatsächlicher mathematischer Beweis, der in veröffentlichten wissenschaftlichen Arbeiten gefunden werden kann, indem die Lambda-Rechnung auf Operationen / Berechnungen auf Turing-Maschinen "reduziert" wird. Um die Zeit von Turings Paper 1936 und später wurden verschiedene "umfassende" Berechnungsmodelle vorgeschlagen / zirkuliert. es wurde nicht sofort erkannt, dass alle gleichwertig waren. Die Beweise, dass sie gleichwertig sind, wurden ungefähr in den späten 1930er und 1940er Jahren nach Turings Papier veröffentlicht.

Die Turing-Maschine ist konzeptionell (aber nicht funktional) einfacher als die anderen Modelle. Dies ist wahrscheinlich ein wesentlicher Grund dafür, dass die Turing-Vollständigkeit nach ihm benannt wurde. Andere Ideen wie die Lambda-Rechnung sind abstrakter und haben ihren Ursprung hauptsächlich in der Mathematik / Logik-Theorie. Turing schlug eine theoretische Maschine vor . Eine "Maschine" ist buchstäblich ein "physisches Gerät".. Es ist ein bemerkenswertes konzeptuelles Objekt / eine bemerkenswerte Konstruktion, die zwei verschiedene Welten verbindet, die angewandte und die theoretische. es verleiht physikalischen Entitäten eine neue abstrakte Bedeutung, zB "Zeit und Raum". Es ist kein Zufall, dass Mathematiker manchmal von "Technologie", "Maschinen" oder "Geräten" für Beweise sprechen. Turing ist es gelungen, all dies in seiner konzeptuellen Erfindung genial zu verschmelzen. Die Definition ist recht einfach, aber die Analyse zeigt einige der außergewöhnlichsten neuen Verhaltensweisen, die jemals in der Geschichte des wissenschaftlichen / mathematischen Denkens beobachtet wurden. Turing war der erste Wissenschaftler / Mathematiker, der viel von dieser Bedeutung / Kraft / Potenzial begriff.