Interpret TwoMega

Question

In this challenge, you will write an interpreter for 2^Ω (transcribed as TwoMega), a language based loosely on brainfuck with an infinite-dimensional storage space.

The Language

2^Ω contains three pieces of state:

• The Tape, which is an infinite list of bits, all initialized to 0. It has a leftmost element, but no rightmost element.

• The Memory Pointer, which is a nonnegative integer that is an index of an element in the tape. A higher memory pointer refers to a tape cell further to the right; a memory pointer of 0 refers to the leftmost element. The memory pointer is initialized to 0.

• The Hypercube, which is a conceptually ∞-dimensional "box" of cells, each of which contains a bit initialized to 0. The width of the Hypercube is bound in every dimension to only 2 cells, but the infinity of dimensions means the number of cells is uncountable.

An index into the hypercube is an infinite list of bits that refers to a cell in the hypercube (in the same way that a finite list of bits could be used to refer to a hypercube of finite dimension). Because the tape is an infinite list of bits, the entire tape always refers to an element of the Hypercube; this element is called the referent.

2^Ω gives meaning to 7 different characters:

• < decrements the memory pointer by 1. Decrementing it below 0 is undefined behavior, so you do not need to handle it.
• > increments the memory pointer by 1.
• ! flips the bit at the referent.
• . outputs the bit at the referent.
• ^ replaces the bit at the cell pointed to by the memory pointer on the tape with the inverse of the bit at the referent.
• [x] runs the code x as long as the bit at the referent is 1.

The Challenge

Your task is to write a program that takes a string as input and executes that input as a 2^Ω program.

This is code-golf, so the shortest valid answer (measured in bytes) wins.

Notes

• You can assume that the program will consist solely of the characters <>!.^[] and that [] will be properly nested.
• Your interpreter should only be limited by available memory on the system. It should be able to run the sample programs in a reasonable amount of time.

Sample Programs

Print 1:

!.

Print 010:

.!.!.

Print 0 forever:

![!.!]

Print 0 forever, or 1 forever if ! is prepended:

[.]![!.!]

Answer 1

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

Try it online!

t is the tape. t = 6 means the tape is [0 1 1 0 0 0 …]

m is 2 to the power of the memory pointer. So m = 8 means we're pointing at tape bit 3.

h is the hypercube. h = 80 (bits 4 and 6 set) means the bits at [0 0 1 0 …] and [0 1 1 0 …] are set.

To read the bit at the referent, we check 2^t & h. To flip it, we perform h ^= 2^t.

We translate the instructions to Python code and execute the result. I stores the indentation level of the while loops.

Answer 2

JavaScript (Node.js), 148 bytes

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

Try it online!

It's turing complete

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

Need init as moving right few places and init the current and right one bit of the address as 1 (>>>>>>>>^>^<)

Try it online!

Place n in BoolFuck is written as (0, 0, ..., 0(n*0), [1], 1, 0, 0, ...).

For >, it does 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

Same to how < work

Answer 3

Brain-Flak Classic, 816 bytes

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

Try it online!

This code was written just so I'd have a place to write a proof of Turing-completeness.

Proof of Turing-completeness

We show a reduction from Boolfuck to TwoMega:

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

This translation stores the Boolfuck state in the even-numbered tape cells in TwoMega. All of the translated commands will preserve the following invariants:

• The memory pointer is at an even-numbered cell.
• All odd-numbered tape cells are zero.
• For any possible tape with all odd-numbered cells zero, the corresponding value on the hypercube is zero.

The snippet !^! will keep [0]0 constant and swap between 0[0] and [1]1 (where attention is limited to the line on the hypercube reachable without moving the memory pointer). As such, it is used to temporarily put the current tape value into the referent for the Boolfuck commands which care about it.

If TwoMega were given an input command , with the expected semantics, the Boolfuck command , would translate to >^<,!^>[!]!^<. Since , is not necessary to prove that Boolfuck is Turing-complete, the lack of an input command does not affect this proof.

Answer 4

Python 3, 297 284 274 bytes

-10 bytes thanks to ovs and 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)

Try it online!

Answer 5

Pip, 75 71 bytes

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

Try it online!

Translates the 2^Ω code into equivalent Pip code and evaluates it.

We use i to represent the tape, v for the tape pointer*, and l for the hypercube. The first two come preinitialized to useful values; l starts as [], to which we push a 0 (lPU0) to avoid indexing-empty-list problems.

^{* Actually, it's the bitwise negation of the tape pointer, because we're storing the tape backwards for easier conversion to decimal.}

The rest of the code is:

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

The translation table:

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

l@FBi is the referent: element of hypercube l at the index (convert i from binary). It appears often, so we call it _ and replace _ with the real code at the end.

• !:_ logically negates the referent in place.

• --viPU0 decrements v (moving the tape pointer to the right); it then pushes another 0 to the left side of i, to make sure that the tape pointer stays in bounds.

• ++v increments v (no need for bounds-checking, per OP).

• W_{ runs a loop while the referent is truthy (i.e. nonzero, i.e. 1).

• } closes the loop.

• O_ outputs the referent without newline.

Finally, for ^:

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