10
\$\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:

[.]![!.!]
Improve this question
\$\endgroup\$
7
  • 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\$ Commented Apr 29, 2018 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\$ Commented Apr 29, 2018 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\$ Commented Apr 29, 2018 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\$ Commented Apr 29, 2018 at 22:36
  • \$\begingroup\$ Then you could do [.]![!.!] to print the value of that cell forever \$\endgroup\$ Commented Apr 30, 2018 at 0:10

5 Answers 5

Reset to default
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.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Either your program or the second test case is wrong \$\endgroup\$ Commented May 1, 2018 at 12:46
  • \$\begingroup\$ @wastl The second test case was wrong. ;) \$\endgroup\$ Commented Mar 20, 2019 at 6:59
  • \$\begingroup\$ Some rearrangements, extra variable for 2**t (-6 bytes). \$\endgroup\$ Commented Mar 21, 2019 at 18:37
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

Improve this answer
\$\endgroup\$
11
  • \$\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\$ Commented Apr 29, 2018 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\$ Commented Apr 29, 2018 at 4:43
  • \$\begingroup\$ @EsolangingFruit for !>., only > is a valid command in boolfuck... \$\endgroup\$ Commented Apr 29, 2018 at 6:03
  • 1
    \$\begingroup\$ @l4m2 In TwoMega, ! inverts the referent, not the tape cell. \$\endgroup\$ Commented Apr 29, 2018 at 6:08
  • \$\begingroup\$ @EsolangingFruit so what's wrong here? \$\endgroup\$ Commented Apr 29, 2018 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.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ It mainly stores info in the position in the hypercube rather than the cube itself? \$\endgroup\$ Commented May 3, 2018 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\$ Commented May 3, 2018 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!

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ t.discard(p) -> t-={p} \$\endgroup\$ Commented Apr 30, 2018 at 12:17
  • \$\begingroup\$ @shooqie That doesn't work unless t is global. \$\endgroup\$ Commented May 1, 2018 at 8:38
  • \$\begingroup\$ @fergusq Though I'm pretty sure it works if you declare f as f(C,p,t=set()) \$\endgroup\$ Commented May 1, 2018 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
Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.