В этих проблемах, вы будете писать интерпретатор для 2 ^Ом (транскрибируется в TwoMega ), язык , основанный на свободно Brainfuck с бесконечномерным пространством для хранения.

Язык

2 ^Ω содержит три части состояния:

• Лента , которая представляет собой бесконечный список битов, все инициализируются в 0. Это имеет крайний левый элемент, но не крайний правый элемент.

• Указатель памяти , которая представляет собой неотрицательное целое число , которое является индексом элемента в ленте. Более высокий указатель памяти относится к ячейке ленты дальше справа; указатель памяти 0 ссылается на самый левый элемент. Указатель памяти инициализируется в 0.

• Гиперкуба , который является концептуально ∞ - мерным «окном» ячеек, каждый из которых содержит бит , инициализированное в 0. ширина Гиперкуба связана в каждом измерении только 2 клеток, но бесконечность размеров означает число клетки неисчислимы .

Индекс в гиперкуб бесконечного список бит, относится к клетке , в гиперкуба (таким же образом , что конечный список бит может быть использован для обозначения гиперкуба конечной размерности). Поскольку лента представляет собой бесконечный список битов, вся лента всегда ссылается на элемент гиперкуба; этот элемент называется референтом .

2 ^Ω дает значение 7 различным символам:

• < уменьшает указатель памяти на 1. Уменьшение его ниже 0 - неопределенное поведение, поэтому вам не нужно обрабатывать его.
• > увеличивает указатель памяти на 1
• ! переворачивает бит у референта.
• . выводит бит на референте.
• ^заменяет бит в ячейке, на которую указывает указатель памяти на ленте, на инверсию бита в референте.
• [x]выполняет код xдо тех пор, пока бит у референта равен 1.

Соревнование

Ваша задача - написать программу, которая принимает строку в качестве входных данных и выполняет эти входные данные как 2- ^омную программу.

Это Код-гольфТаким образом, самый короткий действительный ответ (измеряется в байтах) выигрывает.

Ноты

• Вы можете предположить, что программа будет состоять только из символов <>!.^[]и []будет правильно вложена.
• Ваш переводчик должен быть ограничен только доступной памятью в системе. Он должен быть в состоянии запустить примеры программ в разумные сроки.

Примеры программ

Печать 1:

!.

Печать 010:

.!.!.

Печать 0 навсегда:

![!.!]

Выведите 0 навсегда или 1 навсегда, если !добавлено:

[.]![!.!]

Python 2 , 167 байт

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

Попробуйте онлайн!

т является лента. t = 6 означает, что лента [0 1 1 0 0 0…]

m равно 2 степени указателя памяти. Таким образом, m = 8 означает, что мы указываем на бит 3 ленты.

h - гиперкуб. h = 80 (биты 4 и 6 установлены) означает, что биты в [0 0 1 0…] и [0 1 1 0…] установлены.

Чтобы прочитать бит у референта, мы проверяем 2 ^t & h . Чтобы перевернуть это, мы выполняем h ^ = 2 ^т .

Мы переводим инструкции в код Python и выполняем результат. Я сохраняю уровень отступа циклов while.

JavaScript (Node.js) , 148 байт

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))

Попробуйте онлайн!

Тьюринг завершен

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

Нужно, чтобы init как перемещался вправо на несколько мест, и инициализировал текущий и правый один бит адреса как 1 ( >>>>>>>>^>^<)

Попробуйте онлайн!

Место n в BoolFuck записывается как (0, 0, ..., 0(n*0), [1], 1, 0, 0, ...).

Ибо >это делает 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

То же самое, как <работать

Brain-Flak Classic , 816 байт

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

Попробуйте онлайн!

Этот код был написан просто для того, чтобы у меня было место, чтобы написать доказательство полноты по Тьюрингу.

Доказательство Тьюринга-полноты

Мы показываем сокращение от Boolfuck до TwoMega:

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

Этот перевод сохраняет состояние Boolfuck в чётных ячейках ленты в TwoMega. Все переведенные команды сохранят следующие инварианты:

• Указатель памяти находится в четной ячейке.
• Все нечетные ячейки ленты равны нулю.
• Для любой возможной ленты с нулевыми нечетными ячейками соответствующее значение в гиперкубе равно нулю.

Фрагмент !^!будет оставаться [0]0постоянным и переключаться между 0[0]и [1]1(где внимание ограничено линией на гиперкубе, доступной без перемещения указателя памяти). Как таковой, он используется для временного помещения текущего значения ленты в референт для команд Boolfuck, которые заботятся об этом.

Если бы TwoMega была дана команда ввода ,с ожидаемой семантикой, команда Boolfuck ,переведена в >^<,!^>[!]!^<. Поскольку ,нет необходимости доказывать, что Boolfuck является тьюрингово-полным, отсутствие входной команды не влияет на это доказательство.

Python 3 , 297 284 274 байта

-10 байт благодаря яйцам и Джонатану Аллану

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)

Попробуйте онлайн!

Пип , 75 71 байт

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

Попробуйте онлайн!

Переводит 2 ^Ω код в эквивалентный код Pip и оценивает его.

Мы используем iдля представления ленты, vдля указателя ленты * и lдля гиперкуба. Первые два преинициализированы на полезные значения; lначинается как [], к которому мы нажимаем 0( lPU0), чтобы избежать проблем с indexing-empty-list.

^{* На самом деле, это побитовое отрицание указателя ленты, потому что мы храним ленту в обратном направлении для более простого преобразования в десятичную.}

Остальная часть кода:

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

Таблица перевода:

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

l@FBiявляется референтом: элементом гиперкуба lв индексе (конвертируется iиз двоичного кода). Он появляется часто, поэтому мы вызываем его _и заменяем _реальным кодом в конце.

• !:_ логически отрицает референт на месте.

• --viPU0уменьшение v(перемещение указателя ленты вправо); затем он толкает другой 0в левую сторону i, чтобы убедиться, что указатель ленты остается в границах.

• ++vприращения v(нет необходимости в проверке границ, для каждой операции).

• W_{запускает цикл, в то время как референт верен (то есть ненулевой, то есть 1).

• } замыкает цикл

• O_ выводит референт без перевода строки.

Наконец, для ^:

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