Ist es möglich, eine quine in jeder Turing-complete Sprache zu schaffen?

Question

Ich wollte nur wissen, ob es zu 100% möglich ist, wenn meine Sprache Turing-complete, ein Programm darin zu schreiben, den Druck selbst aus (natürlich keine Dateilesefunktion verwendet wird)

Also, wenn die Sprache nur die wirklich notwendigen Dinge, um es Turing vollständig zu machen hat (ich würde das beweisen durch Brainf * ck Code, um es zu übersetzen), wie Ausgang, Variablen, Bedingungen und gotos (Hölle ja, gotos), kann ich ein quine darin versuchen zu schreiben?

Ich frage dies auch, weil ich nicht sicher bin, dass ein quine paßt in direkt Turings Gesetz, dass die Turing-Maschine der Lage jeder Rechenaufgabe ist. Ich möchte nur wissen, so dass ich nicht versuche seit Jahren, ohne zu wissen, dass es unmöglich sein kann.

Answer 1

  

Jede Programmiersprache, die ist   Turing abgeschlossen ist, und welche in der Lage,   Ausgang beliebige Zeichenkette (durch eine berechenbare   Funktion des Strings als Programm -   Dies ist ein technischer Zustand, der ist   in jeder Programmierung zufrieden   Sprache in Existenz) eine quine   Programm (und in der Tat unendlich viele   Quine-Programme und viele ähnliche   Kuriositäten) folgt, wie durch die   Festpunkt-Satz.

hier sehen

Answer 2

Ich lief in dieser Frage ein paar Monaten.

Während ein quine Schreiben beweist nicht unbedingt, dass eine Sprache Complete Turing, ist es eine starke Anregung;) Was Turing Vollständigkeits gehen, wenn man (wie Sie gesagt hat) eine gültige Übersetzung von Sprache in einer anderen zur Verfügung stellen Turing-Complete Sprache, dann Ihre Sprache ist Turing abgeschlossen.

Das wird gesagt, jede Sprache, die Complete Turing dass ausgeben kann sollte ein String Lage sein, eine quine zu erzeugen. Auch aus Wikipedia:

  

A quine ist ein fester Punkt von einer Ausführungsumgebung, wenn die Ausführungsumgebung als eine Funktion betrachtet wird. Quines sind möglich in einem beliebigen Programmiersprache, die die Fähigkeit zur Ausgabe von jedem berechenbaren String, als direkte Folge von Kleenes hat Rekursionssatz . Umso schlimmer, versuchen Programmierer manchmal die kürzest mögliche quine in einem bestimmten Programmiersprache zu entwickeln.

Answer 3

Es ist möglich, eine Programmiersprache zu haben, die nicht alle Symbole in seiner Darstellung drucken. Zum Beispiel kann die I / O in ASCII-Zeichen 7-Bit mit Sprache Keywords in Arabisch begrenzt. Das ist die einzige Ausnahme, die ich mir vorstellen kann.

Answer 4

Nun, technisch gesehen, nicht immer. Nach dem Beweis auf Wikipedia , hat die Programmiersprache eine zulässige Nummerierung sein. Praktisch und vernünftig Turing-complate Programmiersprachen sind alle zulässigen Nummerierungen. Und eine Turing-complate Programmiersprache ist eine zulässige Nummerierung wenn es möglich ist zwischen diesem und anderen zulässigen Nummerierung zu übersetzen.

Ein Beispiel Turing-vollständige Programmiersprache, die nicht eine zulässige Nummerierung ist:

Der Quellcode enthält immer eine oder zwei doublequoted entkommen Saiten. Ist der Eingang leer ist, die erste Ausgabezeichenfolge, wenn es zwei Zeichenfolgen oder Schleife immer wenn es einen gibt. Andernfalls bewertet die letzte Zeichenfolge in Python, den ursprünglichen Eingang als Eingabe verwendet.

Es ist keine zulässige Nummerierung, weil, da ein Python-Programm, haben wir ihr Verhalten wissen, wann die Eingabe leer ist, ist es in dieser Sprache zu übersetzen. Aber wir können nie wissen, ob es eine unendliche Schleife ist, wie wir das Halteproblem nicht lösen können. Wir wissen, dass eine Übersetzung immer existiert, aber.

Es ist unmöglich zu schreiben quines in dieser Sprache.