Ich habe gehört, dass ein Programmierer, der genug Zeit und Fähigkeiten in einer bestimmten Sprache und genügend Codezeilen hat, ein Programm mit einer beliebigen Sprache erstellen kann. Ich weiß, dass es sicherlich nicht kosteneffektiv sein wird, zum Beispiel Adobe Photoshop in BASIC umzuschreiben, aber könnte ein gut genug und geduldig genug Programmierer möglicherweise irgendein Programm in irgendeiner Sprache erstellen?
Wenn eine Sprache Turing abgeschlossen ist, dann kann theoretisch jedes Programm darin geschrieben werden - aber auch das hat einige Einschränkungen wie Benutzerschnittstelle und Betriebssystem-APIs. Zum Beispiel ist Brainfuck Turing vollständig, aber es gibt keine Möglichkeit, eine GUI zu haben, weil Sie nicht auf den Videospeicher zugreifen können, und Es gibt keine Threading-Unterstützung. Es ist jedoch möglich, eine Rechenaufgabe damit zu erledigen.
Das hängt davon ab, wie genau Sie "jedes Programm" und "jede Sprache" definieren.
Beginnen wir mit dem ersten: "jedes Programm". Es gibt viele Programme (tatsächlich gibt es unendlich viele Programme), die überhaupt nicht geschrieben werden können , unabhängig von der Programmiersprache. Eine der bekanntesten ist das sogenannte Halting-Problem: Schreiben Sie ein Programm H , das bei Angabe eines Programms P und einer Eingabe x bestimmt, ob P(x) schließlich anhält. Alan Turing hat vor vielen Jahrzehnten bewiesen, dass es für ein solches Programm unmöglich ist zu existieren. Ergo, Sie können dieses Programm nicht in der Programmiersprache any schreiben.
Nun reden wir über "jede Sprache". Es gibt tatsächlich verschiedene Klassen von Sprachen. Manche sind mächtiger als andere. Zum Beispiel können reguläre Ausdrücke (die sind eine Art Programmiersprache) nicht eine beliebige Funktion berechnen. Sie sind in ihrer Rechenleistung begrenzt. Die meisten Programmiersprachen für allgemeine Zwecke werden jedoch allgemein als "Turing-vollständig" bezeichnet.
Kurze Geschichte: Um die Unentscheidbarkeit des Halteproblems zu beweisen, erfand Alan Turing eine hypothetische Maschine namens Turing Machine. Ein TM ist im Grunde ein hypothetischer Computer mit unendlichem Speicher, der eine bestimmte Funktion berechnet. Es stellt sich heraus, dass Sie eine Universal Turing Machine bauen können, die jede andere Turing Machine emulieren kann.
Ungefähr zur selben Zeit erfand die Alonzo-Kirche den Lambda-Kalkül. Die LC ist auch ein abstraktes mathematisches Modell der Berechnung, aber vollständig anders. Die Leute begannen sich zu fragen: Welches dieser beiden Modelle ist stärker? Gibt es etwas, was ein UTM berechnen kann, was LC nicht kann und umgekehrt? Kann das LC das Halteproblem lösen?Wie sich herausstellt, können Sie einen Emulator für eine UTM in LC schreiben und ein TM erstellen, das LC interpretiert. Dies bedeutet, dass ein TM alles berechnen kann, was LC berechnen kann (indem es einfach im Interpreter ausgeführt wird) und LC kann alles berechnen, was ein UTM berechnen kann (indem es es einfach im Emulator ausführt). Also, wir haben
%Vor% In Englisch: LC und UTM sind genau gleich stark. Tatsächlich stellt sich heraus, dass jedes Modell der Berechnung und jede Maschine und jede Programmiersprache, die wir jemals gefunden haben, höchstens
Wir nennen solche Modelle der Berechnung Turing-vollständig . Und, BTW, Sie brauchen nicht viel Turing-vollständig .
Damit können wir jetzt definieren, was wir mit "jedem Programm" und "jeder Sprache" meinen:
Wenn ein Programm in einer Turing-vollständigen Sprache geschrieben werden kann, dann kann es in jeder Turing-vollständigen Sprache geschrieben werden.
Es ist alles eine Frage der Zeit, oder? Das Fehlen geeigneter Bibliotheken und APIs, die für BASIC verwendet werden können, kann dazu führen, dass das Adobe Photoshop-Projekt für immer in Anspruch nimmt. Wenn es fertig ist, läuft es möglicherweise nicht reibungslos, ist aber theoretisch machbar.
Die Sprache muss Turing-vollständig sein und außerdem eine Möglichkeit für den Zugriff auf das native Betriebssystem für viele verschiedene Operationen wie Dateien, Sockets usw. benötigen.
Sicher (sorta). Es gibt einen Kompromiss, Leistung. Einige Sprachen sind möglicherweise nicht in der Lage, auf bestimmte Funktionen des Systems zuzugreifen, wodurch bestimmte Aufgaben auf dem Computer nicht ausgeführt werden können. Einige Sprachen sind nur ... schwächer als andere und es würde eine Weile dauern.
Sie müssen vorsichtig sein mit dem, was Sie mit "jedem Programm" meinen. Wenn Sie zum Beispiel aufgefordert werden, ein Programm zu schreiben, das eine Textdatei auf dem Datenträger mit "Hello world" erstellt, und Sie aufgefordert wurden, es in reinem Javascript zu schreiben, wäre das unmöglich, weil reines Javascript keine Möglichkeit hat, etwas auf die Festplatte zu schreiben .
Für eine gründliche Diskussion dieser Idee möchten Sie vielleicht die Berechenbarkeit lesen.
Wenn Sie "... auf einem leistungsfähigen Computer hinzugefügt haben, und vorausgesetzt, dass die Sprache über Bibliotheken verfügt, die mit allem fertig werden können, was das Programm benötigt", dann wäre die Antwort immer noch nein. Manche Sprachen können Programmierer so verrückt machen, dass sie sich umbringen. Wenn ich jemals gezwungen würde, zurück zu Visual Basic 3 (keine Klassen oder Sammlungen) zu gehen, würde ich nicht wissen, wie man Notepad neu schreibt.
Ich denke, wenn Sie "kreativ genug" hinzufügen und die Auswertungen als Programmierung und die Definition von "jedem Programm" als ein bestehendes Programm betrachten, lautet die Antwort ja.
Tags und Links programming-languages