Hinweis: Ich bin bereit, für jede Antwort, die ich interessant finde, ein Kopfgeld zu zahlen.
Ihre Herausforderung besteht darin, einen Turing- Complete - One-Instruction-Set-Computer (OISC) zu entwerfen:
Ein OISC ist eine abstrakte Maschine, die nur einen Befehl verwendet - die Notwendigkeit eines maschinensprachlichen Opcodes entfällt. Mit einer vernünftigen Wahl für den einzelnen Befehl und mit unendlichen Ressourcen ist ein OISC in der Lage, ein universeller Computer zu sein, genauso wie herkömmliche Computer mit mehreren Befehlen.
Hier sind einige Beispiele für einzelne Befehle, die einen Turing-vollständigen OISC ausmachen.
Regeln:
Sie müssen eine Interpretation oder einen Beweis dafür vorlegen
Sie müssen einen Dolmetscher für Ihre Sprache bereitstellen. Dieser Interpreter sollte nur durch den Speicher / die Zeit eingeschränkt werden (z. B. darf er keine vom Benutzer auferlegten Einschränkungen aufweisen). Wenn Sie keinen Dolmetscher für Ihre Sprache zur Verfügung stellen (aus irgendeinem anderen Grund als Faulheit), müssen Sie nachweisen, dass es möglich ist, einen zu schreiben. Ein Dolmetscher muss möglich sein .
Sie müssen seine Turing-Vollständigkeit nachweisen
Sie müssen einen formellen Nachweis beifügen, dass Ihre Sprache Turing-vollständig ist. Eine einfache Möglichkeit, dies zu tun, besteht darin, nachzuweisen, dass es eine andere Sprache von Turing-complete interpretieren kann oder dasselbe Verhalten hat. Die grundlegendste zu interpretierende Sprache wäre Brainf ** k .
Eine normale Sprache mit denselben Befehlen wie Brainf ** k (und denselben vom Benutzer auferlegten Speicherbeschränkungen) ist beispielsweise Turing-complete, da alles, was in Brainf ** k implementiert werden kann, in der Sprache implementiert werden kann .
Hier ist eine Liste von sehr einfach zu implementierenden Turing-vollständigen Sprachen.
Zusätzliche OISC-Anforderungen
Diese OISC sollte nur eine Anweisung enthalten - sie kann nicht mehrere Anweisungen enthalten, von denen eine die Turing-Vervollständigung bewirkt.
Ihr OISC kann eine beliebige Syntax verwenden. Sie sollten in Ihrer Antwort definieren, was Anweisung ist, was Daten sind und was ein No-Op ist (z. B. Leerzeichen). Seien Sie kreativ!
Argumente müssen nicht nur ganze Zahlen sein. Zum Beispiel ist /// ein schönes Beispiel für ein Turing-vollständiges OISC.
Wie und ob Input und Output genommen und gegeben werden, bleibt Ihnen überlassen. Die meisten OISCs implementieren E / A über bestimmte Speicherorte. Möglicherweise gibt es jedoch auch andere Möglichkeiten, und Sie werden aufgefordert, eine zu finden.
Eine gültige Antwort muss einen Beispielcode in Ihrem OISC enthalten, entweder durch Einfügen in den Post oder durch Verknüpfen mit einer einfachen, in der Sprache gelösten Herausforderung.
Wählen
Wähler, bitte denken Sie daran, langweilige Einsendungen nicht zu unterstützen. Beispiele:
- lenguage -Äquivalente
- Eine Implementierung eines bestehenden OISC (Beantworter, bitte erstellen Sie Ihre eigenen!)
- Ein "OISC", in dem das erste Argument einen aufzurufenden Befehl angibt ( Beispiel )
Sie sollten jedoch interessante, kreative Beiträge unterstützen, wie z. B .:
- Ein OISC basierend auf einer mathematischen Gleichung
- Ein Turing-vollständiges ZISC basierend auf einem neuronalen Netzwerk
- Ein OISC, bei dem die Ausgabe-E / A auf andere Weise als an bestimmten Speicherorten erfolgt
Gewinnen
Wie beim Beliebtheitswettbewerb gewinnt die Antwort mit den meisten Stimmen! Viel Glück!
Antworten:
XOISC
Diese OISC basiert auf Fokkers X-Combinator, der wie folgt definiert ist:
Wenn wir die Tatsache anerkennen, dass der SKI-Kalkül Turing vollständig ist, ist der obige Kombinator auch Turing vollständig. Das ist weilX , K und ich in Bezug auf X geschrieben werden können:S K ich X
So funktioniert XOISC
Intern hat XOISC einen (anfangs leeren) Stack, von dem aus die Anweisung, die als Argument verwendet, Folgendes bewirkt:n
Sobald keine weiteren Anweisungen mehr vorhanden sind, überträgt XOISC alle Befehlszeilenargumente (falls vorhanden) an den Stack. Beispiel:
Die endgültige Berechnung lautet .( … ( ( … ( S1 s2) … ) S M) a 1) … ) AN
Da der eine Befehl in XOISC nur ein Argument enthält (Speicheroffset), gibt es keinen Grund, einen Namen für diesen Befehl zu verwenden. Eine gültige Quelldatei besteht also ausschließlich aus Ganzzahlen, die durch Zeilenumbrüche oder Leerzeichen voneinander getrennt sind. Beispiel:
Probieren Sie es online!
Beispiel
Nehmen wir das obige Beispiel (Stapel wächst nach rechts):
Vollständigkeit prüfen
Beweisidee
0
0
2
0
2
Wir haben also ein anderes (aber semantisch äquivalentes) XOISC-Programm:
0 0 2 0 2 0 2
Probieren Sie es online!Wenn wir bei dieser Strategie bleiben, können wir jeden Ausdruck, der aus leicht transformierenX Kombinatoren besteht, in ein XOISC-Programm umwandeln, das nur eine einzige Funktion auf dem Stapel belässt.
Formeller Beweis
Da der SKI-Kalkül vollständig ist, müssen wir zwei Dinge zeigen:
Der erste Teil, in dem die drei Gleichheiten in der Einleitung bewiesen werden, ist sehr langwierig und platzraubend und auch nicht sehr interessant. Anstatt es in diesen Beitrag zu schreiben, finden Sie es hier * .
Der zweite Teil kann durch strukturelle Induktion bewiesen werden , obwohl es einfacher ist, eine etwas stärkere Aussage zu beweisen: Nämlich für jeden von gebildeten AusdruckX Kombinatoren gibt es nämlich ein Programm, das diesen Ausdruck als einen einzelnen Ausdruck auf dem Stapel belässt:
0
Dolmetscher
Eingänge
Da die nicht typisierte Lambda-Rechnung es erfordert, dass wir für alles, was wir wollen, unsere eigenen Datentypen definieren. Dies ist umständlich, da der Dolmetscher die Zahlen der Kirche kennt - das heißt , wenn Sie liefern Eingänge es Nummern automatisch in ihren entsprechenden Kirche Zeichen verwandeln.
Als Beispiel sehen Sie hier ein Programm, das zwei Zahlen multipliziert: Probieren Sie es online aus!
Sie können auch Funktionen als Argumente bereitstellen, indem Sie De Bruijn-Indizes verwenden , z. B. den
S
Kombinator\\\(3 1 (2 1))
(oderλλλ(3 1 (2 1))
). Allerdings erkennt er auch dieS
,K
,I
und natürlichX
combinator.Ausgabe
Standardmäßig prüft der Interpreter, ob die Ausgabe eine Ganzzahl codiert. Wenn dies der Fall ist, wird die entsprechende Zahl (zusätzlich zum Ergebnis) ausgegeben. Für die Bequemlichkeit gibt es die
-b
Flag, mit dem der Interpreter versucht, einen Booleschen Wert zu finden (siehe letztes Beispiel).Assembler
Natürlich benötigt jede Sprache auf niedriger Ebene einen Assembler, der eine Sprache auf hoher Ebene in diese konvertiert. Sie können einfach eine beliebige Eingabe (siehe oben) verwenden und sie mithilfe des
-a
Flags in ein XOISC-Programm übersetzen. Probieren Sie es online aus! *** Falls der Link nicht funktioniert, finden Sie in diesem Beitrag eine Kopie als HTML-Kommentar.
** Dies führt zu einem Programm, das auf Ursprünglichkeit prüft. Probieren Sie es online aus!
quelle
Zeichnen
Draw ist ein OISC, der auf ein 2D-Gitter einwirkt und Quadrate ähnlich wie die Wang B-Maschine markiert. Um die Sprache so einfach und OISC-y wie möglich zu halten, markieren alle Anweisungen (von denen es insgesamt eine gibt) das gerade betretene Quadrat und treten, um anhalten zu können, auf ein markiertes Quadrat Beendet das Programm.
Das Programm besteht aus einer Folge von Zeilen, die einen Zeilenbezeichner (beliebige Zeichenfolge ohne # oder Leerzeichen), zwei Ganzzahlen (
x
undy
) und zwei weitere Zeilenbezeichner (a
und) enthältb
) enthält.Das Programm läuft wie folgt ab:
Beginnend mit der Linie, die als
start
mit dem Zeiger gekennzeichnet ist, der auf Position (0, 0) zeigt, bewegen Sie den Zeiger um den Betrag, der durchx
und angegeben ist,y
und markieren Sie das Quadrat, auf dem sich der Zeiger jetzt befindet (es sei denn, das Quadrat ist bereits markiert). In diesem Fall wird die Ausführung abgebrochen. Springen Sie dann zur Linie,a
wenn mindestens eines der direkt benachbarten Quadrate ebenfalls markiert ist, und zur Linie , wenn dies nicht der Fall istb
.Dolmetscher werden aufgefordert, das Endergebnis des Rasters als eine Art Bild, Leinwand usw. auszugeben.
Turing-Vollständigkeit
Draw ist Turing-complete, da es möglich ist, eine modifizierte Version (Alternate) einer Minsky-Maschine in die Sprache zu kompilieren.
Alternate verhält sich ähnlich wie ein Minsky-Computer mit zwei Zählern, die Befehle unterliegen jedoch einer großen Einschränkung: Die Befehle müssen abwechselnd auf den ersten und den zweiten Zähler abzielen. Um diese Änderung zu umgehen, wurde ein zusätzlicher Befehl hinzugefügt:
nop
. Dieser Befehl ändert den Zielzähler überhaupt nicht, wodurch es möglich ist, aufeinanderfolgende Änderungen an einem Zähler "aufzufüllen", wodurch die oben beschriebene Einschränkung erfüllt wird. Dies bedeutet auch, dass das zu modifizierende Register nicht angegeben werden muss und für einen gegebenen Befehl direkt aus den Befehlen abgeleitet werden kann, aus denen die Ausführung darauf springen kann.Beispiel: Diese Minsky-Maschine
wird zu diesem alternativen Programm:
Diese Einschränkung ist aufgrund der Art und Weise notwendig, in der das eventuelle Draw-Programm Register verarbeitet, dh, es wird überhaupt nicht zwischen diesen unterschieden. Stattdessen kopiert das Zeichenprogramm einfach das Register, das durch den vorhergehenden Befehl nicht geändert wurde, und ändert es entsprechend dem ausgeführten Befehl.
Anschließend wird das Alternativprogramm wie folgt direkt in Draw übersetzt:
Das Programm startet mit diesem Satz.
inc
,dec
Undnop
sind in fast der gleichen Weise wie jede andere übersetzt. In allen Fällen besteht kein Unterschied zwischen dem Ändern des ersten oder des zweiten Registers (wie oben erläutert). Hier ist ein Inkrement, das äquivalent ist zuinc 2
:Ändern Sie die Nummern in den
i1_x
Teilen in den Index der aktuellen Anweisung und in deni2_x
Teilen in den Index der nächsten auszuführenden Anweisung.Die
nop
Anweisung kann folgendermaßen übersetzt werden:Dies ist eine Dekrementierung:
i3_x
verweist auf die Anweisung, die aufgerufen werden soll, wenn der Zähler bereits 1 ist.Halt:
Ändern Sie die Beschriftungen entsprechend und verketten Sie einfach alles. Wenn Sie dies für das Beispiel von oben tun, wird das Draw-Programm im Repository von oben angezeigt.
Dolmetscher
Derzeit gibt es zwei Dolmetscher, die beide in Python geschrieben sind. Sie befinden sich im GitHub-Repository von Draw .
genau den falschen Zweck.Einfachere grafische Ausgabe, wobei die Quelle beim Starten des Skripts über ein Popup- Fenster abgerufen wird . Golly kann mit Python etwas heikel sein, stellen Sie also sicher, dass Sie Python 2 installiert haben (und mischen Sie nicht 32-Bit-Golly mit 64-Bit-Python oder umgekehrt). Die Ausgabe erfolgt über das in Golly integrierte Zellenraster.Das folgende Bild ist ein Beispiel für die Ausgabe des zweiten Interpreters. Wenn Sie das Beispielprogramm im Repository ausführen, erhalten Sie Folgendes (oder Ähnliches):
quelle
-3
Hier ist das Wesentliche.
Erinnerung
Der Speicher ist eine Karte von Bändern, in der die Schlüssel Zeichenfolgen und die Werte Ganzzahlen beliebiger Größe sind.
Zusätzlich gibt es eine Reihe von Bezeichnungen, zu denen das Programm springen kann.
Es gibt einen Stapel, der die Operanden enthält, die Strings sind.
Es gibt einen Test, der steuert, auf welche Bänder im Speicher zugegriffen werden kann.
Die eine Anweisung
-
. Zunächst wird eine ZeichenfolgeLABEL
vom Stapel entfernt. Wenn diesLABEL
nicht als Etikett definiert ist, definiert es das Etikett und löscht die Quelle dieses Etiketts (dh woher es stammt) und die aktuelle Anweisung. Andernfalls führt er die folgende Berechnung, die beiden oberen Werte verwenden,A
undB
:Beachten Sie, dass das Programm einen Fehler ausführt und den Status des Programms anzeigt, wenn es überzählige oder unzureichende Argumente gibt.
Der Offset kann geändert werden, indem auf den Wert von zugegriffen wird
.
.Beispielcode
Dies setzt die Variable
i
auf7
, indem die7
Zeiten erhöht werden .Dies multipliziert sich
i+1
mit der Konstanten2
.Nachweis der Vollständigkeit
Ungeachtet der Int-Größen von C ++ (vorausgesetzt, sie sind unendlich) ist -3 Turing Complete durch Reduktion auf 3-Zellen-Brainfuck . Ich kann diese Größe ignorieren, da auf einem Computer mit unendlichem Speicher, der beliebig große Zellen hat, ein Interpreter für -3 geschrieben werden kann.
Ich glaube auch, dass jedes BCT als -3-Programm geschrieben werden kann.
quelle