9
\$\begingroup\$

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 , 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:

[.]![!.!]
\$\endgroup\$
  • 2
    \$\begingroup\$ A small note: the number of storage cells is not actually uncountable, as the number of 1s on the tape is always finite. In fact, there is a fairly simple bijection between the natural numbers and the tape states (interpret the tape contents as a backwards binary number), which shows that the Hypercube is basically an infinite 1D array, accessed by flipping bits in an integer pointer value, instead of in/decrementing as in brainfuck. \$\endgroup\$ – Lynn Apr 29 '18 at 10:19
  • \$\begingroup\$ Also, re: your invitation to write a cat program: there doesn't seem to be an instruction for taking input. \$\endgroup\$ – Lynn Apr 29 '18 at 10:23
  • 2
    \$\begingroup\$ I think there should be sample programs using more of the instruction set.Two simple ones: . - prints a single zero and then exists; !^!. - prints a single one then exits. More would be good though. At the moment one must understand submissions in order to verify them (and hence upvote them!) \$\endgroup\$ – Jonathan Allan Apr 29 '18 at 11:35
  • \$\begingroup\$ @Lynn The input would be given by having either a 1 or a 0 on cell [0,0,0,0,0,0,0...] (i.e. the presence of a ! at the start of the program). \$\endgroup\$ – Esolanging Fruit Apr 29 '18 at 22:36
  • \$\begingroup\$ Then you could do [.]![!.!] to print the value of that cell forever \$\endgroup\$ – Leo Apr 30 '18 at 0:10
2
\$\begingroup\$

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 2t & h. To flip it, we perform h ^= 2t.

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

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Are you sure this translation is valid? !>. prints 1 in boolfuck but translates to !>^. which prints 1 in TwoMega (> does not affect the tape; ^ does not affect the tape since the referent is 1) \$\endgroup\$ – Esolanging Fruit Apr 29 '18 at 4:36
  • \$\begingroup\$ @EsolangingFruit +>; do [1]00... 1[0]0... (output 0), !>^. do (0,0,...)=1, ptr=([0],0,...) (0,0,...)=1, ptr=(0,[0],...) (0,0,...)=1, ptr=(0,[1],...) (output 0), what's wrong? \$\endgroup\$ – l4m2 Apr 29 '18 at 4:43
  • \$\begingroup\$ @EsolangingFruit for !>., only > is a valid command in boolfuck... \$\endgroup\$ – ASCII-only Apr 29 '18 at 6:03
  • 1
    \$\begingroup\$ @l4m2 In TwoMega, ! inverts the referent, not the tape cell. \$\endgroup\$ – Esolanging Fruit Apr 29 '18 at 6:08
  • \$\begingroup\$ @EsolangingFruit so what's wrong here? \$\endgroup\$ – l4m2 Apr 29 '18 at 8:45
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ It mainly stores info in the position in the hypercube rather than the cube itself? \$\endgroup\$ – l4m2 May 3 '18 at 4:53
  • \$\begingroup\$ @l4m2 My reduction from BoolFuck does not store any data in the cube itself. Any 1s I make on the hypercube are only there to set tape cells to 0. \$\endgroup\$ – Nitrodon May 3 '18 at 4:55
0
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ t.discard(p) -> t-={p} \$\endgroup\$ – shooqie Apr 30 '18 at 12:17
  • \$\begingroup\$ @shooqie That doesn't work unless t is global. \$\endgroup\$ – fergusq May 1 '18 at 8:38
  • \$\begingroup\$ @fergusq Though I'm pretty sure it works if you declare f as f(C,p,t=set()) \$\endgroup\$ – shooqie May 1 '18 at 13:45
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.