Warum sind einige Programmiersprachen vollständig, aber es fehlen einige Fähigkeiten anderer Sprachen?

42

Beim Schreiben eines Interpreters, der sich an externe Programme / Funktionen anhängt (anhängen sollte), ist ein merkwürdiges Problem aufgetreten: Funktionen in 'C' und 'C ++' können keine unterschiedlichen Funktionen anhängen , z. B. kann ich keine Funktion erstellen , die 'printf' aufruft. mit genau den gleichen Argumenten, die es bekam, und muss stattdessen eine alternative Version aufrufen, die ein variadisches Objekt nimmt. Dies ist sehr problematisch, da ich ein Objekt erstellen möchte, das einen anonymen Hook enthält.

Daher fand ich das seltsam, da Forth , JavaScript und möglicherweise eine Vielzahl anderer Sprachen dies sehr leicht tun können, ohne auf Assemblersprache / Maschinencode zurückgreifen zu müssen. Bedeutet das, dass andere Sprachen dies so einfach können, dass die Klasse von Problemen, die jede Programmiersprache lösen kann, tatsächlich von Sprache zu Sprache unterschiedlich ist, obwohl alle diese Sprachen vollständig sind ?

Mr. Minty Fresh
quelle
33
Sie sollten in turing Tarpits suchen . Sie sind eine faszinierende Art von Programmiersprache, die absichtlich so wenig Operationen wie möglich zur Verfügung hat, während sie noch vollständig sind. Den meisten von ihnen fehlen grundlegende Datentypen, Funktionen, sogar einfache Dinge wie das Deklarieren von Variablen. Persönlich finde ich, dass das Codieren in ihnen großen Spaß macht, da es Sie aus Ihrer Komfortzone zwingt, etwas unnötig Schwieriges auszuprobieren.
DJMcMayhem
8
Schauen Sie sich an, was eine Turing-Maschine leistet, und Sie werden feststellen, dass "Turing-complete" eine sehr geringe Hürde ist, die es zu überwinden gilt. Grundsätzlich ist alles, was lesen, schreiben und springen kann, während Grundrechenarten unterstützt werden, Turing-vollständig. Das ist weit unter dem Niveau der Sprachfunktionen, die Sie suchen.
30.
2
Noch lächerlicher: Die MOV-Anweisung auf einem x86-Prozessor ist Turing-complete. Weitere Informationen finden Sie unter cl.cam.ac.uk/~sd601/papers/mov.pdf .
Gareth McCaughan
3
Auch das Kartenspiel Magic: The Gathering ist Turing-komplett. Turing-Vollständigkeit hat fast nichts mit den Merkmalen einer Sprache zu tun.
Mast
2
Übrigens gibt es auch sehr komplizierte Programmiersprachen, die nicht vollständig sind, wie diese Proof-Checker.
1.

Antworten:

68

NkN

λ

Die Vollständigkeit der Daten sagt nichts über Typen, eingebaute Arrays / Ganzzahlen / Wörterbücher, Eingabe- / Ausgabefunktionen, Netzwerkzugriff, Multithreading, dynamische Zuweisung, ... aus.

Nur weil Java nicht über Feature X verfügt (z. B. Makros, übergeordnete Typen oder abhängige Typen), hört es nicht plötzlich auf, Turing zu beenden.

Vollständigkeit und Ausdruckskraft der Sprache sind zwei verschiedene Begriffe.

chi
quelle
42
Edwin Brady, der Designer von Idris, verwendet scherzhaft (ich weiß nicht, ob er es erfunden hat) den Ausdruck "Tetris-vollständig", um diesen Unterschied zwischen "kann jede berechenbare Funktion auf natürlichen Zahlen berechnen" und "kann" auszudrücken verwendet werden, um nicht triviale Programme zu schreiben, die mit der Umgebung interagieren ".
Jörg W Mittag
12
Sie könnten auch erwähnen, dass Sie diese Dinge in C / C ++ haben könnten. Sie müssen nur Code schreiben, der in C / C ++ als Compiler fungiert, für eine andere Sprache, in der der Code eine Zeichenfolge in Ihrem C / C ++ - Code kompiliert. Dann können Sie einfach etwas wie Java in Ihrer C-Datei programmieren. Das wäre alles viel Arbeit, aber es ist möglich (nachweislich, weil C / C ++ Turing Complete ist).
Shufflepants
4
@Shufflepants Ich frage mich jedoch, ob es wirklich nützlich ist zu sagen, "Ich kann es in C ++ tun, da ich eine andere Sprache interpretieren kann". In diesem Sinne sind Java, ML, C ++ äquivalent. TM mit einem Orakel für Syscalls (I / O) sind ebenfalls gleichwertig. Ich befürchte, dass nach dieser Überlegung praktisch alle Sprachen gleichermaßen ausdrucksstark sind. Wenn ja, ist es kein nützlicher Begriff, Sprachen zu vergleichen.
Chi
9
@chi Du hast recht, sie sind gleichwertig. Genau das bedeutet es, Turing Complete zu sein. Alles, was mit einem Turing Complete-System gemacht werden kann, kann mit einem anderen Turing Complete-System gemacht werden. Es ist möglicherweise nicht bequem, dies in einem bestimmten System zu tun. Und die Bequemlichkeit, verschiedene Dinge zu tun, ist die Hauptmethode, mit der wir verschiedene Programmiersprachen vergleichen. Aber das war nicht das, was die Frage stellte.
Shufflepants
5
@Rhymoid Wenn C aus Gründen des Speicherzugriffs nicht Turing Complete ist oder weil das Senden von beliebigen Signalen an ein angeschlossenes Gerät mit beliebig großem Speicherplatz nicht zählt, könnte man argumentieren, dass keine Sprache oder kein Gerät der realen Welt Turing Complete ist . Aber ich glaube nicht, dass dies eine sehr produktive Argumentationslinie ist.
Shufflepants
47

Vollständigkeit ist ein abstrakter Begriff der Berechenbarkeit. Wenn eine Sprache Turing vollständig ist, ist sie in der Lage, alle Berechnungen durchzuführen, die eine andere Sprache von Turing vollständig ausführen kann.

Dies sagt jedoch nicht, wie bequem es ist, dies zu tun. Einige Funktionen, die in einigen Sprachen einfach sind, können in anderen aufgrund der Auswahl des Designs sehr schwierig sein. Turing Vollständigkeit sagt nur , dass Sie kann die Berechnung tun. Als extremes Beispiel mag es schwierig sein, varadische Funktionen in C ++ einzuhängen, aber es ist möglich, einen JavaScript-Interpreter in C ++ zu schreiben, der variadische Funktionen einbinden kann.

Sprachdesign ist eine ziemlich interessante Kunst. Einer der wichtigsten Schritte ist die Ermittlung der Verhaltensweisen, die das Rückgrat Ihrer Sprache bilden sollen. Diese Verhaltensweisen sind Dinge, die in Ihrer Sprache einfach zu tun sind, weil sie im Erdgeschoss eingebaut sind. Wir treffen Entwurfsentscheidungen darüber, welche Funktionen in jeder Sprache enthalten sein sollen.

In Bezug auf Ihr spezielles Beispiel, als C entwickelt wurde, wurde es so konzipiert, dass es sehr nahe an den Assemblersprachen des Tages arbeitet. Variadic-Funktionen haben einfach Argumente mit sehr geringer Typensicherheit auf den Stapel geschoben. Die Implementierung dieser variablen Funktionen wurde dem Compiler überlassen, um maximale Portabilität zu gewährleisten. Dementsprechend wurden nur sehr wenige Annahmen über die Leistungsfähigkeit der Hardware getroffen. Als JavaScript auf den Markt kam, hatte sich die Szene geändert. Es wird bereits in einer virtuellen Maschine als interpretierte Sprache ausgeführt, sodass sich das Gleichgewicht in Richtung Bequemlichkeit verlagert. Das Zulassen des Einhängens verschiedener Funktionen wird sinnvoll. Selbst im Fall von JavaScript, das Just In Time Compiled ist, sind unsere Compiler bereit, weitaus mehr zusätzliche Informationen über die Argumente zu speichern, als die C-Compiler von früher zu speichern bereit waren.

Cort Ammon
quelle
1
@Wildcard Ich würde (fast) alle Compiler als unsauber ansehen. Die meisten Sprachen sind Turing-komplett, müssen aber eventuell von der Assembly interpretiert / kompiliert werden, was nicht der Fall ist. Dies ist jedoch eine notwendige physikalische Einschränkung - Hardware ist niemals leistungsfähig. Die Berechenbarkeit bietet jedoch viele nützliche Konzepte, die in praktischer Hinsicht auf reale Computer "zutreffen".
Chi
3
@Wildcard In diesem trivialen Sinne. Assembly (und C) haben Zeiger mit fester Größe, die nur eine begrenzte Menge an Speicher adressieren können. Theoretisch könnten wir eine Assembly definieren, in der Zeiger unbegrenzt natürlich sind, aber ich würde diese Assembly nicht mehr als "Assembly" bezeichnen - ich würde sie als URM oder so ähnlich bezeichnen. In der Praxis geben wir einfach vor, dass die physischen Grenzen groß genug sind, um die Ausführung unserer Programme zu ermöglichen. Selbst wenn ein Computer nur eine Finite-State-Maschine ist (was bedeutet, dass er zB keine Addition ausführen kann), denken wir eher über eine Turing-Maschine nach ( so ist der Zusatz machbar).
Chi
4
@chi Das ist nicht ganz richtig. Zuallererst betrachtet praktisch jeder C als vollständig, da wir diese Formulierung in der Regel mit der Annahme verbinden, dass "Sie genug Speicher haben". Für die sehr kleine Anzahl von Personen, die sich um die strengere Formulierung sorgen müssen, bei der solche Annahmen ungültig sind, gibt C nicht die Größe eines Zeigers an und gibt keine Grenze an, wie viel Speicher adressiert werden kann. Selbst im absolut strengsten Sinne von "Turing vollständig" ist C in der Tat "Turing vollständig".
Cort Ammon
3
@ CortAmmon Ich muss nicht zustimmen. Wenn wir die Semantik von C formalisieren und versuchen, die Annahme "genügend Speicher" einzubetten, würden wir scheitern, da sizeof(void *)die Bewertung nach dem ISO-C-Standard vorgeschrieben ist. Dies zwingt uns, die Speicherkapazität für ein bestimmtes Programm an etwas Großes zu binden - aber immer noch an eine Grenze. Ich kann zB kein Programm schreiben, dessen Semantik zwei willkürliche Naturalien hinzufügt. C könnte durch I / O noch leistungsfähiger gemacht werden, indem Dateien wie TM-Bänder verwendet werden (wie @Hurkyl oben erwähnt). Ich bin damit einverstanden, dass dies in der Praxis kein Problem darstellt.
Chi
7
Ich schlage die neue Sprache C-inf vor, die genau wie C ist, außer wenn durch Rekursion oder Heap-Zuweisung zu viel Speicher zugewiesen wird, wird das Programm abgebrochen und mit einem größeren Wert für sizeof (void *) und sizeof (size_t) neu kompiliert. und fängt wieder von vorne an zu laufen.
gnasher729
26

Stellen Sie sich Programmiersprachen als verschiedene Landfahrzeuge vor: Fahrräder, Autos, Hovercars, Züge.

Turing Completeness sagt: "Dieses Fahrzeug kann überall hingehen, wo jedes andere Fahrzeug hingehen kann." Das heißt, Sie können dieselben Funktionen berechnen. Eingabe zu Ausgabe, Start zu Ende.

Diese Aussage sagt jedoch nichts darüber aus, wie Sie dorthin gelangen. Es könnte auf Schienen sein, es könnte auf Straßen sein, es könnte in der Luft sein. Ebenso sagt Turing Completeness nichts darüber aus, wie Sie eine Funktion berechnen. Sie können Rekursion oder Iteration oder einige seltsame zellulare Automaten verwenden. Sie können Typen verwenden oder nicht, Sie können dynamische oder statische Techniken verwenden. Wenn Sie jedoch nur Funktionen (oder Mengen / formale Sprachen) in Betracht ziehen, können Sie diese Funktionen berechnen, solange Sie Turing Complete ausführen.

jmite
quelle
4
Dies ist eine großartige Analogie. Es erstreckt sich auch gut auf die Frage, die ich an anderer Stelle auf dieser Website gesehen habe, ob es andere Rechenmodelle geben könnte, die eine Turing-Maschine übertreffen: In dieser Analogie sind Flugzeuge und Raumschiffe mehr als Turing Complete, und Schnellboote sind andere Art der Maschine ganz. :)
Wildcard
2
Schneller als leichtes Reisen ist wahrscheinlich eine bessere Analogie für Super-Turing-Berechnungen. Es mag möglich sein, aber die meisten Leute denken, dass es nicht so ist.
Mittwoch,
@jmite Natürlich gibt es noch keine guten Beweise dafür, dass es sich bei unserem Gehirn um überragende Computer handelt. Unsere (offensichtliche) Unfähigkeit, Maschinen zu berücksichtigen, die nicht funktionieren, könnte darauf zurückzuführen sein, obwohl dies nicht unbedingt eine unüberwindbare Barriere ist. Flugzeuge sind eigentlich eine gute Analogie - sie bewegen sich einfach "geradeaus" zwischen zwei Punkten und ignorieren dabei das Gelände. Wenn wir die Topologie der Raumzeit selbst ignorieren könnten, könnten wir auch schneller als das Licht fliegen. Nicht, dass ich sage, dass es möglich ist , die Topologie der Raumzeit zu ignorieren,
wohlgemerkt
1
@Luaan Richtig, aber unser Gehirn muss nicht unbedingt super-Turing sein, um einen super-Turing-Computer zu verstehen. Ich kann die Semantik einer Turing-Maschine mit einer schwächeren Terminierungssprache wie Simply Typed Lambda Calculus beschreiben, indem ich eine Funktion schreibe, die ein TM und seinen Zustand aufnimmt und in den nächsten Zustand überführt. Ich kann den Computer nicht in dieser Sprache ausführen (da dies möglicherweise unendlich viele Schritte erfordert), aber ich kann schreiben, wie jeder Schritt aussieht.
Mittwoch,
@Luaan, "es gibt immer noch keine guten Beweise, die darauf hindeuten, dass unsere Gehirne Super-Turing-Computer sind" - vielleicht, aber es gibt auch keine Beweise, die darauf hindeuten, dass der menschliche Geist nur eine Turing-Maschine ist. Da es keine Turing - Maschine ist, die überall gerichtet werden kann , die nicht auf Ideen zurückverfolgt werden kann von einem Menschen stammt Geistes gibt es noch die Unterscheidung , dass das Leben kann entstehen Ideen und mechanische Vorrichtungen nicht. Was aber die Rechenmodelle betrifft, denke ich, dass Turing-Maschinen alles erfolgreich umfassen, was vernünftigerweise als "Berechnung", Ideen und Träume und so weiter bezeichnet werden kann.
Wildcard
17

Was Sie im Wesentlichen fragen, ist der Unterschied zwischen der Rechenkraft und der Ausdruckskraft (oder einfach Ausdruckskraft ) einer Sprache (oder eines Rechensystems).

Rechenleistung

Die Rechenleistung bezieht sich darauf, welche Arten von Problemen die Sprache berechnen kann. Die bekannteste Klasse von Rechenleistung ist diejenige, die einer Universal-Turing-Maschine entspricht . Es gibt viele andere Rechensysteme, wie z. B. Random Access Machines , λ-Kalkül , SK-Kombinator-Kalkül , µ-rekursive Funktionen , WHILEProgramme und viele andere. Und wie sich herausstellt, können sich alle gegenseitig simulieren, was bedeutet, dass sie alle die gleiche Rechenleistung haben.

Daraus entsteht die Church-Turing-These (benannt nach Alonzo Church , der die λ-Rechnung erstellt hat, und Alan Turing , der die Universal Turing Machine erstellt hat). Die Church-Turing-These ist eine Hypothese zur Berechenbarkeit mit zwei Aspekten:

  1. alle allgemein berechenbaren Rechnersysteme sind gleich leistungsfähig und
  2. Ein Mensch, der einem Algorithmus folgt, kann genau die Funktionen berechnen, die eine Turing-Maschine (und damit eines der anderen Systeme) berechnen kann.

Die zweite ist jedoch im Bereich der Philosophie des Geistes wichtiger als die Informatik.

Es gibt jedoch zwei Dinge, die die Church-Turing-These nicht sagt und die für Ihre Frage sehr relevant sind:

  1. wie effizient die verschiedenen Simulationen sind und
  2. wie bequem die Kodierung eines Problems ist.

Ein einfaches Beispiel für (1): Auf einem Computer mit wahlfreiem Zugriff dauert das Kopieren eines Arrays proportional zur Länge des Arrays. Bei einer Turing-Maschine dauert die Zeit jedoch proportional zum Quadrat der Länge des Arrays, da die Turing-Maschine keinen wahlfreien Speicherzugriff hat und sich nur zellenweise über das Band bewegen kann. Daher muss es sich n- mal über die n Elemente des Arrays bewegen, um sie zu kopieren. Daher können verschiedene Berechnungsmodelle auch im asymptotischen Fall, in dem versucht wird, von Implementierungsdetails abzuweichen, unterschiedliche Leistungsmerkmale aufweisen.

Beispiele für (2) gibt es zuhauf: Sowohl λ-Kalkül als auch Python sind Turing-vollständig. Aber möchten Sie lieber ein Programm in Python oder in λ-Kalkül schreiben?

Es gibt auch eine dritte Falte, die ich bis jetzt umgangen habe: Alle diese ursprünglichen Systeme wurden von Logikern, Philosophen oder Mathematikern entworfen, nicht von Informatikern… einfach, weil Computer und damit Informatik nicht existierten. Diese alle gehen zurück zu den frühen 1930er Jahren, noch vor Konrad Zuse ist sehr erste Experimente (die nicht programmierbar und / oder Turing-complete ohnehin waren). Sie sprechen nur von "berechenbaren Funktionen auf den natürlichen Zahlen".

Nun, wie sich herausstellt, gibt es eine Menge, die Sie als Funktionen auf natürlichen Zahlen ausdrücken können - schließlich kommen unsere modernen Computer sogar mit viel weniger aus (im Grunde 3-4 Funktionen auf den Zahlen 0 und 1, und das war's ), aber welche Funktion berechnet beispielsweise ein Betriebssystem?

Diese Vorstellung von I / O-Nebenwirkungen, die mit der Umgebung interagieren, wird von der Idee der "Funktionen über natürlichen Zahlen" nicht erfasst. Und doch ist es irgendwie wichtig, da, wie Simon Peyton Jones einmal legt es „All eine reine Funktion ohne Nebenwirkungen, ist Ihre CPU heiß machen“ , zu dem ein Zuschauer antwortete „tatsächlich, das ist eine Seite -Effekt auch! "

Edwin Brady , der Designer von Idris , verwendet scherzhaft (ich weiß nicht, ob er es erfunden hat) den Ausdruck "Tetris-vollständig", um diesen Unterschied zwischen "kann jede berechenbare Funktion auf natürlichen Zahlen berechnen" und "kann" auszudrücken verwendet werden, um nicht triviale Programme zu schreiben, die mit der Umgebung interagieren ". Ironischerweise demonstriert er dies durch die Implementierung eines Space Invaders-Klons in Idris , ist jedoch zuversichtlich, dass Tetris sich zu Space Invaders reduziert.

Eine andere Sache, die hervorgehoben werden muss, ist, dass nicht nur die Turing-Äquivalenz nicht unbedingt ausreicht, um über das tatsächliche Schreiben von "nützlichen" Programmen zu sprechen, sondern dass OTOH möglicherweise auch nicht einmal notwendig ist . Zum Beispiel ist SQL erst mit ANSI SQL: 1999 Turing-äquivalent geworden , aber vorher war es noch nützlich. In der Tat könnten einige argumentieren, dass die Herstellung eines Turing-Äquivalents überhaupt nicht zu seiner Nützlichkeit beigetragen hat. Es gibt viele domänenspezifische Sprachen, die nicht Turing-äquivalent sind. Datenbeschreibungssprache ist normalerweise nicht (und sollte es auch nicht sein). Total Languages ​​kann natürlich nicht Turing-äquivalent sein, Sie können jedoch Ereignisschleifen, Webserver oder Betriebssysteme darin schreiben. Es gibt auch Sprachen, die Turing-äquivalent sind, bei denen dies jedoch als Fehler angesehen wird.

Alles in allem ist die Turing-Äquivalenz also nicht besonders interessant, es sei denn, Sie möchten Programme statisch analysieren.

Ausdruckskraft

Unter der Annahme, dass unser Rechensystem leistungsfähig genug ist, um unser Problem überhaupt zu lösen, müssen wir als Nächstes unseren Algorithmus zum Lösen dieses Problems in einer Art formaler Notation für dieses System ausdrücken. Mit anderen Worten: Wir müssen ein Programm in einer Computersprache schreiben. Hier kommt der Begriff der Ausdruckskraft ins Spiel.

Es bezieht sich im Wesentlichen darauf, wie "einfach" oder "angenehm" es ist, unser Programm in unserer speziellen Programmiersprache zu schreiben. Wie Sie sehen können, ist der Begriff ziemlich vage, subjektiv und eher psychologisch als technisch.

Es gibt jedoch Versuche, die Definitionen zu präzisieren. Der bekannteste (und strengste, den ich kenne) stammt von Matthias Felleisen in seinem Aufsatz Über die Ausdruckskraft von Programmiersprachen (die ersten beiden Seiten enthalten eine sanfte Einführung, der Rest des Aufsatzes ist fleischiger).

Die Hauptintuition ist folgende: Wenn Sie ein Programm von einer Sprache in eine andere Sprache übersetzen, sind einige der Änderungen, die Sie vornehmen müssen, lokal enthalten (wie z. B. FORSchleifen in WHILESchleifen oder Schleifen in bedingte GOTOs umwandeln), und einige erfordern eine Änderung der globalen Struktur des Programms.

Wenn Sie ein Merkmal einer Sprache nur durch lokale Transformationen durch ein anderes Merkmal einer anderen Sprache ersetzen können, haben diese Merkmale keine Auswirkung auf die Ausdruckskraft. Dies nennt man syntaktischen Zucker .

Wenn es andererseits erforderlich ist, die globale Struktur des Programms zu ändern, kann die Sprache, in die Sie übersetzen, die Funktion nicht ausdrücken. Die Sprache, aus der Sie übersetzen, soll aussagekräftiger sein (in Bezug auf diese Funktion).

Beachten Sie, dass dies eine objektiv messbare Definition der Ausdruckskraft gibt. Beachten Sie auch, dass der Begriff kontextabhängig und vergleichend ist. Also, wenn jedes Programm in der Sprache A kann Sprache übersetzt wird B mit nur lokalen Veränderungen, und es gibt mindestens ein Programm in Sprache B , das kann nicht übersetzt wird A mit nur lokalen Änderungen, dann Sprache B ist streng ausdrucksvoller als Sprache EIN. Das wahrscheinlichere Szenario ist jedoch, dass viele Programme in beiden Sprachen hin und her übersetzt werden können, aber es gibt einige Programme in beiden Sprachen, die nicht in die andere übersetzt werden können. Dies bedeutet, dass keine Sprache strikt aussagekräftiger ist als die andere. Sie verfügen lediglich über unterschiedliche Funktionen, mit denen unterschiedliche Programme auf unterschiedliche Weise ausgedrückt werden können.

Dies gibt eine formale Definition dessen, was es bedeutet, "ausdrucksvoller" zu sein, erfasst aber immer noch nicht die psychologischen Vorstellungen, die hinter dem Phänomen stehen. Beispielsweise erhöht syntaktischer Zucker nach diesem Modell nicht die Ausdruckskraft einer Sprache, da er nur durch lokale Änderungen übersetzt werden kann. Aber wir wissen aus Erfahrung , dass mit FOR, WHILEund zur IFVerfügung, auch wenn sie nur syntaktischer Zucker für die bedingten sind GOTOMarken zum Ausdruck unserer Absicht leichter .

Tatsache ist, dass verschiedene Sprachen unterschiedliche Merkmale haben, die es leichter oder schwerer machen, unterschiedliche Denkweisen über ein Problem auszudrücken. Und manche Menschen finden vielleicht eine Möglichkeit, ihre Absicht leichter auszudrücken, und andere eine andere.

Ein Beispiel, das ich im Ruby-Tag auf StackOverflow gefunden habe: Viele Benutzer, die dem Ruby-Tag folgen, behaupten, dass Schleifen einfacher zu verstehen sind als Rekursion und Rekursion nur für fortgeschrittene funktionale Programmierer und Schleifen für Neueinsteiger intuitiver komplette Neulinge, die intuitiv Code wie folgt schreiben:

def rock_paper_scissors
  get_user_input
  determine_outcome
  print_winner
  rock_paper_scissors # start from the top
end

Was normalerweise dazu führt, dass mehrere Leute kommentieren, dass "das nicht funktioniert" und "sie es falsch machen" und der "richtige Weg" ist:

def rock_paper_scissors
  loop do
    get_user_input
    determine_outcome
    print_winner
  end
end

Offensichtlich gibt es einige Leute, für die die Schwanzrekursion eine natürlichere Art ist, das Konzept des "Schleifens" auszudrücken als Schleifenkonstrukte.

Zusammenfassung

Die Tatsache, dass zwei Sprachen Turing-äquivalent sind, sagt eins und genau eines aus: Sie können die gleichen Funktionen für natürliche Zahlen berechnen wie eine Turing-Maschine. Das ist es.

Es sagt nichts darüber aus, wie schnell sie diese Funktionen berechnen. Es sagt nichts darüber aus, wie einfach es ist, diese Funktionen auszudrücken. Und es sagt nichts darüber aus, was sie außer der Berechnung von Funktionen für natürliche Zahlen noch tun können (z. B. Verknüpfung mit C-Bibliotheken, Lesen von Benutzereingaben, Schreiben von Ausgaben auf den Bildschirm).

Bedeutet das, dass die Klasse von Problemen, die jede Programmiersprache tatsächlich lösen kann, von Sprache zu Sprache unterschiedlich ist, obwohl diese Sprachen alle vollständig sind?

Ja.

  1. Es gibt Probleme, die nicht unter den Begriff "Turing-complete" fallen (der sich nur mit Rechenfunktionen für natürliche Zahlen befasst), beispielsweise das Drucken auf dem Bildschirm. Zwei Sprachen können Turing-vollständig sein, aber eine kann das Drucken auf dem Bildschirm ermöglichen und die andere nicht.
  2. Selbst wenn beide Sprachen die gleichen Probleme lösen können, sagt das nichts darüber aus, wie komplex die Codierung ist und wie einfach es ist, diese Codierung auszudrücken. ZB kann C jedes Problem lösen, das Haskell kann, indem Sie einfach einen Haskell-Interpreter in C schreiben. Sie müssen jedoch zuerst den Haskell-Interpreter schreiben, um ein Problem auf diese Weise zu lösen!
Jörg W. Mittag
quelle
7

Alle Programmiersprachen von Turing complete können die gleichen Algorithmen implementieren. Wenn Sie also feststellen, dass es sehr schwierig ist, einen Algorithmus in einer bestimmten Sprache zu implementieren, bedeutet dies nicht, dass dies unmöglich ist.

Denken Sie daran, dass eine Sprache aus Syntax und Semantik besteht. Manchmal ist die Menge der Wörter, die zu einer Sprache gehören, kein Minimum, um als vollständig angesehen zu werden. Es gibt Funktionen , die die Dinge einfacher machen (deshalb werden sie Funktionen genannt ). Wenn Sie diese Funktionen herausnehmen, ist die Sprache immer noch vollständig.

Einige davon könnten von Interesse sein:

Euge
quelle
5

Alle Turing-complete-Sprachen können die gleichen Dinge berechnen.

Wenn Sie versuchen, eine moderne Sprache zu implementieren, werden Sie feststellen, dass die meisten Funktionen keine Rechenfunktionen hinzufügen . Viele dieser Funktionen können auf einfachere Funktionen reduziert werden, die bereits in derselben Sprache vorhanden sind.

Hier sind einige Beispiele:

  • Wenn Sie keine Aufzählungen haben, können Sie ganze Zahlen verwenden.
  • Wenn Sie keine Puffer haben, deren Größe bekannt ist, können Sie einen Typ erstellen, der eine Größe und einen Puffer enthält, dessen Größe nicht bekannt ist.
  • Wenn Sie keine Überprüfung der Puffergrenzen haben, können Sie den Index einfach jedes Mal überprüfen, wenn Sie sie verwenden.
  • Wenn Sie keine variablen Funktionen haben, können Sie eine Funktion erstellen, die einen Puffer verwendet, dessen Größe bekannt ist, und aus diesem Puffer dieselben Informationen lesen, die Sie aus formalen Argumenten erhalten würden.
  • Wenn Sie keine Operatoren haben, können Sie Funktionen verwenden.
  • Wenn Sie keine Typen haben, die sich gegenseitig erben können, können Sie Typen erstellen, die sich gegenseitig enthalten, und über eine zusätzliche Indirektionsebene auf sie zugreifen, wobei die Untertypisierung einfach eine Umwandlung des Handles in den gesamten Typ in einen ist Handle-to-the-Contained-Typ.
  • Wenn Sie keine Delegaten, aber Funktionszeiger haben, können Sie einen Typ erstellen, der das Referenzobjekt und einen Funktionszeiger enthält.
  • Wenn Sie keine Delegaten, aber Schnittstellen haben, können Sie eine Schnittstelle deklarieren, die eine einzelne Methode mit der gewünschten Signatur enthält.
  • Wenn Sie keine generischen Typen haben, können Sie nicht generische Typen verwenden, die nur die Ober- oder Untergrenzen annehmen, an denen Sie interessiert sind (und möglicherweise entsprechende Casts an den Verwendungspunkten durchführen, um den Compiler bei Laune zu halten).
  • Wenn Sie kein lineares / affines Typsystem haben, können Sie einfach vermeiden, eine Variable mehr als einmal zu verwenden.
  • ...und so weiter.

Das Mainstream-Sprachdesign konzentriert sich auf Funktionen, die es uns einfacher und bequemer machen, schneller zu rechnen, unsere Fehler früher zu erkennen, unbekannte Komponenten zu programmieren, die Parallelität sicherer zu machen und so weiter.

Das rein rechnerische Zeug wurde vor langer Zeit festgenagelt.

Theodoros Chatzigiannakis
quelle
4

Die vorhandenen Antworten weisen zu Recht darauf hin, dass die Vollständigkeit von Turing kein guter Weg ist, um Sprachen zu vergleichen. Tatsächlich sind fast alle Sprachen vollständig. ("Wenn jeder etwas Besonderes ist, dann ist niemand etwas Besonderes", wie die Unglaublichen sagten.)

Es ist jedoch möglich, die Ausdruckskraft von Sprachen mit mathematischer Präzision zu vergleichen. Schauen Sie sich Felleisens Über die Ausdruckskraft von Programmiersprachen an . Die Idee ist ungefähr, die folgende Frage zu stellen: Kann ich jedes Programm in Sprache A in ein Programm in Sprache B konvertieren, indem ich nur lokale Änderungen vornehme? Mit anderen Worten, Felleisen gibt Ihrer Intuition eine mathematisch präzise Form.

rgrig
quelle
2

Neben den Antworten aller anderen ist hier eine weitere Analogie.

Um Kleidung zu waschen, braucht man drei Dinge: ein Reservoir, das Wasser enthält, ein Reinigungsmittel und einen Rührmechanismus. Dies könnte auf viele Arten realisiert werden. Das Wasserreservoir ist alles, was genügend Wasser enthält (z. B. eine Wanne, ein See, ein Fluss). Der Bewegungsmechanismus kann eine mechanische Vorrichtung, ein Waschbrett oder sogar ein Stein sein, gegen den die Kleidung geschlagen wird. Und Waschmittel gibt es auch in verschiedenen Formen.

Was ist der Unterschied zwischen einer modernen Computer-Waschmaschine und einem Felsen neben einem Fluss?

Es läuft auf drei Dinge hinaus: Effizienz, Sicherheit und Komfort. Einige Waschmethoden verbrauchen weniger Energie, belasten die Umwelt weniger, verbrauchen weniger Wasser und so weiter. Einige Waschmethoden erfordern weniger wiederholte manuelle Tätigkeiten (die zu Verletzungen führen) oder sind bei schlechtem Wetter draußen. Für einige Waschmethoden ist kein Mensch erforderlich, um den Prozess zu überwachen.

Turing-complete-Programmiersprachen sind universell einsetzbar und werden daher für mehr als eine Aufgabe eingesetzt. Dennoch sind einige Programmiersprachen für eine bestimmte Aufgabe effizienter, bequemer und sicherer (in dem Sinne, dass weniger schief gehen kann, wenn das Programm tatsächlich verwendet wird) als andere.

Pseudonym
quelle
2

Andere haben viele gute Antworten geliefert, erwähnen aber nicht ausdrücklich einen Vorbehalt, der mich einmal sehr verwirrt hat: Vollständigkeit bedeutet nicht, dass eine Sprache beliebige berechenbare Funktionen von ihren Eingaben bis zu ihren Ausgaben ausdrücken kann. Es ist schwächer: es muss einige Weise die Domäne darstellt , und den Bereich des Satzes von berechenbaren Funktionen als Ein- und Ausgänge , so daß jede dieser Funktionen abbildet auf ein Programm , das eine Darstellung der Eingänge an die entsprechenden Ausgänge erfolgt.

Nehmen wir zum Beispiel eine Sprache, die Turing-Maschinen ausdrückt. Jedes Programm in der Sprache ist eine Turingmaschine.

Betrachten Sie nun die Subsprache aller Turing-Maschinen, die nur die Zeichen a, b und blank lesen und schreiben. Es ist Turing complete, kann aber keine Programme ausdrücken, die zum Beispiel c für alle Eingaben erzeugen, da es kein cs schreiben kann. Es kann nur alle berechenbaren Funktionen an Ein- und Ausgängen ausdrücken, die als Zeichenfolgen von as und bs codiert sind.

Es ist also nicht wahr, dass alle Turing-vollständigen Sprachen die gleichen Dinge berechnen können, auch wenn wir diese Dinge auf die berechenbaren Funktionen von ihren potentiellen Eingaben bis zu ihren potentiellen Ausgaben beschränken. Für die Sprache müssen möglicherweise Ein- und Ausgänge auf bestimmte Weise codiert werden.

reinierpost
quelle