In dieser Herausforderung schreiben Sie einen Interpreter für 2 ^Ω (transkribiert als TwoMega ), eine Sprache, die lose auf Brainfuck mit einem unendlich dimensionalen Speicherplatz basiert .

Die Sprache

2 ^Ω enthält drei Zustandselemente:

• Das Band , eine unendliche Liste von Bits, wurde alle auf 0 initialisiert. Es hat ein Element ganz links, aber kein Element ganz rechts.

• Der Speicherzeiger , eine nicht negative Ganzzahl, die ein Index eines Elements im Band ist. Ein höherer Speicherzeiger bezieht sich auf eine Bandzelle weiter rechts; Ein Speicherzeiger von 0 bezieht sich auf das Element ganz links. Der Speicherzeiger wird auf 0 initialisiert.

• Der Hypercube , eine konzeptionell ∞- dimensionale "Box" von Zellen, von denen jede ein auf 0 initialisiertes Bit enthält. Die Breite des Hypercubes ist in jeder Dimension an nur 2 Zellen gebunden, aber die Unendlichkeit der Dimensionen bedeutet die Anzahl von Zellen ist unzählig .

Ein Index in den Hypercube ist eine unendliche Liste von Bits, die sich auf eine Zelle im Hypercube bezieht (genauso wie eine endliche Liste von Bits verwendet werden könnte, um auf einen Hypercube mit endlicher Dimension zu verweisen). Da das Band eine unendliche Liste von Bits ist, bezieht sich das gesamte Band immer auf ein Element des Hypercube. Dieses Element wird als Referent bezeichnet .

2 ^Ω gibt 7 verschiedenen Zeichen Bedeutung:

• < Dekrementiert den Speicherzeiger um 1. Das Dekrementieren unter 0 ist ein undefiniertes Verhalten, sodass Sie nicht damit umgehen müssen.
• > erhöht den Speicherzeiger um 1.
• ! dreht das Bit beim Referenten um.
• . gibt das Bit am Referenten aus.
• ^Ersetzt das Bit an der Zelle, auf die der Speicherzeiger auf dem Band zeigt, durch die Umkehrung des Bits am Referenten.
• [x]führt den Code xaus, solange das Bit am Referenten 1 ist.

Die Herausforderung

Ihre Aufgabe ist es, ein Programm zu schreiben, das eine Zeichenfolge als Eingabe verwendet und diese Eingabe als 2 ^Ω- Programm ausführt .

Dies ist Code-Golf , daher gewinnt die kürzeste gültige Antwort (gemessen in Bytes).

Anmerkungen

• Sie können davon ausgehen, dass das Programm nur aus den Zeichen besteht <>!.^[]und []ordnungsgemäß verschachtelt ist.
• Ihr Interpreter sollte nur durch den verfügbaren Speicher im System begrenzt sein. Es sollte in der Lage sein, die Beispielprogramme in angemessener Zeit auszuführen.

Beispielprogramme

Druck 1:

!.

Drucken 010:

.!.!.

0 für immer drucken:

![!.!]

Drucken Sie 0 für immer oder 1 für immer, wenn !vorangestellt wird:

[.]![!.!]

Python 2 , 167 Bytes

t=h=I=0
m=1
E=''
for c in input():i='[<>!.^]'.find(c);E+=' '*I+'while+2**t&h: m/=2 m*=2 h^=2**t print+(2**t&h>0) t=t&~m|m*(2**t&h<1) #'.split()[i]+'\n';I-=~-i/5
exec E

Probieren Sie es online aus!

t ist das Band. t = 6 bedeutet, dass das Band [0 1 1 0 0 0…] ist.

m ist 2 hoch zur Potenz des Speicherzeigers. So m = 8 Mittel auf Band wir zeigen Bit 3.

h ist der Hyperwürfel. h = 80 (Bits 4 und 6 gesetzt) ​​bedeutet, dass die Bits bei [0 0 1 0…] und [0 1 1 0…] gesetzt sind.

Um das Bit beim Referenten zu lesen, überprüfen wir 2 ^t & h . Um es umzudrehen, führen wir h ^ = 2 ^{t aus} .

Wir übersetzen die Anweisungen in Python-Code und führen das Ergebnis aus. Ich speichere die Einrückungsstufe der while-Schleifen.

JavaScript (Node.js) , 148 Byte

x=>eval(x.replace(e=/./g,c=>({'<':'u/=2','>':'u*=2','!':'e[v]^=1','.':'alert(+!!e[v])','^':'v=(v|u)^u*e[v]','[':'while(e[v]){'}[c]||'}')+';',v=u=1))

Probieren Sie es online aus!

Es ist komplett

BoolFuck TwoMega
< >^>^>[!]^<<<<[!]^>>[!]!^>[!]!^>[!]!^<<<<(>^>^>1<<<<1>>0>0>0<<<<)
> ^<^<[!]^>>>>[!]^<<[!]!^<[!]!^<[!]!^>>>(^<^<1>>>>1<<0<0<0>>>)

Benötigen Sie init, um sich an einigen Stellen nach rechts zu bewegen, und initiieren Sie das aktuelle und rechte Bit der Adresse als 1 ( >>>>>>>>^>^<)

Probieren Sie es online aus!

Platz nin BoolFuck ist geschrieben als (0, 0, ..., 0(n*0), [1], 1, 0, 0, ...).

Denn >es tut n=>n+1

     0 0 0 0 0[1]1 0 0 0 0
^    0 0 0 0 0[x]1 0 0 0 0
<    0 0 0 0[0]x 1 0 0 0 0
^    0 0 0 0[y]x 1 0 0 0 0, yx != 01
<    0 0 0[0]y x 1 0 0 0 0
[!]^ 0 0 0[1]y x 1 0 0 0 0, (0yx10) = 0
>>>> 0 0 0 1 y x 1[0]0 0 0
[!]^ 0 0 0 1 y x 1[1]0 0 0, (1yx10) = 0
<<   0 0 0 1 y[x]1 1 0 0 0
[!]! 0 0 0 1 y[x]1 1 0 0 0, (1yx11) = 1
^    0 0 0 1 y[0]1 1 0 0 0
<    0 0 0 1[y]0 1 1 0 0 0
[!]! 0 0 0 1[y]0 1 1 0 0 0, (1y011) = 1
^    0 0 0 1[0]0 1 1 0 0 0
<    0 0 0[1]0 0 1 1 0 0 0
[!]! 0 0 0[1]0 0 1 1 0 0 0, (10011) = 1
^    0 0 0[0]0 0 1 1 0 0 0
>>>  0 0 0 0 0 0[1]1 0 0 0

Gleich wie <funktioniert

Brain-Flak Classic , 816 Bytes

<>(((<(())>)))<>{(([][][])(((({}){}[])({}))({})[]([][](({})(({}())(({}){}{}({}(<()>))<{<>({}<>)}{}>))))))(([]{()(<{}>)}{}){<((<{}>))<>(()(){[](<{}>)}{}<{({}[]<({}<>)<>>)}{}{}>)<>({()<({}<>)<>>}<<>{<>(({}){}<>({}<>)[])<>}{}<>({()<({}[]<<>({}<>)>)>}{})<>(({})<<>{({}[]<({}<>)<>>)}({}<>)<>{({}<>)<>}>)<>>)<>({}<>)<>>}{}([]{()(<{}>)}{}){{}<>({})(<>)}{}([]{()(<{}>)}{}){(<{}<>({}<{((<({}[])>))}{}{((<(())>))}{}>)<>>)}{}([]{()(<{}>)}{}){(<{}<>({}<({}())>)<>>)}{}([]{()(<{}>)}{}){(<{}<>[({})]<>>)}{}([]{()(<{}>)}{})<{((<{}>))<>{}({}<{<>(({}){}<>({}<>)[])<>}{}<>({()<({}[]<<>({}<>)>)>}{})<>(((){[](<{}>)}{})<<>{({}[]<({}<>)<>>)}{}(<>)<>{({}<>)<>}>)<>>)<>({}<>)<>}{}(<>)<>{({}<>)<>}{}>()){((({}[]<>){(<{}({}<>)>)}{}())<{({}<({}<>)<>((((((([][][]){}){}){}()){}){}({})())[][])>{[](<{}>)}{}{()(<{}>)}{})}{}({}<>)>[]){{}(<>)}}{}}

Probieren Sie es online aus!

Dieser Code wurde nur geschrieben, damit ich einen Beweis für die Vollständigkeit von Turing schreiben kann.

Nachweis der Turing-Vollständigkeit

Wir zeigen eine Reduzierung von Boolfuck auf TwoMega:

Boolfuck   TwoMega
>          >>
<          <<
.          !^!.!^!
[          !^![!^!
]          !^!]!^!
+          !^[!]^[>!^<[!]!^>[!]!^<]

Diese Übersetzung speichert den Boolfuck-Status in den geradzahligen Bandzellen in TwoMega. Alle übersetzten Befehle behalten die folgenden Invarianten bei:

• Der Speicherzeiger befindet sich in einer Zelle mit gerader Nummer.
• Alle ungeradzahligen Bandzellen sind Null.
• Für jedes mögliche Band mit allen ungeradzahligen Zellen Null ist der entsprechende Wert auf dem Hyperwürfel Null.

Das Snippet !^!bleibt [0]0konstant und wechselt zwischen 0[0]und [1]1(wobei die Aufmerksamkeit auf die Linie auf dem Hypercube beschränkt ist, die erreichbar ist, ohne den Speicherzeiger zu bewegen). Als solches wird es verwendet, um den aktuellen Bandwert vorübergehend in den Referenten für die Boolfuck-Befehle zu setzen, die sich darum kümmern.

Wenn TwoMega einen Eingabebefehl ,mit der erwarteten Semantik erhalten würde, würde der Boolfuck-Befehl ,in übersetzt >^<,!^>[!]!^<. Da ,es nicht erforderlich ist, zu beweisen, dass Boolfuck Turing-vollständig ist, hat das Fehlen eines Eingabebefehls keinen Einfluss auf diesen Beweis.

Python 3 , 297 284 274 Bytes

-10 Bytes dank Ovs und Jonathan Allan

C=input()
h={}
t=set()
def f(C,p):
 c=C[0];r=hash(frozenset(t));v=h.get(r,0)
 p={"<":p-1,">":p+1}.get(c,p)
 if'"'>c:h[r]=not v
 if"."==c:print(int(v))
 if"]"<c:t.discard(p)if v else t.add(p)
 if"["==c:
  while f(C[1:],p):1
 else:return c=="]"and v or C and f(C[1:],p)
f(C,0)

Probieren Sie es online aus!

Pip , 75 71 Bytes

lPB0aR:^"!><[].^_""!:_
--viPU0
++v
W_{
}
O_
i@v:!_LFBilPB0
l@FBi"^n;Vau

Probieren Sie es online aus!

Übersetzt den 2 ^Ω- Code in einen äquivalenten Pip-Code und wertet ihn aus.

Wir verwenden idas Band, vden Bandzeiger * und lden Hypercube. Die ersten beiden sind auf nützliche Werte vorinitialisiert; lbeginnt als [], auf die wir ein 0( lPU0) drücken , um Probleme beim Indizieren von leeren Listen zu vermeiden.

^{* Eigentlich ist es die bitweise Negation des Bandzeigers, da wir das Band rückwärts speichern, um die Konvertierung in Dezimalzahlen zu vereinfachen.}

Der Rest des Codes lautet:

aR:...;     Do a bunch of replacements in a, translating it into Pip code
       Va   Evaluate a
         u  Suppress output of the final expression that was evaluated

Die Übersetzungstabelle:

!  !:_
>  --viPU0
<  ++v
[  W_{
]  }
.  O_
^  i@v:!_LFBilPB0
_  l@FBi

l@FBiist das referent: Element des Hypercube lam Index ( ivon binär konvertieren ). Es erscheint oft, also nennen wir es _und ersetzen es _am Ende durch den echten Code.

• !:_ negiert logisch den vorhandenen Referenten.

• --viPU0Dekremente v(Bewegen des Bandzeigers nach rechts); Anschließend wird ein weiterer 0nach links gedrückt i, um sicherzustellen, dass der Bandzeiger in Grenzen bleibt.

• ++vInkremente v(keine Notwendigkeit zur Überprüfung der Grenzen pro OP).

• W_{führt eine Schleife aus, während der Referent wahr ist (dh ungleich Null, dh 1).

• } schließt die Schleife.

• O_ gibt den Referenten ohne Zeilenumbruch aus.

Zum Schluss für ^:

i@v:            Set the current tape cell to
    !_          The logical negation of the referent
                Now, make sure the list representing the hypercube is long enough:
      LFBi      Loop frombinary(i) times:
          lPB0  Push another 0 to the end of l
                This ensures that FBi will always be a valid index into l