19
\$\begingroup\$

All those busy beavers made quite a mess. They wrote all over the tape. At this rate, our neighbour will stop lending us unbounded tapes.

We need a new way to play the busy beaver game, one that doesn't ruin every tape we use.

The Rules

Brainfuck only. Memory tape is unbounded both ways. Input instruction will always read \$0\$, so it can be used to clear a value.

50 bytes source limit.

At the end of execution, memory must be all \$0\$s.

Score is distance between the memory pointer's starting location and final location - if it takes \$n\$ move instructions to go between them, your score is \$n\$. Higher is better. Provide an exact value if you can, otherwise provide an estimate.

Example

32 bytes, \$2^{255}-1\$

-[-[[>]+>+[<]>-[[>]<+<+[<]>-]]>]

Explanation

-                                Initialize the list to [255].
 [                             ] Repeat as long as the list is not empty.
 [-                            ] Decrement the left end. We need to shrink the numbers so it ends eventually.
 [ [                         ] ] Skip if 0 already.
 [ [[>]                      ] ] Move to the cell past the right end.
 [ [   +                     ] ] Make this cell 1.
 [ [    >                    ] ] Go right again.
 [ [     +                   ] ] Make this cell 1. We've now appended [1, 1].
 [ [      [<]>               ] ] Go back to the first nonzero cell on the left.
 [ [          -              ] ] And decrement it.
 [ [           [            ]] ] We will need to transfer the rest of the number from the left to the right, so keep looping.
 [ [           [[>]<        ]] ] Go to the last nonzero cell on the right.
 [ [           [    +<+     ]] ] Increment this and the one on the left. These are the cells we appended earlier. We transfer to them.
 [ [           [       [<]> ]] ] Go back to the first nonzero cell on the left, which we are transferring from.
 [ [           [           -]] ] Decrement here on the left to balance out the incrementing on the right.
 [                            >] We end the iteration on a now empty cell. Move right, the new left end is there.

We begin with the list \$[255]\$. At each iteration, we consume the value \$n\$ on the left of the list, and if \$n>1\$, we append \$[n-1, n-1]\$ to the right. The numbers appended \$(n-1)\$ are lower than the original \$(n)\$, so they will get smaller until they are \$1\$, at which point they are consumed without expanding. Thus, the process ends eventually, with all \$0\$s in memory. However, at each step, the number of copies of the number doubles. The score of this program initialized with the list \$[n]\$ is \$2^n-1\$.

This example is meant to show some of the techniques used in creating a submission. It's not competitive for its size.

\$\endgroup\$
  • 3
    \$\begingroup\$ @Okx no problem - that wasn't intended as a criticism. If there's another way to score this that allows arbitrary code length, now is the time to find it before answers come in. I'm going to retag this as currently the code golf tag is misleading \$\endgroup\$ – trichoplax Sep 9 '18 at 20:01
  • 3
    \$\begingroup\$ There has to be some limit, since more bytes lets you define a faster growing function. There's no reason in particular for 50, it looks high enough for some decent growth (definitely better than my example's exponential) and creative solutions but still too small for Beklemishev's worm or other extremely fast growth. // Thanks for fixing my tags by the way, I rushed a bit getting this out. \$\endgroup\$ – EPICI Sep 9 '18 at 20:02
  • 2
    \$\begingroup\$ Just for background: We try to avoid minimum scores for code golf, but this challenge is not code golf, and the number of bytes is not the score, so I see absolutely no problem with there being a 50 byte limit in this case. \$\endgroup\$ – trichoplax Sep 9 '18 at 20:06
  • 1
    \$\begingroup\$ Info: I think I can "trivially port" this answer from other challenge and get similar score. \$\endgroup\$ – user202729 Sep 10 '18 at 2:01
  • 1
    \$\begingroup\$ @EPICI My previous busy beaver was already traceless, which is why I was trying to adapt it. \$\endgroup\$ – Jo King Sep 10 '18 at 9:34
10
\$\begingroup\$

Score: \$ A(255, 2) - 1 = (2 \uparrow^{253} 5) - 4 \$

+<+<<++>-[-[<+>>[-<[->+<]+>>]+<-]>[>]+[<]+<]>[->]

\$ A \$ here is the Péter-Ackermann formulation of the Ackermann function, while the other score expression uses Knuth up-arrow notation. The 35-byte main loop [-[<+>>[-<[->+<]+>>]+<-]>[>]+[<]+<] can be used to compute \$ A(m,n) \$ by placing on the tape the values 1 - m, m, 1 <n times> and entering the loop with the pointer on the m cell. After the loop terminates, the nonzero tape contents are \$ A(m,n) \$ ones starting immediately to the right of the pointer.

I used the following Python program for modeling the behavior of the program:

def a(M, N):
    assert M > 0
    m = [-M + 1, M]
    n = N
    while m[-1]:
        while m[-1] > 1:
            m[-1] -= 1
            m[-2] += 1
            while n:
                m.insert(-1, 1)
                n -= 1
            n = 1
        n += 2
        m.pop()
    return n
\$\endgroup\$
  • 1
    \$\begingroup\$ You could increase your score by adding a trailing >. \$\endgroup\$ – Jonathan Frech Sep 14 '18 at 1:56
  • \$\begingroup\$ wow, very impressive \$\endgroup\$ – alan2here Nov 17 '18 at 11:04

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.