In jeder Turing-Complete-Sprache ist es möglich, ein funktionierendes
zu erstellenCompiler für sich selbst, der zuerst auf einem in einer anderen Sprache geschriebenen Interpreter läuft und dann seinen eigenen Quellcode kompiliert? ( Bootstrapping )
Standard-Compilant C ++ - Compiler, der Binärdateien für z. B. Windows ausgibt?
Regex Parser und Evaluator?
World of Warcraft-Klon? (Angenommen, die Sprache erhält die notwendigen API-Bindungen, wie zum Beispiel OpenGL und der WoW-Quellcode ist verfügbar)
(Alles hier theoretisch)
Nehmen wir Brainf * ck als Beispielsprache.
In jeder Turing-Complete-Sprache ist es möglich, ein funktionierendes ...
zu erstellen
Wenn eine Turing-vollständige Sprache das kann, dann können sie alle. In diesem Sinne sind sie alle gleichermaßen "mächtig". Da alles, was Sie beschrieben haben, bereits in mindestens einer Turing-vollständigen Sprache existiert, kann jedes dieser Programme in jeder anderen Turing-vollständigen Sprache geschrieben werden.
Aber nur weil etwas möglich ist bedeutet nicht, dass es einfach oder sogar machbar ist. Das ist eine sehr wichtige Unterscheidung, und es ist der Knackpunkt, warum verschiedene Programmiersprachen existieren. Sie sind nicht alle gleich gut darin, bestimmte Arten von Software zu machen - wenn sie es wären, würden wir nur eine Sprache brauchen!
Nein, Turings Vollständigkeit hat nichts mit I / O und Hardwares zu tun. Sie können jedoch vorgeben, dass I / O, Hardware-Systeme und Grafiksysteme mit Variablen (oder dem "Speicherband") existieren. In BF könnten Sie die ersten 2 Zellen ( x , y ) für die "vorgetäuschte" Bildschirmauflösung verwenden, dann ein anderes x mal y Zellen für alle Pixel auf dem Bildschirm, dann nächste Zelle ( n ) für die "vorgegebene" Dateisystemgröße, dann nächste n Zellen für den Dateisysteminhalt ...
Ja, natürlich, all diese. Das ist, was "Turing-complete" bedeutet: Es kann alles berechnen, was berechnet werden kann.
Alles was Turing-complete wirklich benötigt, ist, dass Sie einfache Mathematik machen, einige Variablen haben und eine while-Schleife machen können. Oder irgendeine Anzahl gleichwertiger Dinge. Wenn Sie echte Programme machen wollen, brauchen Sie ein bisschen mehr (vor allem Syscalls) und Sie müssen sich auch Gedanken um Effizienz machen (Turing-Maschinen können sehr langsam sein ...) Theoretisch gibt es keinen Unterschied zwischen Turing-äquivalenten Systemen, aber in der Praxis da ist.
Wenn jemand einen WoW-Client in BF macht, bin ich sehr beeindruckt!
Jeder Algorithmus, der in einer Turing-Complete-Sprache implementiert werden kann, kann in jedem anderen implementiert werden. Ihre Fragen haben mehr mit den Betriebssystemdiensten und APIs zu tun, die über die jeweilige Sprache zur Verfügung gestellt werden müssen.
Kurz gesagt, die Antwort ist Ja zu allen oben genannten aus formeller Sicht.
Jede Turing-Complete-Sprache könnte denselben Satz von Funktionen berechnen. Eine turing-vollständige Sprache könnte also alles, was Sie geschrieben haben, tun, weil diese Dinge mit anderen Turing-vollständigen Sprachen berechnet werden.
Tags und Links language-agnostic turing-complete