Bitte beachten Sie: Die Spezifikation für diese Herausforderung ist naturgemäß schwer zu verstehen. Es erfordert wahrscheinlich mindestens einen Anfängerkurs in Berechenbarkeitstheorie oder ein gleichwertiges Hintergrundlesen. Darüber hinaus ist die Herausforderung selbst ziemlich schwer. Um darauf zu antworten, muss ein ganzer Dolmetscher für eine Untergruppe der von Ihnen gewählten Sprache geschrieben werden. Außerdem muss der Dolmetscher die Form eines Quines haben. Wenn Ihre Antwort dies alles nicht tut, ist es fast sicher, dass Sie die Spezifikation nicht erfüllen.
Sie müssen das Halteproblem nicht (auch nur teilweise) lösen, um diese Herausforderung zu lösen. Allerdings Sie mit ziemlicher Sicherheit tun Notwendigkeit , einen Dolmetscher zu schreiben (der Sprache , die Sie verwenden, in derselben Sprache geschrieben interpretiert), obwohl es nicht Funktion komplett zu sein braucht. Das macht dies zu einer interessanten Herausforderung.
Ich habe versprochen, eine Prämie von 500 Punkten für die erste Antwort zu vergeben, die der Spezifikation entspricht, und diese Prämie wird an Jo Kings BF-Antwort vergeben .
Die Herausforderung
Eine grobe, vereinfachte Version von Alan Turings Beweis für die Unlösbarkeit des Halteproblems sieht ungefähr so aus:
Angenommen, ich habe ein Programm geschrieben, F
das das Halteprogramm lösen soll. Dies bedeutet, dass F
der Quellcode eines anderen Programms als Eingabe verwendet wird und zurückgegeben F(G)
werden soll, 1
wenn G
angehalten wird und 0
ansonsten.
Aber wenn ich Ihnen mein Programm gebe, F
dann können Sie ein anderes Programm erstellen H
, das mein Programm H
als Eingabe ausführt. Wenn F(H)
kehrt, 0
dann H
kehrt zurück 0
, aber sonst geht es absichtlich in eine Endlosschleife. Dies führt zu einem Paradoxon, und wir müssen zu dem Schluss kommen, dass F
das Halteproblem schließlich nicht gelöst werden kann.
Ihre Aufgabe ist es, das Programm zu schreiben H
, aber mit einer Wendung: Ich werde Ihnen nicht mein Programm geben. Stattdessen erhält Ihr Programm den Quellcode meines Programms als Eingabe. Das ist:
Ihr Programm erhält mein Programm als Eingabe in Quellcode-Form. (ZB als Datei oder als Kommandozeilen-Eingabe, die Details liegen bei Ihnen.)
Mein Programm wird in der gleichen Sprache wie Ihr Programm geschrieben und auch in Form einer Quellcode-Zeichenfolge eingegeben.
Wenn mein Programm zurückkehrt ,
0
wenn gegeben Ihr Programm als Eingabe Ihres Programm sollte anhalten (und zurück0
) , wenn gegeben mein Programm als Eingabe. (Die genaue Bedeutung von "Returing0
" liegt bei Ihnen.)Wenn mein Programm nicht anhält oder wenn es etwas anderes zurückgibt, als
0
wenn Ihr Programm als Eingabe angegeben wird, sollte Ihr Programm auf unbestimmte Zeit ausgeführt werden.
Die Wendung ist, dass man, um es wirklich sehr viel schwieriger zu machen, die folgenden Regeln befolgen muss:
Sie können keine eingebauten
exec
odereval
typisierten Funktionen verwenden.Sie können keine "Schummelmethoden" verwenden, um an den Quellcode Ihres eigenen Programms zu gelangen. (ZB können Sie nicht sagen "Speichern Sie dies in einer Datei namens" Programm "" und haben dann
open(program)
in Ihrem Programm.)
Dies bedeutet, dass Ihr Programm eine Art verrückte Super-Quine sein muss, die nicht nur ihren eigenen Quellcode in Form eines Strings reproduzieren kann, sondern auch in der Lage ist, die Sprache, in der es geschrieben ist, korrekt zu analysieren und zu interpretieren.
Um es etwas weniger wahnsinnig schwer zu machen, dürfen Sie nur eine (Turing-complete) Teilmenge Ihrer gewählten Sprache verwenden. Wenn Ihr Programm also in Python geschrieben ist und nur funktioniert, wenn mein Programm nur if
s und while
Schleifen sowie grundlegende Zeichenfolgenoperationen enthält , ist das in Ordnung, solange Ihr Programm auch nur diese Dinge verwendet. (Dies bedeutet, dass Sie sich nicht um die Implementierung der gesamten Standardbibliothek Ihrer gewählten Sprache kümmern müssen!) Ihr Programm muss jedoch tatsächlich ausgeführt werden - Sie können nicht einfach Ihre eigene Sprache erstellen.
Dies ist ein Beliebtheitswettbewerb , daher gewinnt die Antwort mit den meisten Stimmen. Wie oben erwähnt, ist es jedoch eine ernsthafte Herausforderung, die Spezifikation überhaupt zu erfüllen. Daher werde ich für die erste Antwort, die dies nach meinem Ermessen tut, eine Prämie von 500 Punkten gewähren.
bitte beachte: es gibt zweifellos viele möglichkeiten, bei dieser herausforderung zu "schummeln", wenn man die genaue formulierung beachtet , die ich verwendet habe. Ich hoffe jedoch sehr auf Antworten, die den Grundgedanken der Frage widerspiegeln. Die beabsichtigte Herausforderung ist sehr schwierig, aber möglich, und ich hoffe wirklich auf echte Lösungen dafür. Ich werde das Kopfgeld nicht für eine Antwort vergeben, die sich meiner Meinung nach betrügerisch anfühlt.
Hinweis: Diese Herausforderung wurde ursprünglich als Beliebtheitswettbewerb veröffentlicht , wurde jedoch 2016 geschlossen, da es kein "objektives Gewinnkriterium" gab, und ich habe sie in Code-Golf geändert, um sie wieder zu eröffnen. Ich habe jedoch festgestellt, dass ab Januar 2018 Beliebtheitswettbewerbe in PPCG nicht mehr verboten sind ( dies ist die jüngste Metadiskussion). Daher verstieß das Schließen in erster Linie gegen die Richtlinien der Website. Ich verstehe , dass popcons in diesen Tagen nicht beliebt sind, aber dies ist eine alte Herausforderung, und seine Natur macht es wirklich nicht geeignet für den Code-GolfPunktesystem. Wenn noch immer jemand der Meinung ist, dass dies nicht erlaubt sein sollte, sollten wir eine Metadiskussion führen, bevor enge Abstimmungen stattfinden. Da es unwahrscheinlich ist, dass jemand im letzten Jahr versucht hat, seine Lösung zu entwickeln, können Sie sicher sein, dass sie bei dieser Herausforderung genauso wettbewerbsfähig und die Prämie genauso wert ist, wie dies beim Code-Golf der Fall gewesen wäre Ausführung.
quelle
F
in eine Datei zu exportieren und zuimport
bearbeiten? ; 3Antworten:
Brainfuck ,
601348774376 BytesEdit: -1136 Bytes. Es wurde auf eine bessere Methode zum Generieren der Daten für die Quine umgestellt
Edit2: -501 Bytes. Ich habe meinen Selbstinterpretierer erneut besucht und ein paar Hundert Bytes reduziert
Probieren Sie es online! Die Eingabe hier ist ein einfaches cat-Programm (
,[.,]
), das das Programm selbst ausgibt."Return 0" wird definiert, indem das Programm in einer Zelle mit dem Wert 0 beendet wird.
Eine unheilige Kombination aus zwei Programmen, die ich in der Vergangenheit geschrieben habe, einem Quine und einem Selbstinterpretierer. Der erste Abschnitt ist der Quine-Teil, der die Daten aufnimmt und das Band mit der Datengenerierung und anschließendem Quellcode auffüllt. Als nächstes kommt der Selbstinterpreter, der Ihr Programm übernimmt und ausführt. Dies ist so ziemlich eine unveränderte Kopie eines normalen Selbstinterpreters, mit der Ausnahme, dass die Eingabe nicht direkt erfolgt, sondern am Anfang des Datenabschnitts erfolgt und die Zelle auf 0 gesetzt wird, wenn keine weitere Eingabe erfolgt. Beenden Sie schließlich die aktuelle Zelle Ihres Programms und führen Sie es aus
[]
. Wenn der zurückgegebene Wert 0 war, endet mein Programm bei Null. Wenn es sich um etwas anderes handelt, wird eine Endlosschleife ausgeführt. Wenn Ihr Programm für immer läuft,Mein Programm wird für immer laufen.Wie es funktioniert:
Teil 1: Datengenerierung
Dieser Teil bildet den Datenabschnitt des Quines und ist mit 3270 Bytes bei weitem der größte Teil des Codes. Der Anfang
-
ist eine Markierung für den Beginn der Daten. Jedes steht>+++
für ein Zeichen des Codes nach diesem Abschnitt.Teil 2: Generieren Sie den Datenabschnitt mit den Daten
Hierbei werden die Daten aus Teil 1 verwendet, um die Zeichen, die zum Generieren der Daten verwendet werden, zum Codeabschnitt hinzuzufügen. Es fügt
>
dem Ende des Codeabschnitts ein und dem Wert dieser Zelle viele Pluszeichen hinzu.Teil 3: Generieren Sie den Rest des Codes mit den Daten
Zerstört den Datenabschnitt und fügt den Rest des Quellcodes zum Codeabschnitt hinzu
Teil 4: Eingegebenes Programm holen
Ruft das eingegebene Programm ab. Entfernt Nicht-Brainfuck-Zeichen und stellt jedes Zeichen mit einer Nummer dar:
Stellt das Programmende mit dar
255
.Teil 5: Interpretation der Eingabe
Interpretiert das Programm. Der einzige Unterschied zu einem normalen ist, dass die Eingabe am Anfang des Codeabschnitts statt der Eingabe erfolgt.
Teil 6: Halt, wenn return nicht 0 ist
Navigieren Sie zur Endzelle Ihres Programms und führen Sie eine Endlosschleife aus, wenn die Rückgabe nicht 0 ist. Wenn sie 0 ist, beenden Sie die Schleife und beenden Sie sie bei derselben 0.
Testeingänge:
Gibt immer 0 zurück (hält an und gibt 0 zurück)
Gibt immer 1 zurück (läuft für immer)
Gibt alle Eingaben zusammen, Mod 256, zurück (gibt 211 zurück, läuft also für immer)
Gibt 0 zurück, wenn die letzten beiden Zeichen eines Codes eine Endlosschleife sind (
[]
) ( Ihr Programm gibt 0 zurück, wenn es mein Programm gibt , daher stoppt mein Programm )Fun Fact für diejenigen, die noch lesen
Wenn es sich bei der Eingabe für dieses Programm um den Quellcode dieses Programms handelt, wird es rekursiv und erstellt wiederholt Selbstinterpreter, die dieses Programm ausführen, und gibt ihm dann dasselbe Programm erneut. Dies gibt mir einige interessante Ideen zum Erstellen von rekursiven Programmen in Brainfuck. Anstatt den Rückgabewert zu überprüfen und eine Endlosschleife wie in dieser Frage zu starten, kann der Rückgabewert gespeichert und bearbeitet werden. Ein einfaches Beispiel wäre ein Fakultätsprogramm
Dies ist natürlich eine völlig verrückte Art, Brainfuck zu codieren, da das Ausführen von rekursiven Selbstinterpretern die Laufzeit exponentiell erhöht.
quelle
.
. Obwohl dies keine Code-Golf-Frage mehr ist, ist die Unterstützung der gesamten Sprache möglicherweise eindrucksvoller.