Eine Herausforderung, die ich für sehr cool hielt, ist es, einen Dolmetscher für eine Turing-vollständige Sprache Ihrer Wahl zu erstellen .
Die Regeln sind einfach:
- Sie können eine beliebige Sprache verwenden, um diesen Interpreter zu erstellen, auch wenn er neuer als diese Herausforderung ist.
- Sie können eine beliebige Turing-complete-Sprache verwenden, sofern diese nicht mit derjenigen identisch ist, mit der Sie sie schreiben.
- Sie können Code nicht einfach auswerten, sondern beispielsweise Auswertungsfunktionen verwenden.
- Eine Erklärung, wie Sie sich dem näherten, ist nett, aber nicht erforderlich.
- Dies wird in Bytes bewertet.
- Jede Einreichung muss vollständig funktionieren, dh, jede Funktion, die Ihre gewählte Sprache hat, muss vorhanden sein.
Einfach ausgedrückt:
Ihre Aufgabe ist es, einen Arbeitsdolmetscher für jede Turing-vollständige Sprache mit einer beliebigen Sprache Ihrer Wahl zu erstellen.
Viel Glück!
code-golf
interpreter
Arodebaugh
quelle
quelle
eval
Lösungen zu vermeiden .eval
Befehle / Funktionen sperren, da in einigen Sprachen Code in einer anderen Sprache ausgewertet werden kann.Antworten:
Brachylog (2) → Korrespondenzproblem melden , 9 Bytes
Probieren Sie es online!
Die Eingabe ist eine Liste von Listen mit Zeichenfolgen. (Im Post-Korrespondenz-Problem, wie es in Wikipedia definiert ist, haben die inneren Listen jeweils zwei Elemente, obwohl dieses Programm tatsächlich eine Verallgemeinerung auf eine beliebige Anzahl von Elementen durchführen kann.) Dieses Programm erzwingt Lösungen für das Problem in der Reihenfolge der Länge bis es wird eine lösung gefunden. Es ist bekannt, dass das Post-Korrespondenz-Problem in der Lage ist, eine Turing-Maschine zu simulieren, und daher ist die Lösung, die sie zwingt, Turing vollständig. Wenn es als Funktion und nicht als Programm ausgeführt wird, wird auch eine aussagekräftige Ausgabe erstellt.
Das Programm im obigen TIO-Link ist
[["a","baa"],["ab","aa"],["bba","bb"]]
, das ich aus Wikipedia kopiert habe. Die Lösung (die das Programm ziemlich schnell findet) ist["bbaabbbaa","bbaabbbaa"]
.Erläuterung
Dies ist so ziemlich nur eine direkte Übersetzung des Post-Korrespondenz-Problems nach Brachylog.
Grundsätzlich erstellen wir eine Liste, in der Kopien der Eingaben wiederholt werden (so wenig wie möglich, sodass beim Brute-Forcing keine Möglichkeiten ausbleiben). Nehmen Sie ein Element aus jeder Kopie und verknüpfen Sie die entsprechenden Elemente (wie in der Post-Korrespondenz) Problem).
quelle
~dp
(was nicht ganz dasselbe bedeutet, aber nah genug ist, um es noch zu sein) Turing-complete), außer dass der Brachylog-Interpreter noch nicht weiß, wie er umkehren solld
.Jelly → "Add Minimum zu transponieren",
54 BytesProbieren Sie es online! (führt nur eine Iteration aus, um Zeitüberschreitungen zu vermeiden)
Eine sehr einfache Turing-vollständige Konstruktion: Wir nehmen eine quadratische Matrix als Programm und schleifen für immer, identifizieren die lexikographisch kleinste Zeile und erhöhen dann jedes Element der ersten Zeile um das erste Element der lexikographisch kleinsten, jedes Element der zweiten Zeile durch das zweite Element des lexikographisch kleinsten und so weiter. (Das Jelly - Programm ist "
+"
füge entsprechende Elemente {der Eingabe und}Ṃ
das Minimum {der Originalschleife} hinzuẞ
"; dies ist ein Byte kürzer als mein vorheriges ProgrammZ+ṂZß
, das genau das Gleiche tat. Ich hätte mich eindeutig auf das Golfen konzentrieren sollen Jelly, nicht nur Golfspielen mit der implementierten Sprache.)Die resultierende Sprache ist Turing-complete aus dem gleichen Grund wie Kangaroo. Das erste Element jeder Zeile verhält sich wie eine Sprunganzahl (obwohl statt der Sprunganzahl jedes Befehls, die sich verringert, wenn er übersprungen wird, die Sprunganzahl jedes Befehls erhöht wird, wenn er ausgeführt wird, und stattdessen nach dem Befehl mit der niedrigsten Sprunganzahl gesucht wird) als befehle mit null überspringen zählt, das kommt auf die gleiche sache). Wir stellen sicher, dass dieses erste Element höher ist als die anderen Elemente (die angeben, wie oft jeder Befehl im Multiset jedes Befehls vorkommt), um sicherzustellen, dass die erste Zeile niemals das Minimum darstellt. Der Rest der ersten Reihe kann Müll sein. Die einzige verbleibende Schwierigkeit besteht darin, die Art und Weise zu modellieren, in der Befehle mit gleicher Sprungzahl zyklisch nacheinander ausgeführt werden. Dies können wir jedoch erreichen, indem wir alle Sprungzahlen mit einer großen Konstanten multiplizieren und dann eine kleine "Initiale" hinzufügen. Überspringen zählt zur ersten Spalte, die als Tiebreak dient. Dies gibt uns einen Tiebreak von "ersten nicht übersprungenen Befehlsausführungen", nicht "nicht übersprungenen Befehlen, die zyklisch nacheinander ausgeführt werden", aber die Turing-Vollständigkeitskonstruktion für Kangaroo kümmert sich nicht um diesen Unterschied.
quelle
Mathematica interpretiert Conways Spiel des Lebens, 64 Bytes
Conways Spiel des Lebens ist bekanntermaßen vollständig. und zellulare Automaten sind Stephen Wolframs wahrste Besessenheit.
CellularAutomaton@{224,{2,{t={2,2,2},{2,1,2},t}},{1,1}}
ist eine Regel, die eine zweidimensionale Anordnung von Nullen und Einsen gemäß einem Schritt von Conways Spiel des Lebens transformiert. (Ich denke, das Standardverhalten ist, dass sich dieses Array um seine Kanten schlängelt, also wirklich ein diskreter Torus.)~Nest~##&
Diese Regel wird in eine Funktion umgewandelt, die bei einem anfänglichen Board-Status (beliebiger Dimensionen) und einer Ganzzahln
als Argumente das ausgibt Ergebnis vonn
Iterationen der Game of Life-Regel.Für Ihren eigenen Genuss können Sie die verpackte Version verwenden
und scrollen Sie sich auf einem 50x50-Board durch 100 Generationen.
quelle
Turtlèd interpretiert CT , 49 Bytes
Ich könnte das Golf spielen können
Auch dies gibt nichts Nützliches aus. es stoppt genau dann, wenn das angegebene CT-Programm stoppt.
Dies ist eine, die ich vor einiger Zeit gemacht habe (dann habe ich jetzt Golf gespielt)
Wie es funktioniert:
Turtlèd benutzt Gitterzellen. Wenn ich "etwas in das Raster schreiben" sage, bedeutet dies, dass eine zusammenhängende Gruppe von Zeichen in das Raster eingefügt wird. Beispiel
auf das Programm
Daten werden zuerst eingegeben:
Dies ist im Wesentlichen ein Katzenprogramm. Es schreibt die Eingabe in das Raster.
dann werden die Befehle eingegeben:
was es mit diesen Befehlen macht:
Diese Befehle sind "Produktionen". Wenn das Datenbit ganz links eine 1 ist, wird die Produktion auf das Ende des Datenstrings kopiert. sonst passiert nichts. Dann wird das Datenbit ganz links entfernt und die nächste Produktion mit dem Datenbit ganz links verwendet. Das Programm wird angehalten, wenn die Datenzeichenfolge keine Bits enthält. Eine Möglichkeit, diese Produktionen zu erstellen, besteht darin, die Teile und das Ende der Produktionen separat zu behandeln. Das ist, was unser Programm macht. Es kopiert die Bits von der Befehlszeichenfolge separat an das Ende der Datenzeichenfolge und löscht die Bits separat aus dem Datenring
auf, wie dieses Programm es tut. Nach der Eingabe der Befehle springt der Turtle / Grid-Zeiger zum linken Bit des Datenrings zurück. es geht dann in eine Schleife
In dieser Schleife springt es vom linken Datenring nach oben und schreibt das aktuelle Befehlszeichen (u.) auf. Wenn es sich um das Ende einer Produktion handelt, wird es nach unten verschoben und das ganz linke Datenbit darunter wird gelöscht und es wird wieder nach oben verschoben (
(;d' u)
). dann bewegt es sich so oder so um eins nach unten (d
). Wenn das Bit dort nicht gelöscht wurde, bedeutet dies, dass geprüft werden muss, ob am Ende ein Bit aus den Befehlen kopiert werden soll. Wenn dieses Zeichen, das das am weitesten links stehende Datenbit ist oder war, eine 1 ist, wird es an das Ende des rechten Endes der Datenzeichenfolge verschoben, das Bit aus der Befehlszeichenfolge kopiert und an den linken Bereich der am weitesten links liegenden Daten zurück verschoben bit ((1[ r].[ l])
). Jetzt befindet es sich entweder auf dem ganz linken Datenbit, das eine Null war, oder links vom ganz linken Datenbit. wir bewegen uns also nach rechts, wenn wir uns auf einem Leerzeichen befinden (( r)
). Dann wird der Befehlszeiger inkrementiert, sodass wir den nächsten Befehl in der nächsten Iteration der Schleife aufschreiben. Wenn keine Daten mehr übertragen werden, bedeutet dies, dass wir uns in einem Leerzeichen befinden und die Schleife endet. Andernfalls führen wir die Schleife erneut aus.quelle
Perl → Three Star Programmer- Variante, 26 + 1 = 27 Byte
Probieren Sie es online! (Dieser Link enthält einen Header, der das Programm nach einer festgelegten Anzahl von Iterationen beendet (damit TIO keine Zeitüberschreitung erfährt) und den internen Status bei jeder Iteration ausgibt (damit etwas Beobachtbares geschieht).)
Laufen Sie mit
-a
(1 Byte Strafe, wie Sie es vor dem-M5.010
Produzieren einpassen können-aM5.010
).Dies implementiert speziell Three Star Programmer, bei dem Befehle durch Leerzeichen getrennt sind und in der Datei keine Kommentare ohne E / A-Erweiterungen zulässig sind. (Diese Änderungen haben offensichtlich keinen Einfluss auf die Turing-Vollständigkeit der Sprache.) Es gibt keinen Beweis für die Turing-Vollständigkeit für Three Star Programmer online, aber es ist Turing-vollständig - Vollständigkeit mit anderen Esoprogrammen, aber ich habe aufgehört, an der Sprache zu arbeiten, als ich herausgefunden habe, dass es eigentlich ziemlich einfach ist, sie zu programmieren, wenn man den ursprünglichen Schock überwunden hat.
Das Programm braucht nicht wirklich viel Erklärung; Drei-Sterne-Programmierer hat eine sehr einfache Spezifikation, und dies ist eine direkte Übersetzung davon. Die einzigen subtilen Punkte:
@F
ist die Eingabe in das Programm in Array-Form (dies ist eine Folge von-a
); undredo
wiederholt das gesamte Programm, da es sich in einer impliziten Schleife befindet (auch eine Folge von-a
).quelle
x86-Assembly (Intel-Syntax / MASM) -Brainfuck 2127 Bytes.
Immer noch golffähig
quelle
Pip- Interpretation von zyklischen Tag-Systemen , 16 Byte
Übernimmt die Produktionen des Tag-Systems als Befehlszeilenargumente und die anfängliche Datenzeichenfolge von stdin.
Der obige Code ist schwer zu überprüfen, da er keine Ausgabe erzeugt (das einzige beobachtbare Verhalten ist "terminiert" vs. "terminiert nicht"). Daher gibt es hier eine ungolfed-Version, die den Datenstring nach jedem Schritt ausgibt und auch nach 20 Schritten endet, sodass TIO nicht mit Tonnen von Ausgaben aus Endlosschleifen umgehen muss: Probieren Sie es online aus!
Zyklische Tag-Systeme
Zyklische Tag-Systeme sind ein äußerst einfaches und dennoch Turing-vollständiges Rechenmodell. Sie bestehen aus einer Liste von Produktionen , die Operationen für eine Datenzeichenfolge definieren . Die Produktionen und der Datenstring bestehen aus Einsen und Nullen.
Bei jedem Schritt wird das Zeichen ganz links in der Datenzeichenfolge entfernt.
In beiden Fällen wechselt die aktuelle Produktion zyklisch zur nächsten Produktion in der Liste: Wenn wir bei der letzten Produktion waren, wechseln wir zur ersten. Die Ausführung wird fortgesetzt, bis der Datenstring leer ist.
Erläuterung
quelle
1
Quelle sein: esolangs Links zu dieser arxiv.org/abs/1312.6700 . Ich werde meine Antwort bald bearbeiten, und wenn dies Ihrer Antwort hilft, sollten Sie (obwohl Ihre Eingabe tatsächlich golfen genug scheint)Iterierte verallgemeinerte Collatz-Funktionen -> Python 2, 46 Bytes
Rufen Sie diese Funktion mit einer Liste von m-1 a und b, dem Startwert x und dem Divisor m auf, die zusammen ein "Programm" für IGCF bilden. Anstatt ein drittes Array zu nehmen, um anzuzeigen, auf welchen Modulen anzuhalten ist, stoppt dies einfach, wann immer der Modul m-1 ist. Diese Vereinfachung bedeutet, dass die Konvertierung eines bestimmten Fractran-Programms in diese Variante einige zusätzliche Mühe erfordert, jedoch einige Bytes im Interpreter einspart.
Probieren Sie es online! Diese TIO zeigt, wie Sie mit dieser Sprache 5 + 5 hinzufügen. Das Programm a = [3], b = [0], m = 2 addiert, und beginnend mit 7776 = 2 ^ 5 * 3 ^ 5 ergibt sich schließlich 59049 = 3 ^ 10.
quelle
ResPlicate- Variante -> Python 2, 47 Bytes
Diese Funktion interpretiert eine Variante von ResPlicate
Die letzte Änderung hat zur Folge, dass einige ResPlicate-Programme (die die erste Bedingung erfüllen) in dieser Variante nicht dasselbe Verhalten aufweisen. Glücklicherweise benötigen die BCT-Interpreter die entfernte Funktionalität nicht und die Sprache bleibt daher TC.
Probieren Sie es online! In diesem TIO ist ein Ausdruck eingeklemmt, der anzeigt, dass es funktioniert, und ein Header, der das Programm nach 1 Sekunde beendet, und ein Beispiel, das mehr Ausgabe generiert, als TIO in dieser Sekunde verarbeiten kann.
quelle
l=input()
? Wäre ein Byte kürzer.Perl
-a
→ E / A-Maschine , 24 BytesProbieren Sie es online! (Enthält einen Header, der den internen Status ausgibt und nach 10 Iterationen angehalten wird, sodass das Verhalten beobachtet werden kann.)
Über die Sprache
Ich habe in den letzten Tagen an der I / D-Maschine gearbeitet , eine meiner neuesten Ideen für sehr einfache Programmiersprachen. Dies funktioniert folgendermaßen: Der Datenspeicher besteht aus einem unbegrenzten RAM, anfangs aus Nullen. Jedes Element kann eine unbegrenzte Ganzzahl speichern (obwohl in der Praxis die meisten I / D-Maschinenprogramme nur kleine Ganzzahlen speichern und die unbegrenzten Ganzzahlen nur zum Adressieren von Zellen mit großen Adressen verwenden). Es gibt auch einen Datenzeiger, der auf eine Zelle zeigt (dh die Adresse als Zelle enthält); es ist anfangs auch null.
Es gibt nur zwei Befehle:
I
: Inkrementieren Sie die Zelle, auf die der Datenzeiger zeigt. (Der Datenzeiger selbst bleibt unverändert.)D
: Verweise auf den Datenzeiger, dh lese den Wert der Zelle, auf die der Datenzeiger zeigt. Speichern Sie dann den Ergebniswert, den Sie zurückgelesen haben, in den Datenzeiger.Die Ausführung führt das Programm einfach für immer wiederholt in einer Schleife aus.
Es ist ziemlich überraschend, dass eine so einfache Sprache Turing-vollständig ist, also habe ich daran gearbeitet, das zu beweisen. Hier ist der Beweis . Es ist ziemlich ähnlich (aber einfacher als) der Beweis für Three Star Programmer, eine sehr ähnliche Sprache (und tatsächlich verwendet diese Einreichung dieselbe grundlegende OISC- "Shell" um das Programm, die sich nur in der tatsächlich implementierten Anweisung unterscheidet).
Über das Programm
Verwendungszweck
Die Eingabe sollte als Standardeingabe erfolgen und ist ein I / D-Maschinenprogramm ohne Kommentare und unter Verwendung der RLE / OISC-Syntax. (Die E / A-Maschine verfügt über zwei unterschiedliche, äquivalente Syntaxen, aus Gründen der Benutzerfreundlichkeit unterstützt dieses Programm jedoch nur eine.) In dieser Syntax ist ein Programm eine Folge von Zahlen in Dezimalform, die die Länge der
I
Befehlsfolgen zwischenD
Befehlen darstellt. (Sie können zwei oder mehr aufeinanderfolgendeD
Befehle angeben, indem Sie einen "Durchlauf von 0I
Befehlen" dazwischen platzieren. Die Syntax ist also völlig allgemein.)Erläuterung
Wie aus dem Programm hervorgeht, werden die Befehle
I
und nichtD
einzeln implementiert . Tatsächlich ist es ein (sehr geringfügig) optimierender Interpreter (nur weil es kürzer ist, so zu schreiben). Der Schlüssel ist zu sehen, dass ein Durchlauf von n Inkrementbefehlen das Ziel des Datenzeigers n- mal inkrementiert , dh n dazu hinzufügt ; Auf diese Weise kann auch eine Ausführung von 0-Inkrement-Befehlen implementiert werden, da das Hinzufügen von 0 zum Speicher keine Auswirkung hat. Die Operation, die wir tatsächlich implementieren, besteht also darin, zwischen der Implementierung eines Run-of-I
s und eines zu wechselnD
. Oder mit anderen Worten: "addiere nLesen Sie dann den Wert, auf den der Datenzeiger zeigt, und speichern Sie ihn im Datenzeiger. "Das ist eindeutig ausführlicher als erforderlich zu sein, und wir können dies weiter vereinfachen, um " n zu dem Wert hinzuzufügen, auf den der Datenzeiger zeigt, und diesen Wert dann sowohl im Ziel des Datenzeigers als auch im Datenzeiger selbst zu speichern".Das macht den Kern unseres Programms aus. Wir verwenden ein Array
$a
zum Speichern des RAM und$p
als Datenzeiger (Indizieren in das Array):Praktischerweise interpretiert Perl nicht initialisierte Array-Elemente als 0, wenn sie wie Zahlen behandelt werden, sodass das Array für uns träge mit Nullen initialisiert wird, ohne dass hierfür expliziter Code benötigt wird. (Ein mögliches Problem ist die numerische Genauigkeit bei großen Zahlen. Dies kann jedoch nur passieren, wenn die Menge des verwendeten Arrays den Adressraum des Computers überschreitet (Perl-Ganzzahlen sind groß genug, um Zeiger aufzunehmen). Dies kann nicht passieren auf einer idealisierten Maschine.)
Schließlich müssen wir dieses Programm nur noch in ein paar Schleifen einteilen. Die
for@F
Schleife durchläuft zusammen mit der-a
Befehlszeilenoption die Felder der Standardeingabe (die Standarddefinition von "Feld" wird hier in Leerzeichen aufgeteilt). Dieredo
Schleife platziert das gesamte Programm in einer impliziten Schleife (mit Ausnahme des Lesens der Standardeingabe), wodurch das Programm entsprechend der Semantik der E / A-Maschine wiederholt in einer Schleife ausgeführt wird.quelle
-a
. codegolf.meta.stackexchange.com/a/14339/9365Gelee → 2-Tag-System , 8 Bytes
Probieren Sie es online!
Ich habe eine Prämie, die praktische Sprachen bevorzugt, aber ich dachte, ich könnte genauso gut versuchen, die ursprüngliche Aufgabe zu gewinnen, während ich dabei war (da ich meine eigene Prämie nicht genau gewinnen kann).
Implementiert eine Variante von Tag-Systemen ohne Halt-Status, da dies für die Vollständigkeit von Turing nicht erforderlich ist. Die Zustände werden fortlaufend von 1 nummeriert, und die Anfangszeichenfolge steht vor dem Programm.
Zum Beispiel gibt Wikipedia ein Beispiel für ein Tag - System {
a
,b
,c
}, {a
→bc
,b
→a
,c
→aaa
} mit Anfangsketteaaa
; In diesem Eingabeformat, das ist[1,1,1]
,[[2,3],[1],[1,1,1]]
. (Tag-Systeme haben keine feste Syntax, und dies scheint eine vernünftige Methode zu sein.)Der TIO-Link verfügt über einen Zusatz
Ṅ
("Write Internal State und Newline To Stdout"), um anzuzeigen, dass das Programm tatsächlich funktioniert.Erläuterung
quelle
BF / P "implementiert in einer Turingmaschine, 842 Bytes
Übergangstabelle (aufgrund der Länge verknüpft)
Übergangstabelle, weniger Golf Version
Turing Machine Simulator, den ich benutzt habe
Dies wird sicherlich keine Preise für Länge gewinnen, aber es ist etwas, was ich schon immer machen wollte, da BF einer Turing-Maschine so ähnlich ist. Jede Zelle speichert einen Wert von
0x0
-0xF
. Die Breite ist jedoch so groß, dass die Turing Machine-Website nicht zum Absturz Ihres Browsers führen kann. Die,
und.
Funktionen (Input und Output) sind nicht definiert, es ist also eher ein P "als ein echtes BF.Fügen Sie dazu die Übergangstabelle in den Turing Machine-Simulator ein, setzen Sie die Eingabe auf einen BF-Code und drücken Sie Ausführen.
Das Band des TM speichert sowohl den BF-Code als auch die BF-Daten mit einem einzelnen Leerzeichen in der Mitte. Er verfolgt seine Position im Code, indem er das aktuell ausgeführte Zeichen (
[
->(
usw.) und seine Position in den Daten mit einem^
vor der Zelle ändert. Sobald es ein Befehlszeichen liest, bewegt es sich, bis es das Einfügemarke trifft, verschiebt eine Zelle nach rechts und führt die entsprechende Funktion aus. Dann kehrt es zurück und sucht nach einem der "geänderten" Befehlszeichen im BF-Code und fährt mit dem nächsten fort, wobei der gesamte Vorgang wiederholt wird. Sobald es keinen Code mehr gibt, wird es angehalten.Der beste Weg, um zu verstehen, wie es funktioniert, besteht darin, die ungolfed-Version auszuführen, sie in den Step-Modus zu versetzen und zu beobachten, welche Zeilen zu welchen anderen führen und was die einzelnen Status / Zeilenblöcke tun.
Die Golf- und die Ungolf-Version sind in ihrer Funktionsweise genau gleich, die Ungolf-Version hat jedoch menschlichere Namen und ist in Abschnitte unterteilt.
quelle
C Implementierung der (2,3) Turing-Maschine ,
236205 Bytes (4631 weniger, wenn Sie sich nicht für umständliche Eingaben interessieren)Dank Appleshell für -11 Bytes, VisualMelon für -12 Bytes und Johan du Toit für -7 Bytes.
CeilingCat hat eine Version erstellt, die nur 144 Bytes verwendet, siehe hier .
(Ich habe hier ein paar Zeilenumbrüche eingefügt, damit Sie nicht scrollen müssen, aber normalerweise werden die meisten davon gelöscht.)
Probieren Sie es online!
Verwendung: Geben Sie eine Zeichenfolge mit bis zu 256 Einsen, Nullen und Zweien ein, um das Band zu initialisieren. Alle nicht initialisierten Werte sind Null. (Andere Werte als 0, 1 und 2 können undefiniertes Verhalten verursachen.) Das Programm durchläuft 256 Schritte. Die Anzahl der Schritte, über die iteriert wird, kann durch Ändern des Codes erhöht werden, dies erfordert jedoch offensichtlich mehr Zeichen.
Es ist ein ziemlich langer Einstieg, aber dies ist das erste Mal, dass ich einen solchen mache, und ich habe keine spezielle Golfsprache verwendet. Ich hatte viel Spaß, auch wenn es länger als ich erwartet hatte.
Viele der Bytes stammen aus dem Umgang mit Ein- und Ausgängen, und ich habe ganze 42 Bytes verloren, indem ich dafür gesorgt habe, dass sie 0, 1 und 2 anstelle von NUL, SOH, STX akzeptieren. (Um dies zu ändern, löschen Sie
k;
von vorne undfor(;k<256&&d[k];)d[k++]-=48;
von der zweiten Zeile.)Die Übergangstabelle, insbesondere die Zeile
*p=-t*t+(2-s)*t+1+s;
(die die Werte auf dem Band festlegt), könnte wahrscheinlich auch stärker komprimiert werden.quelle
k,j;c s,d[256];
(int
Ist in C impliziert, dann können Sie auchi
zur globalen Deklaration wechseln , um weitere 3 Byte zu sparen.)k++
und Entfernen der noch{}
ein paar Bytes speichert:for(;k<256&d[k];)d[k++]-=-48;
Daj
nur ein Zeitnehmer (Wert nie benutzt) ist , können Sie es ersetzen (undi
) mitk
nach rückwärts gezählt werden: Sie weiß ,k==256
nach der ersten Schleife, so auf Null in den zweiten Countdownfor(;k>0;)
, was gehtk==-1
, damit die letzte Schleife werden kannfor(;++k<256;)
. (Haftungsausschluss: Ich spiele normalerweise GolfC#
, aber dies schien zu kompilieren).k<256&&d[k]
,&
weild[k]
bei ausgewertet wurdek==256
. Dak
nicht mehr garantiert wurde, dass es256
nach dieser Schleife ist, musste ich sie anschließend zurücksetzen, um 256 Schritte zu garantieren. (Wenn Sie (also VisualMelon) andere Vorschläge haben, sollten wir sie wahrscheinlich in den Chat stellen, damit wir nicht zu viele Kommentare bekommen.)Röda implementiert Fractran ,
114112106 Bytes1 Byte gespart dank @fergusq durch Umstellen der Parameter
Probieren Sie es online!
Rufen Sie die Funktion wie folgt:
f reference_to_input program
. Die Ausgabe wird am Speicherort von gespeichertinput
.quelle
e[1]
ist überflüssig. Sie können auch durch Änderung Parameter , um ein Byte speichern:f&n,a
.f&n,a
Trick, und ich wollte gerade das Semikolon entfernen, als Sie kommentierten :)Clojure,
8281 bytes (Turingmaschine)Update: hat ein Leerzeichen von entfernt
t{} s
.Implementiert die Turing-Maschine als Schleife und gibt das Band zurück, wenn der Haltezustand erreicht ist. In Zustandsübergangsregeln wird dies durch Weglassen des Übergangszustands angezeigt. Dies stellt
N
sich einnil
und der folgende Vorgang wird abgebrochen ,if-let
da der entsprechende Zustandsübergang nicht in der Eingabe-Hash-Map gefunden wird%
. Tatsächlich ist jeder Wert für diesen Status ausreichend, z. B.:abort
0 oder -1.Ungolfed mit einem 3-Zustands-2-Symbol-Busy-Biber aus Wikipedia .
Probieren Sie es online aus .
Auf einem einzelnen Kern von 6700K läuft der beschäftigte Biber mit 2 Symbolen und 5 Zuständen (47,1 Millionen Schritte) in etwa 29 Sekunden oder 1,6 Millionen Schritten / Sekunde.
quelle
M → Tipp , 4 Bytes
Probieren Sie es online!
Der TIO-Link fügt eine Fußzeile hinzu, um die Funktion mit dem auf der Esolang-Seite gezeigten Beispiel-Tip-Programm aufzurufen (Ms "automatischer Wrapper" zum Aufrufen von Funktionen, als ob sie Programme wären, die keine rationalen oder Festkommazahlen oder zumindest I-Ports verarbeiten könnten) Ich habe nicht herausgefunden, wie ich es erklären soll, also muss ich die Funktion von Hand in ein vollständiges Programm umwandeln, um es ausführen zu können.)
Dies gibt tatsächlich eine nützliche Debug-Ausgabe aus. Das Programm kann nicht in 3 Bytes in M geschrieben werden, da ein Programm, das aus genau drei Dyaden besteht, einen Sonderfall im Parser auslöst. Daher musste ich einen zusätzlichen Befehl hinzufügen, um den Sonderfall zu vermeiden. Wenn Sie es
Ṅ
erstellen (mit Zeilenumbruch drucken), hat es zumindest einen nützlichen Zweck.ı
Implementiert keine E / A (außer halt / no-halt). I / O ist eine Erweiterung von Tip (nicht Teil der Sprache selbst) und wird für die Vollständigkeit von Turing nicht benötigt.
Erklärung / Hintergrund
[1,2,3]
[1,2,3,1,2,3,1,2,3,…]
ḅ
Also habe ich zurückgeschaut und ein bisschen überarbeitet. Gibt es Operationen, die wir anstelle der Polynomauswertung verwenden könnten? Idealerweise kommutativ, damit wir uns keine Gedanken über die Reihenfolge der Argumente machen müssen? Bald darauf wurde mir klar, dass Collatz-Funktionen komplexer sind, als sie sein müssen.
Und natürlich anders als Basis - Konvertierung (
ḅ
), Multiplikation (×
) kommutativ ist, und so spielt es keine Rolle , was die Argumente der Reihenfolge platziert in. Also alles müssen wir schreiben wird×ị
, und dann das Programm in eine unendliche Rekursion setzen mitß
, und wir haben eine Turing-vollständige Sprache. Richtig?¹×ịß
¹
¹
Ṅ
ist eine gute Wahl, da es nützliche Debug-Ausgaben erzeugt.Sind drei Bytes möglich? Es sei denn, ich vermisse etwas, nicht mit dieser speziellen Wahl der Implementierung und der implementierten Sprache, aber an diesem Punkt scheint es sicherlich irgendwie möglich zu sein, da es so viele Möglichkeiten gibt, dies in vier und so vielen Turing-vollständigen zu tun Sprachen, die Sie implementieren könnten.
quelle
ḋ
undṙ
anstelle von×
und verwendenị
. Die resultierende Sprache ist nicht ganz dieselbe Sprache wie Tip, aber sie ist ziemlich ähnlich und mit ziemlicher Sicherheit aus demselben Grund vollständig. Leiderḋ
ist es nicht in M implementiert, und ich kann Jelly nicht dazu bringen, Berechnungen mit willkürlicher Genauigkeit durchzuführen, wenn eine der Eingaben eine nicht ganzzahlige reelle Zahl ist. Wenn jemand eine andere Golfsprache kennt, in der diese Konstruktion funktionieren könnte, können Sie sie ausprobieren.C Brainfuck interpretieren, 187 Bytes
Probieren Sie es online aus
quelle
Lua interpretiert Brainf ***, 467 Bytes
Ich weiß, dass ich später noch etwas abnehmen kann, aber hier endete mein erster Durchgang. Übernimmt den Brainf-Code aus der Standardeingabe.
quelle
brains
, es macht immer Spaß, wenn Golfer eine Liste von Variablen zuweisen.CJam → ResPlicate Variant,
151413 Bytes-1 Byte danke an @ ais523
Die Variante ist die gleiche wie in dieser Antwort , mit der Ausnahme, dass die Anzahl der aus der Warteschlange entnommenen Elemente um eins unter der höchsten Anzahl in der Warteschlange liegt.
Das
l~{ ... }h
Teil nimmt nur ein Array als Eingabe und wiederholt sich, bis dieses Array leer ist.Erklärung für die Hauptschleife:
quelle
Chip , 20 + 3 = 23 Bytes (Regel 110)
+3 für Flagge
-z
Probieren Sie es online!
Diese Vorlage ist nicht perfekt, da Chip nicht (noch) jede Looping Fähigkeit hat, so muss der Ausgang übergeben werden , wenn die Eingabe mehrere Generationen zu simulieren, mit so etwas wie diesem (natürlich könnte man diese Schleife auf unbestimmte Zeit laufen, und Chip kann beliebig lange Eingaben verarbeiten, daher lautet diese Kombination "Turing Complete".
Diese Implementierung nimmt Eingaben und gegebene Ausgaben in Form von ASCIIs
0
und1
s auf. Die Logik hier ist wie folgt:Der Rest der Elemente ist für das Housekeeping bestimmt:
e*f
Verursacht die Ausgabe von ASCII-Zahlen undE~Zt
beendet die Ausführung zwei Bytes nach Erschöpfung der Eingabe (da die Breite mit jeder Generation um 2 zunimmt).quelle
Clojure, 75 Bytes (zyklisches Tag-System)
Update 1: ersetzt
some?
durchnil?
.Update 2: Ein Fehler
S
im else-Zweig von wurde behobenif s
.Implementiert das zyklische Tag-System , gibt zurück,
nil
wenn das Programm anhält, und wiederholt sich andernfalls für immer. Clojure glänzt hier wirklich mit unendlichen faulen Sequenzen (wie Zyklus ) und Destrukturierung . Einsen und Nullen werden als wahre und falsche Werte angegeben. Wenn der Datenstring ausgehts
wirdnil
.Ungolfed:
Beispielergebnisse:
quelle
JavaScript interpretiert Regel 110 , 131 Bytes (99 Bytes ?, 28 Bytes?)
Wie Sie sehen können, definiert der Code 3 Funktionen
a
,b
undc
. Vielleicht ist es möglich, Bytes zu sparen, indem man sie in einer Funktion kombiniert (ich verstehe nicht, wie), aber es ist gut, dass sie sich voneinander trennen, weil jeder von ihnen diese Herausforderung in gewissem Sinne bereits erfüllt.Die Funktion
a
nimmt 3 Zahlen als Eingabe und berechnet daraus ein seltsames Polynom. Wenn diese 3 Zahlen sind0
oder1
können sie als Regel 110-Zellen angesehen werden. Die Parität der Ausgabe vona
kann dann als der Wert der mittleren Zelle in der nächsten Generation angesehen werden. In gewisser Weise ist diese einfache Funktion bereits ein Regel 110-Interpreter (28 Byte):Wir können dann eine neue Funktion erstellen
b
, diea
jedes Zeichen einer Folge von Einsen und Nullen bewertet . Diesb
ist dann besser alsa
ein Regel-110-Dolmetscher. Unter mod 2 nach der Auswertung eines spart Klammern (99 Bytes):Um eine Funktion mit Regel 110 tatsächlich zu berechnen, muss der Benutzer den Startzustand und die Anzahl der Generationen angeben, nach denen die Ausgabe "erscheinen" soll. Wir können eine dritte Funktion erstellen
c
, die aus einer Folge von Einsen und Nullen und einer positiven Ganzzahl bestehtn
, die dannb
die Folgen
mal auswertet . Auf diese Weise können wir Regel 110 wirklich als Programmiersprache sehen, in der ein Programm ein Anfangszustand und eine Zahln
ist und die Ausgabe der Zustand nachn
Generationen ist. Die Funktionc
ist jetzt ein tatsächlicher Interpreter für diese Programmiersprache, daher ist der endgültige Code für diese Herausforderung der, den ich oben vorgestellt habe.quelle
JS -> Newline 854 Bytes
Super golfen dank google.
quelle
var
Aussagen kombinieren :var b=0,n=!0,c=[],h=[],e=0,l=[],m=0,f=2,a=0,g=!1;
var
tyClojure, 87 Bytes (Regel 110)
Gutschrift für den Paritätscode geht an Jens Renders! Ich hatte wirklich Mühe, dies auszudrücken, und ich wollte
[p q r]
von binär zu ganzzahlig konvertieren und eine Nachschlagetabelle verwenden.partition
Die Destrukturierung von Here und Clojure macht die Logikanwendung recht einfach. Diese Funktion gibt eine unendliche Folge von Zuständen zurück, sodass der Anrufer fürtake
so viele Zustände verantwortlich ist, wie er benötigt, oder nurnth
für das Überspringen zu einem bestimmten Zustand. Wenn Auffüllungen mit Null zwei Elemente anstelle von nur einem wären, würde das Band ständig wachsen und Randprobleme vermeiden. Jetzt bleibt die ursprüngliche Breite erhalten.Beispiel:
quelle
cycle
wäre in der Lage, das unendlicheAPL (Dyalog) → Fractran- Variante, 15 Bytes
Probieren Sie es online!
Die Funktion nimmt die Rationals als eine Liste von Zahlen auf und nicht als zwei Listen, die den Zähler und den Nenner enthalten, und gibt das Ergebnis aus, wenn das Programm endet. Dies implementiert eine Variante von Fractran, die am Ende des Programms das rationale 1/1 (= 1) hat. Die 1 hat (soweit ich weiß) keine Auswirkung auf die Turing-Vollständigkeit, da die Eingabe in das Programm nur dann auf der 1 landet, wenn keine der anderen Rationen funktioniert, und wenn dies der Fall ist, wird die Eingabe nicht geändert. Dies wird nur verwendet, damit die Funktion weiß, wann sie beendet werden muss.
Die TIO-Verknüpfung führt die Funktion für 2 Iterationen (damit Sie die Ausgabe sehen können, da das Programm nicht endet) auf der ersten Eingabe aus und führt die zweite Eingabe bis zum Abschluss aus. Anschließend wird die Ausgabe zurückgegeben.
(⊃0~⍨××0=1|×)⍣≡
Nimmt die Liste der Rationalen als linkes Argument, das als ⊣ bezeichnet wird, und die Eingabe als rechtes Argument, das als ⊢ bezeichnet wird(⊃0~⍨××0=1|×)
funktion zug1|×
erhalten Sie den Teil nach dem Komma (Modulo 1) des Produkts×
von ⊣ und ⊢0=
ist es gleich 0?××
Multiplizieren Sie dieses Ergebnis mit ⊣ × ⊢. Wenn das rationale × ⊢ keine ganze Zahl ist, wird es durch 0 ersetzt0~⍨
entferne alle Nullen⊃
Holen Sie sich das erste Element⍣
Schleife , bis≡
Eingang nicht ändert, zu beachten , dass das Ergebnis(⊃0~⍨××0=1|×)
als Eingangswiederverwendet wird, so dass , wenn er stoppt (als Ergebnis der 1 am Ende) , stoppt das Programm zu ändernquelle
JavaScript: Lambda-Kalkül (
123114)Repräsentiert mit Debruijn Indicies in Duples.
Der S-Kombinator ist
[0, [0, [0, [[3, 1], [2, 1]]]]]
K ist
[0, [0, 2]]
Ich bin
[0, 1]
Edit: Rasiert 9 Bytes durch Ersetzen
"number"==typeof c
durch!isNaN(c)
quelle
APL (Dyalog Unicode) , 15 Byte SBCS
Volles Programm, das einen verallgemeinerten eindimensionalen zellularen Automaten-Executor implementiert. Dies schließt Regel 110 ein, die vollständig ist. Fordert stdin zur Eingabe des Anfangszustands, der Anzahl der Iterationen (oder
≡
zur Fortsetzung bis zur Stabilisierung oder{⍵≡⎕←⍺}
zur Anzeige aller Zwischenwerte bis zur Stabilisierung) und des Regelsatzes auf.Probieren Sie es online! (4 Wiederholungen von Artikel 110)
⎕
Eingabeaufforderung für den Anfangszustand und⊢
ergibt das (trennt den Zustand von der Anzahl der Iterationen)⍣⎕
Geben Sie die Anzahl der Iterationen ein und wenden Sie die folgende Funktion so oft an:(
…)
Wenden folgende stillschweigende Funktion an:⌺3
Holen Sie sich alle Viertel der Länge 3 (mit der Information, ob sie am Rand sind) und wenden Sie die folgende implizite Funktion auf jedes Paar an:⊂
schließe die Nachbarschaft ein∘
und⊢
Ergib das (verwirf die Information, dass du am Rande bist)∘
dann∊⍨
Überprüfen Sie, ob sie Mitglieder von sind⎕
Aufforderung zur Auflistung der Nachbarschaften, die in der nächsten Iteration aktiviert werdenquelle