Turing-Complete Sprachinterpreter

42

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:

  1. Sie können eine beliebige Sprache verwenden, um diesen Interpreter zu erstellen, auch wenn er neuer als diese Herausforderung ist.
  2. Sie können eine beliebige Turing-complete-Sprache verwenden, sofern diese nicht mit derjenigen identisch ist, mit der Sie sie schreiben.
  3. Sie können Code nicht einfach auswerten, sondern beispielsweise Auswertungsfunktionen verwenden.
  4. Eine Erklärung, wie Sie sich dem näherten, ist nett, aber nicht erforderlich.
  5. Dies wird in Bytes bewertet.
  6. 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!

Arodebaugh
quelle
3
Ich würde auch eine Regel empfehlen, dass die implementierte Sprache anders sein muss als die Sprache, in der Sie sie implementieren, um triviale evalLösungen zu vermeiden .
ETHproductions
1
Eigentlich möchten Sie vielleicht nur evalBefehle / Funktionen sperren, da in einigen Sprachen Code in einer anderen Sprache ausgewertet werden kann.
ETHproductions
2
@arodebaugh Für zukünftige Herausforderungen können Sie Ihre Idee in der Sandbox veröffentlichen, wo Sie Feedback erhalten und Details wie diese ausbügeln können , bevor die Herausforderungen live gehen und beantwortet werden.
Martin Ender
1
OK, Sie sollten wahrscheinlich etwas genauer sein und etwas sagen wie "Sie dürfen Code nicht einfach mit einer beliebigen Methode ausführen", um andere triviale Antworten wie die von Bash + Perl zu vermeiden.
ETHproductions

Antworten:

16

Brachylog (2) → Korrespondenzproblem melden , 9 Bytes

~h=∋ᵐ\cᵐ=

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.

~h=∋ᵐ\cᵐ=
~h         Find {the shortest possible} list which starts with {the input}
  =        and for which all elements are equal
   ∋ᵐ      such that taking an element of each element,
     \cᵐ   and concatenating elements in corresponding positions,
        =  produces a list all of whose elements are equal.

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
1
Und die übliche "Zusammenfassung von Dingen, die sinnvoll sind und Bytes einsparen würden, aber der Brachylog-Interpreter nicht damit umgehen kann": Die ersten fünf Bytes könnten ausgedrückt werden als ~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 soll d.
12

Jelly → "Add Minimum zu transponieren", 5 4 Bytes

+"Ṃẞ

Probieren 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 Programm Z+Ṃ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
10

Mathematica interpretiert Conways Spiel des Lebens, 64 Bytes

CellularAutomaton@{224,{2,{t={2,2,2},{2,1,2},t}},{1,1}}~Nest~##&

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 Ganzzahl nals Argumente das ausgibt Ergebnis von nIterationen der Game of Life-Regel.

Für Ihren eigenen Genuss können Sie die verpackte Version verwenden

b = RandomInteger[1,{50,50}];
Manipulate[ArrayPlot[
  CellularAutomaton@{224,{2,{t={2,2,2},{2,1,2},t}},{1,1}}~Nest~##&
    [b, n] ]
, {{n,0}, 0, 100, 1}]

und scrollen Sie sich auf einem 50x50-Board durch 100 Generationen.

Greg Martin
quelle
Wenn ich das richtig verstehe, hat das eine feste Boardgröße? In diesem Fall kann es meiner Meinung nach nicht vollständig sein, oder?
DLosc
Jeder bestimmte Aufruf der Funktion hat eine feste Kartengröße, aber diese Kartengröße kann beliebig groß sein. (Beachten Sie, dass die zweite Hälfte des Beitrags ein Beispiel für die Beobachtung des Codes in Aktion beschreibt, nicht den tatsächlichen Code selbst.)
Greg Martin
Ich sage, damit GoL vollständig ist, muss es in der Lage sein, ein Muster zu erstellen, das unendlich wächst. (Zum Beispiel eine Segelflugwaffe.) Wenn diese Implementierung das Array nicht von einem Schritt zum anderen vergrößern kann, sondern es stattdessen toroidal umschließt, besteht sie den Test des unendlichen Wachstums nicht.
DLosc
Das ist sicher eine vernünftige Perspektive. Aber Implementierungen von Programmiersprachen auf physischen Computern erfüllen diesen Test nicht einmal! Man könnte sich mit einer (hypothetischen) Abfolge von physischen Computern mit immer mehr Speicher begnügen, von denen jeder in der Lage ist, einen weiteren Wert dieser berechenbaren Funktion zu berechnen. An diesem Punkt sollte man sich jedoch gleichermaßen mit einer (hypothetischen) Folge von Eingaben in ein solches GoL-Programm begnügen.
Greg Martin
9

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)

!-l[*+.r_]' !l[ l]r[ u.(;d' u)d(1[ r].[ l])( r)+]

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

[ ][ ][ ][ ][ ][ ][ ]
[ ][H][E][L][L][O][ ]
[ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ]

auf das Programm

Daten werden zuerst eingegeben:

!-l[*+.r_]' 

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

[ u.(;d' u)d(1[ r].[ l])( r)+]

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.

Zerstörbare Zitrone
quelle
Versuchen Sie, dies mehr Golf!
Arodebaugh
9

PerlThree Star Programmer- Variante, 26 + 1 = 27 Byte

++$a[$a[$a[$_]]]for@F;redo

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.010Produzieren 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: @Fist die Eingabe in das Programm in Array-Form (dies ist eine Folge von -a); und redowiederholt das gesamte Programm, da es sich in einer impliziten Schleife befindet (auch eine Folge von -a).


quelle
1
Ich denke, es ist sinnvoller, wenn der Pfeil "reduziert auf" bedeutet als "interpretiert".
Quintopia
9

x86-Assembly (Intel-Syntax / MASM) -Brainfuck 2127 Bytes.

Immer noch golffähig

.386
.model flat,stdcall
.stack 4096
include \masm32\include\masm32.inc
includelib \masm32\lib\masm32.lib
ExitProcess proto,dwExitCode:dword
.data
bfsrc BYTE 200 dup(0) 
bfcells BYTE 100 dup(0) 
loopStack DD 5 dup(0) 
charBuf BYTE 5 dup(0) 
newline BYTE 10,0 
prompt BYTE "$",0 
hr BYTE 50 dup('-'),0 
space BYTE ' ',0
.code
EvalBf proc
    start:
    invoke StdOut, addr prompt
    invoke StdIn, addr bfsrc,200
    cmp bfsrc,0
    je exit
    mov eax,0 
    mov ebx,0 
    mov ecx,0 
    processInstruction:
    cmp BYTE PTR bfsrc[ebx], '+'
    je plus
    cmp BYTE PTR bfsrc[ebx], '-'
    je minus
    cmp BYTE PTR bfsrc[ebx], '>'
    je fwd
    cmp BYTE PTR bfsrc[ebx], '<'
    je back
    cmp BYTE PTR bfsrc[ebx], '['
    je open
    cmp BYTE PTR bfsrc[ebx], ']'
    je close
    cmp BYTE PTR bfsrc[ebx], '.'
    je dot
    jmp processNextInstruction
    plus:
    inc BYTE PTR bfcells[eax]
    jmp processNextInstruction
    minus:
    dec BYTE PTR bfcells[eax]
    jmp processNextInstruction
    fwd:
    inc eax
    jmp processNextInstruction
    back:
    dec eax
    jmp processNextInstruction
    open:
    mov loopStack[ecx*4],ebx
    inc ecx
    jmp processNextInstruction
    close:
    dec ecx
    cmp BYTE PTR bfcells[eax], 0
    je processNextInstruction
    mov ebx,loopStack[ecx*4]
    inc ecx
    jmp processNextInstruction
    dot:
    mov dl, BYTE PTR bfcells[eax]
    mov BYTE PTR charBuf[0], dl
    mov BYTE PTR charBuf[1],0anything
    push eax
    push ecx
    invoke StdOut, addr charBuf
    pop ecx
    pop eax
    jmp processNextInstruction
    processNextInstruction:
    inc ebx
    cmp BYTE PTR bfsrc[ebx], 0
    je done
    jmp processInstruction
    done:
    invoke StdOut, addr newline
    mov eax, 0
    printNext:
    cmp eax, 100
    jge reset
    push eax
    invoke dwtoa, BYTE PTR bfcells[eax], addr charBuf
    invoke StdOut, addr charBuf
    invoke StdOut, addr space
    pop eax
    inc eax
    jmp printNext
    reset:
    invoke StdOut, addr newline
    invoke StdOut, addr hr
    invoke StdOut, addr newline
    jmp start

    exit:
    invoke ExitProcess,0
EvalBf endp
end EvalBf
Christopher
quelle
3
In der Regel werden Baugruppenantworten in der Größe des resultierenden Maschinencodes gezählt, sodass Sie die Baugruppe überhaupt nicht spielen müssen. Minimieren Sie lediglich die Anzahl / Größe der Anweisungen.
Robert Fraser
@RobertFraser uhh Ich weiß nicht, wie ich das zählen soll: P
Christopher
3
Eigentlich habe ich zuerst irgendwie den Titel "x86 asm implementiert in Brainfuck" gelesen und war irgendwie beeindruckt :)
quetzalcoatl
@Quetzalcoatl Das wäre beeindruckend
Christopher
1
pls golf variable / label names ty
ASCII
8

Pip- Interpretation von zyklischen Tag-Systemen , 16 Byte

YqWyyPBg@++vXPOy

Ü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.

  • Wenn das Zeichen 1 ist, wird die aktuelle Produktion an die rechte Seite der Datenzeichenfolge angehängt.
  • Wenn das Zeichen 0 ist, wird nichts angehängt.

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

                  g is list of cmdline args; v is -1 (implicit)
 q                Read a line of stdin for the data string
Y                 and yank it into the y variable
  Wy              While data string is nonempty:
       g@++v       Retrieve the next production from g (using cyclic indexing)
             POy   Pop the first character of y
            X      String-multiply: result is the production if the first character of y
                   was 1, or empty string if it was 0
    yPB            Push that string to the back end of y
DLosc
quelle
hey, ich habe mich nur daran erinnert, dass Sie den Datenstring nicht eingeben müssen; es kann nur eine 1Quelle 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)
Destructible Lemon
8

Iterierte verallgemeinerte Collatz-Funktionen -> Python 2, 46 Bytes

a,b,x,m=input()
while-~x%m:x=x/m*a[x%m]+b[x%m]

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.

Quintopie
quelle
Verdammt gute Arbeit. Ich hatte gehofft, das Kopfgeld zu gewinnen, aber gute Arbeit
Christopher
7

ResPlicate- Variante -> Python 2, 47 Bytes

l=input()
while l:l=l[2+l[0]:]+l[2:2+l[0]]*l[1]

Diese Funktion interpretiert eine Variante von ResPlicate

  • Ein Programm ist eine Python-Liste mit gerader Länge und geraden Elementen an geraden Indizes.
  • ohne I / O.
  • Bei dem Versuch, mehr Werte zu kopieren, als im Rest der Warteschlange vorhanden sind, wird lediglich der Rest der Warteschlange kopiert (dh das kopierte Bit wird nicht mit Nullen auf die erforderliche Länge aufgefüllt).

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.

Quintopie
quelle
2
Warum nicht l=input()? Wäre ein Byte kürzer.
Feersum
7

Perl -aE / A-Maschine , 24 Bytes

$p=$a[$p]+=$_ for@F;redo

Probieren 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 IBefehlsfolgen zwischen DBefehlen darstellt. (Sie können zwei oder mehr aufeinanderfolgende DBefehle angeben, indem Sie einen "Durchlauf von 0 IBefehlen" dazwischen platzieren. Die Syntax ist also völlig allgemein.)

Erläuterung

Wie aus dem Programm hervorgeht, werden die Befehle Iund nicht Deinzeln 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- Is und eines zu wechseln D. 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 $azum Speichern des RAM und $pals Datenzeiger (Indizieren in das Array):

$p=$a[$p]+=$_
         + $_  add {the run length}
   $a[$p]      to the element of $a pointed to by $p
   $a[$p] =    storing the result back into that element
$p=            and also in the pointer itself

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@FSchleife durchläuft zusammen mit der -aBefehlszeilenoption die Felder der Standardeingabe (die Standarddefinition von "Feld" wird hier in Leerzeichen aufgeteilt). Die redoSchleife 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.

ais523
quelle
Willkommen zurück! Wir müssen keine Flags mehr für Interpreter setzen, beachten Sie nur, dass dies Perl mit ist -a. codegolf.meta.stackexchange.com/a/14339/9365
Dom Hastings
6

Gelee2-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}, { abc, ba, caaa} mit Anfangskette aaa; 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

µḢị⁴⁸;Ḋß
           {implicit: initialise internal state from first argument}
µ          Disregard the second command-line argument by default
 Ḣ         Take the first element, removing it from the internal state
  ị⁴       Use the value to index into the second argument
    ⁸;     Prepend (the rest of) the internal state
      Ḋ    Discard the first element of the internal state
       ß   Loop forever

quelle
6

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.

a52
quelle
1
Die maximale Länge der Pfosten ist mehr als ausreichend, um in die Übergangstabelle zu passen
ASCII,
6

C Implementierung der (2,3) Turing-Maschine , 236 205 Bytes ( 46 31 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.)

#define c char
j;i;k;c s,d[256];c main(){c*p=d+128;gets(d);
for(;k<256&&d[k];)d[k++]-=48;for(;++j<256;)
{c t=*p;*p=-t*t+(2-s)*t+1+s;p+=(s^t==0)*2-1;s=s?t%2:!t%3;
for(i=0;++i<256;)printf("%d",d[i]);puts("");}}

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 und for(;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.

a52
quelle
1
Wow, und das ist dein erster Code Golf hier! Wunderbar!
Zacharý
Sie können die globalen Variablendeklarationen wie folgt kürzen: k,j;c s,d[256];( intIst in C impliziert, dann können Sie auch izur globalen Deklaration wechseln , um weitere 3 Byte zu sparen.)
Appleshell,
@Appleshell Danke, das mache ich.
a52
Sie können den String-Null-Terminal-Check in die for-Schleife verschieben. In-Lining k++und Entfernen der noch {}ein paar Bytes speichert: for(;k<256&d[k];)d[k++]-=-48;Da jnur ein Zeitnehmer (Wert nie benutzt) ist , können Sie es ersetzen (und i) mit knach rückwärts gezählt werden: Sie weiß , k==256nach der ersten Schleife, so auf Null in den zweiten Countdown for(;k>0;), was geht k==-1, damit die letzte Schleife werden kann for(;++k<256;). (Haftungsausschluss: Ich spiele normalerweise Golf C#, aber dies schien zu kompilieren).
VisualMelon
1
@VisualMelon Ich habe das Problem festgestellt. Ich brauchte nicht zu verwenden k<256&&d[k], &weil d[k]bei ausgewertet wurde k==256. Da knicht mehr garantiert wurde, dass es 256nach 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.)
a52
5

Röda implementiert Fractran , 114 112 106 Bytes

1 Byte gespart dank @fergusq durch Umstellen der Parameter

f&n,a{x=1{x=0;(a/" ")()|[_/`/`]|[parseInteger(_[0],_1[1])]|{|q,w|{n*=q/w;x=1}if[n%w<1,x<1]}_,_}while[x>0]}

Probieren Sie es online!

Rufen Sie die Funktion wie folgt: f reference_to_input program. Die Ausgabe wird am Speicherort von gespeichert input.

Kritixi Lithos
quelle
Das Semikolon nach e[1]ist überflüssig. Sie können auch durch Änderung Parameter , um ein Byte speichern: f&n,a.
Fergusq
@fergusq Danke für den f&n,aTrick, und ich wollte gerade das Semikolon entfernen, als Sie kommentierten :)
Kritixi Lithos
5

Clojure, 82 81 bytes (Turingmaschine)

Update: hat ein Leerzeichen von entfernt t{} s.

#(loop[p 0 t{}s 1](if-let[[S M N](%[(or(t p)0)s])](recur(+ p M)(assoc t p S)N)t))

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 Nsich ein nilund der folgende Vorgang wird abgebrochen , if-letda der entsprechende Zustandsübergang nicht in der Eingabe-Hash-Map gefunden wird %. Tatsächlich ist jeder Wert für diesen Status ausreichend, z. B. :abort0 oder -1.

Ungolfed mit einem 3-Zustands-2-Symbol-Busy-Biber aus Wikipedia .

(def f #(loop[pos 0 tape {} state 1]
          (if-let [[sym move next-state](%[(get tape pos 0)state])]
            (do (println [pos tape state])
                (recur(+ pos move)(assoc tape pos sym)next-state))
            tape)))

(f {[0 1] [1  1 2]
    [0 2] [1 -1 1]
    [0 3] [1 -1 2] 
    [1 1] [1 -1 3]
    [1 2] [1  1 2]
    [1 3] [1  1]})

{0 1, 1 1, -1 1, -2 1, -3 1, 2 1}

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.

NikoNyrh
quelle
5

MTipp , 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.

ıi=1

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

Ṅ×ịß
Ṅ     Print {the left argument} and a newline; also resolves a parser ambiguity
  ị   {The left argument}th element of {the right argument}, wrapping on OoB
 ×    Multiply {the left argument} by {the chosen element}
   ß  Recursive call; arguments: {the product} and {the same right argument}

[1,2,3][1,2,3,1,2,3,1,2,3,…]rx+s, das ein Polynom ist, und die "Basisumwandlung", die in vielen Golfsprachen eingebaut ist, ist tatsächlich ein getarnter Allzweck-Polynom-Bewerter. Alles, was wir tun müssen, ist, eine Liste von Ziffernlisten zu indizieren, sie mit der Basis umzuwandeln, und wir sind fertig, oder?

xx

x(xy)xy. Sicher, wir könnten das Verkettungsverhalten auf so ziemlich alles setzen, was wir wollen, aber das würde ein ganzes Byte kosten, und die Golfspracheneingaben zu dieser Frage werden so kurz, dass ein Byte viel ist.

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.

s

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?

(xy)(xy)¹×ịß¹¹ 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.

ais523
quelle
Nachdem wir darüber noch etwas nachgedacht haben, könnten wir dies auf drei Bytes reduzieren, indem wir 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.
AIS523
4

C Brainfuck interpretieren, 187 Bytes

t[999],*p=t,c,i,l;f(char*t){for(i=0;c=t[i];i++){c^62?c^60?c^43?c^45?c^46?c^44?c^91:(*p=getchar()):putchar(*p):--*p:++*p:--p:++p;if(c==93&&*p)for(l=1;l>0;)c=t[--i],c==91?l--:c==93?l++:0;}}

Probieren Sie es online aus

Johan du Toit
quelle
3
Welp, es musste eine Antwort mit BF geben.
Zacharý
4

Lua interpretiert Brainf ***, 467 Bytes

b,r,a,i,n,s=0,io.read,{0},1,1,"><+-.,[]"c,f=r(),{function()n=n+1;a[n]=a[n]or 0;end,function()n=n-1;a[n]=a[n]or 0;end,function()a[n]=a[n]+1;end,function()a[n]=a[n]-1;end,function()io.write(string.char(a[n]))end,function()a[n]=io.read():byte()end,function()i=a[n]~=0 and i or c:find("]",i)end,function()if a[n]~=0 then b,x=1,""repeat i=i-1 x=c:sub(i,i)b=x=="["and b-1 or x=="]"and b+1 or b until b==0 and x=="["end end}repeat f[s:find(c:sub(i,i),1,1)]()i=i+1 until i>#c

Ich weiß, dass ich später noch etwas abnehmen kann, aber hier endete mein erster Durchgang. Übernimmt den Brainf-Code aus der Standardeingabe.

Ausplaudern
quelle
2
+1 für die brains, es macht immer Spaß, wenn Golfer eine Liste von Variablen zuweisen.
Zacharý
4

CJam → ResPlicate Variant, 15 14 13 Bytes

-1 Byte danke an @ ais523

l~{(/((*+e_}h

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~{ ... }hTeil nimmt nur ein Array als Eingabe und wiederholt sich, bis dieses Array leer ist.

Erklärung für die Hauptschleife:

    e# Stack:             | [3 2 1 1 2 2 2 1]
(   e# Pop first element: | [2 1 1 2 2 2 1] 3
/   e# Split chunks:      | [[2 1 1] [2 2 2] [1]]
(   e# Pop first:         | [[2 2 2] [1]] [2 1 1]
(   e# Pop first:         | [[2 2 2] [1]] [1 1] 2
*   e# Repeat array:      | [[2 2 2] [1]] [1 1 1 1]
+   e# Concatenate:       | [[2 2 2] [1] 1 1 1 1]
e_  e# Flatten:           | [2 2 2 1 1 1 1 1]
Esolanging Fruit
quelle
Sie brauchen das Inkrement hier nicht wirklich. Geben Sie einfach an, dass die Blocklängen im ursprünglichen Programm um 1 erhöht werden sollen. Dies schadet der Turing-Vollständigkeit von ResPlicate nicht (es gibt TC-Konstruktionen, bei denen Blocklängen und Wiederholungszahlen niemals miteinander gemischt werden).
3

Chip , 20 + 3 = 23 Bytes (Regel 110)

AZZ
>}/a
`)\'E~Zte*f

+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 0und 1s auf. Die Logik hier ist wie folgt:

p := value of left neighbor cell    AZZ
q := value of current cell          AZ
r := value of right neighbor cell   A

q' := ((r xor q) and p) or          >}/a
      ((r or q) and ~p)             `)\'

Der Rest der Elemente ist für das Housekeeping bestimmt: e*fVerursacht die Ausgabe von ASCII-Zahlen und E~Ztbeendet die Ausführung zwei Bytes nach Erschöpfung der Eingabe (da die Breite mit jeder Generation um 2 zunimmt).

Phlarx
quelle
3

Clojure, 75 Bytes (zyklisches Tag-System)

Update 1: ersetzt some?durch nil?.

Update 2: Ein Fehler Sim else-Zweig von wurde behoben if s.

#(loop[[p & P](cycle %)[s & S]%2](if(nil? s)S(recur P(if s(concat S p)S))))

Implementiert das zyklische Tag-System , gibt zurück, nilwenn 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 ausgeht swird nil.

Ungolfed:

(def f #(loop[[p & P] (cycle %) [s & S] %2 i 5]
          (do
            (pprint [p (concat [s] S)])
            (if (and (some? s) (pos? i))
              (recur P (if s (concat S p) S) (dec i))))))

Beispielergebnisse:

(f [[false]] [true true])
[[false] (true true)]
[[false] (true false)]
[[false] (false false)]
[[false] (false)]
[[false] (nil)]

(f [[false true true] [true false] [true false true]] [true])
[[false true true] (true)]
[[true false]      (false true true)]
[[true false true] (true true)]
[[false true true] (true true false true)]
[[true false]      (true false true false true true)]
[[true false true] (false true false true true true false)]
NikoNyrh
quelle
2

JavaScript interpretiert Regel 110 , 131 Bytes (99 Bytes ?, 28 Bytes?)

a=(p,q,r)=>q+r+q*r+p*q*r
b=l=>{r="";for(i=0;i<l.length-2;i++)r+=a(l[i],+l[i+1],+l[i+2])%2;return r}
c=(l,n)=>!n?l:c(b(0+l+0),n-1)

Wie Sie sehen können, definiert der Code 3 Funktionen a, bund c. 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 animmt 3 Zahlen als Eingabe und berechnet daraus ein seltsames Polynom. Wenn diese 3 Zahlen sind 0oder 1können sie als Regel 110-Zellen angesehen werden. Die Parität der Ausgabe von akann 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):

a=(p,q,r)=>(q+r+q*r+p*q*r)%2

Wir können dann eine neue Funktion erstellen b, die ajedes Zeichen einer Folge von Einsen und Nullen bewertet . Dies bist dann besser als aein Regel-110-Dolmetscher. Unter mod 2 nach der Auswertung eines spart Klammern (99 Bytes):

a=(p,q,r)=>q+r+q*r+p*q*r
b=l=>{r="";for(i=0;i<l.length-2;i++)r+=a(l[i],+l[i+1],+l[i+2])%2;return r}

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 besteht n, die dann bdie Folge nmal auswertet . Auf diese Weise können wir Regel 110 wirklich als Programmiersprache sehen, in der ein Programm ein Anfangszustand und eine Zahl nist und die Ausgabe der Zustand nach nGenerationen ist. Die Funktion cist 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.

Jens Renders
quelle
Berechnet dies 110 mit dem richtigen Hintergrund? Eine frühere Antwort von mir wurde gelöscht, weil sie nicht den Hintergrund hatte.
Weizen-Zauberer
@WheatWizard der Hintergrund ist Teil der Eingabe, deine Antwort sollte dafür nicht gelöscht worden sein
Jens Renders
Der Hintergrund sollte unendlich sein. Können Sie unendlich viel eingeben?
Weizen-Zauberer
@WheatWizard es muss nicht unendlich sein, es muss beliebig groß gemacht werden können und es kann
Jens Renders
1
Regel 110 ist nicht vollständig, wenn Sie die Generation im Voraus bestimmen und Sie in der mir bekannten Konstruktion unendliche Eingaben benötigen. Selbst wenn jemand eine Konstruktion mit einem endlichen Anfangszustand gefunden hat, können Sie den Speicher oder die Zeit, die für die Ausführung des Programms erforderlich sind, nicht kennen, da Sie dann das Halteproblem lösen könnten.
Ørjan Johansen
2

JS -> Newline 854 Bytes

(function(d){var b=0;var n=!0;var c=[];var h=[];var e=0;var l=[];var m=0;var f=2;var a=0;var g=!1;var k=function(a){if(a===1)return!1;if(a%2===0&&a!==2)return!1;if(a%3===0&&a!==3)return!1;if(a%5===0&&a!==5)return!1;if(a%7===0&&a!==7)return!1;for(var b=7;b<d.round(d.sqrt(a))+1;b++)if(a%b===0)return!1;return f=a,!0;};var j=0;var i=0;var o=function(q){var o=d.__split(q,'\n');d.println(o);for(var n=0;n<o.length;n++)if(n>=f^2&&n<=f+1^2&&k(n)){f=n;for(var p=0;p<o[n].length;p++){if(o[n]==='+'&&(a+=c[b],b++),o[n]==='-')if(g===!0&&a<=0)break;else a-=c[b],b++;if(o[n]==='*'&&(a*=c[b],b++),o[n]==='/'&&(a/=c[b],b++),o[n]==='s'&&(a=d.sqrt(a)),o[n]==='%'&&(a%=c[b],b++),o[n]==='a'&&l.push(a),o[n]==='g'&&(a=c[b],b++),o[n]==='q'&&c.push(a),o[n]==='i'&&a++,o[n]==='d')if(g===!0&&a<=0)break;else a--;o[n]==='r'&&(g=!0),o[n]==='w'&&(g=!1),o[n]==='['&&(j=n),o[n]===']'&&a>0&&(n=j,h[e]--),o[n]==='{'&&(i=n),o[n]==='}'&&h[e]>0&&(n=i,h[e]--),m=a,o[n]==='k'&&e++;}}};});

Super golfen dank google.

Christopher
quelle
Ich denke, Sie haben diese Antwort auf die falsche Herausforderung gestellt. Wolltest du es für diese Challenge posten ?
1
In diesem Fall müssen Sie die Implementierung ändern, um die unterschiedlichen Siegbedingungen zu erreichen. Das ist Code-Golf , kein Beliebtheitswettbewerb . Zum Beispiel haben Sie viele Variablennamen, die deutlich kürzer sein könnten, was bedeutet, dass diese Lösung kein ernstzunehmender Konkurrent ist. Sie könnten es vielleicht vorerst löschen und es dann wiederherstellen, wenn Sie Zeit zum Golfen haben.
1
Nichtsdestotrotz verstoßen Antworten, die keinen ernsthaften Versuch machen, die Siegbedingung zu optimieren, gegen die Regeln . Grund genug, es zu löschen, bis es den Regeln entspricht.
1
Sie können alle varAussagen kombinieren :var b=0,n=!0,c=[],h=[],e=0,l=[],m=0,f=2,a=0,g=!1;
Esolanging Fruit
1
Pls entfernen Sie alle varty
ASCII-only
1

Clojure, 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.

#(iterate(fn[S](for[[p q r](partition 3 1(concat[0]S[0]))](mod(+ q(* q(+ 1 p)r)r)2)))%)

partitionDie 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ür takeso viele Zustände verantwortlich ist, wie er benötigt, oder nur nthfü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:

(def f #(iterate(fn[S](for[[p q r](partition 3 1(concat[0]S[0]))](mod(+ q(* q(+ 1 p)r)r)2)))%))

(pprint (take 5 (f '(0 0 0 0 0 1 1 1 0 0 1 0 0))))
((0 0 0 0 0 1 1 1 0 0 1 0 0)
 (0 0 0 0 1 1 0 1 0 1 1 0 0)
 (0 0 0 1 1 1 1 1 1 1 1 0 0)
 (0 0 1 1 0 0 0 0 0 0 1 0 0)
 (0 1 1 1 0 0 0 0 0 1 1 0 0))
NikoNyrh
quelle
1
Wenn Sie immer nur mit der Originalbreite arbeiten, kann dies möglicherweise nicht vollständig sein, da nur begrenzter Speicherplatz zur Verfügung steht. (Tatsächlich erfordern alle bekannten Turing-Vollständigkeitskonstruktionen aus Regel 110 das "Auffüllen", das zum Erweitern der Breite verwendet wird, wenn das Programm ein von der Benutzereingabe vorgegebenes Muster aufweist, das sich links und rechts von dem Muster unterscheidet nur mit Nullen.)
Ich sehe, das macht die Simulation dann ziemlich schwierig. Clojures cyclewäre in der Lage, das unendliche
Füllmuster
Wenn Sie sich das überlegen, wäre es nicht allzu schwierig, dieses Füllmuster als zusätzliches Argument zu verwenden und das simulierte Band um einen Block nach links und rechts zu erweitern. Die Informationsgeschwindigkeit beträgt hier 1 Block / Iteration, daher müssen wir nur den "Lichtkegel" um den zentralen Block simulieren, der die asymmetrische Struktur aufweist. (CMIIW)
NikoNyrh
1

APL (Dyalog)Fractran- Variante, 15 Bytes

(⊃0~⍨××0=1|×)⍣≡

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 zug

  • 1|×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 ersetzt

  • 0~⍨ 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 ändern

Kritixi Lithos
quelle
1

JavaScript: Lambda-Kalkül ( 123 114)

Repräsentiert mit Debruijn Indicies in Duples.

V=function b(c,d){if(!isNaN(c)){for(;--c;)d=d[1];return d[0]}return 0==c[0]?e=>b(c[1],[e,d]):b(c[0],d)(b(c[1],d))}

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 cdurch!isNaN(c)

SYZYGY-DEV 333
quelle
0

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.

⎕∊⍨∘(⊢∘⊂⌺3)⍣⎕⊢⎕

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 werden

Adam
quelle