Können Sie eine Programmiersprache ohne Implementierung angeben?

Ist es theoretisch möglich, eine Programmiersprache anzugeben, für die keine Implementierung existieren könnte? Eine Programmiersprache ist eine Möglichkeit, Funktionen zu definieren. Eine Implementierung bedeutet ein Verfahren zum Ausführen eines bestimmten Programms in dieser Sprache an einem bestimmten Eingang zum Ausgang der Funktion, die dem Programm an diesem Eingang entspricht.

Was sind die Mindestanforderungen an eine solche Sprache?

Normalerweise bedeutet die Implementierung einer Programmiersprache, dass mindestens ein Interpreter in einer Sprache (oder ein Compiler für eine Sprache) angegeben wird, die nicht mehr als Turing-vollständig ist.

Mit dieser "Definition" können wir eine Programmiersprache wie diese angeben:

• es gibt nur ein mögliches Programm HALT;

• Spezifikation von HALT: Es ist eine Funktion, die das Halteproblem löst .

Die Implementierung dieser Programmiersprache erfordert die Lösung des Halteproblems mit der Implementierung. (Was unmöglich ist, da unsere Implementierung nicht leistungsfähiger sein sollte als eine Turing-Maschine).

Die Spezifikation behandelt die Logik und kann daher viel mehr verlangen. Eine andere Spezifikation, die nicht implementiert werden kann, ist "false". (Oder irgendein widersprüchlicher Satz in der Spezifikation) Aber dies fühlt sich nicht wie eine Spezifikation an, weshalb ich das Beispiel für das Stoppproblem verwendet habe.

Nur eine merkwürdige Randnotiz: Die C ++ - Vorlagen-Engine ist Turing-vollständig

Satz 1: Ohne Instanziierungsgrenzen sind C ++ - Vorlagen Turing-vollständig.

Folgerung 1: In Ermangelung von Instanziierungsbeschränkungen ist nicht zu entscheiden, ob ein C ++ - Compiler beim Kompilieren eines bestimmten Programms angehalten wird.

... so kann das C ++ selbst als Programmiersprache betrachtet werden, für die keine "Implementierung" existieren könnte ... :-D

Es ist unklar, was Sie unter einer "Programmiersprache" und einer "Implementierung einer Sprache" verstehen. Sie müssen diese beiden genau definieren, um eine Antwort zu erhalten.

$\Sigma^*$$2^{\Sigma^*}$

$M$$M$$0$

Dies ist jedoch nicht die Art von Spezifikationssprache, die Menschen meinen, wenn sie den Ausdruck "Programmiersprache" verwenden. Eine Programmiersprache ist normalerweise eine Sprache, die berechenbare Funktionen (Prozesse, ...) ausdrückt und die Anweisungen an eine Maschine übermittelt. Daher gibt es ein TM, das diese Programme simulieren und ihre Ergebnisse ausgeben kann. In gewissem Sinne ist eine Programmiersprache, die nicht implementiert werden kann, nicht sinnvoll.

(Ich vermute, dass Sie Programmiersprachen wahrscheinlich entweder mit Spezifikationssprachen oder mit formalen Sprachen verwechseln . In jedem Fall können wir Sprachen definieren, die nicht berechenbar sind.)

Es wurden viele Sprachen ohne Implementierung spezifiziert, z. B. sollte Algol 60 eine Sprache zum Schreiben von Algorithmen sein, die nicht implementiert werden sollte. Einige der vielen "nur zum Spaß" -Sprachen wurden lange vor der Implementierung spezifiziert, fällt Intercal ein.