13
\$\begingroup\$

Write a brainfuck program of no more than 256 characters that takes as many steps as possible, but does not loop infinitely. The program may not take any input.

More specifically:

  • Assume an infinite number of cells to the right.
  • A < when at the leftmost cell does nothing.
  • A - when cell value is zero sets cell to 255.
  • The instructions +-<>. all count as one step when executed.
  • When a [ or ] is encountered, it counts as one step. However, if the condition is true and control flow jumps, the corresponding ] or [ does not again count as a step.
  • The solution that takes the most steps wins.
  • If there is some kind of pattern in your solution, giving a function for how many steps a similar program of length n would take is appreciated but not mandatory.
  • To count instructions, you can use this modified interpreter:

Example:

++[-]

The encountered instructions are ++[-]-], and the program ran for 7 steps.

\$\endgroup\$
  • 6
    \$\begingroup\$ I would be surprised if the winner terminates without overflowing the interpreter's count. Bear in mind that the 6-state TM busy beaver takes at least 10**36534 steps. \$\endgroup\$ – Peter Taylor Feb 1 '12 at 22:54
  • \$\begingroup\$ I agree. Seems highly likely you could write a <50 char BF program that could run for years. I'll get started. \$\endgroup\$ – captncraig Feb 1 '12 at 23:17
  • \$\begingroup\$ Signed. The Busy Beaver research page at drb.insel.de/~heiner/BB is very interesting, especially the fact that the record programs run extremely long and they still have exact results (see drb.insel.de/~heiner/BB/bb-xlist.txt) - simulations remember states, build "macros" to save simulation steps etc. \$\endgroup\$ – schnaader Feb 1 '12 at 23:28
  • 4
    \$\begingroup\$ @AntonGolov: unfortunately, in this universe, RAMs and HDs don't convert to infinite storage devices when you try to store bignums larger than 256 ^ size in bytes on them... \$\endgroup\$ – ceased to turn counterclockwis Feb 2 '12 at 14:06
  • 1
    \$\begingroup\$ @boothby Its perfectly possible to do exact computations involving transcendentals on current computers. The components of the values just have to be stored in a more abstract representation than the normal float or double primitives used for general everyday computing. (At that point the computer is mostly just manipulating strings of that represent the equation) \$\endgroup\$ – AJMansfield Jul 12 '13 at 13:17
15
\$\begingroup\$

Here's a 41-character program that eventually halts, leaving more than 10↑(10↑28) contiguous cells set equal to 1 (so the number of instructions executed is very much greater than that):

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

If I'm not mistaken, that's a correct translation of the following program in the BF-variant language that uses a single bit for each memory cell (i.e., cell content 0..1 instead of 0..255, so '+' acts to simply flip the bit-value):

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

The exact value (the number of adjacent 1-bits) produced by the latter program is

3 * (2 ↑ 118842243771396506390315925503 - 1) + 1.


The above program initializes & computes a function that grows like 2↑↑x (in Knuth up-arrow notation). Similar conversion of a variant-BF program that initializes & computes a function that grows like 2↑23x provides the following 256-character program:

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

which eventually halts, leaving more than 2↑236 adjacent cells set equal to 1 (so the number of steps is enormously more than that).

NB-1: 2↑236 is an "inconceivably large" number; e.g., even 2↑46 = 2↑↑↑↑6 already surpasses the first term (3↑↑↑↑3) in the sequence used to compute Graham's number.

NB-2: I think it's likely that 256 characters is enough for a BF program to initialize & compute a function with output much larger than Graham's number — if I find time, maybe I'll try to write one.

NB-3: In case anyone is interested in the origin of the above programs, here are some programming resources for "Brainf*ck F", with various programs written in Python. ("Brainf*ck F", or just "F", is what I called a Turing-complete variant of the Smallf*ck esolanguage.) I just now uploaded these files, which have been offline for several years, and for now the linked webpage is just a "file cabinet" -- see the file Busy_Beavers.txt for a detailed discussion relevant to the above programs.

\$\endgroup\$
  • \$\begingroup\$ This is a clear winner at the moment (unless I'm just underestimating the others). More suggestions are very welcome, but I'll mark it as accepted for now. If anyone disagrees, please do comment. \$\endgroup\$ – Anton Golov Feb 20 '12 at 20:13
  • \$\begingroup\$ When you get to this level, it becomes unrealistic to assume you have an interpreter with infinite memory. I am starting to think this would be a better challenge with finite wrapping memory, so we could actually run the answers. \$\endgroup\$ – captncraig Feb 22 '12 at 19:10
9
\$\begingroup\$

Here is a nice 39 character one:

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

It basically makes a 3 space wide 'sled' that it moves right and decrements by one. Completed in 31,919,535,558 instructions, with the innermost loop executing 256^3 times. I still have plenty of room to extend this pretty far at a rate of 14 characters to another order of magnitude to the run time.

Works on any interpreter with unbounded memory, or with wrapping memory.

I leave it a an exercise to the reader to determine when the improved by 2 loops version will finish:

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

It has now run overnight, and it is over 3,000,000,000 steps. Still has not gotten through a single iteration of the outer loop. Has barely made it through 15% of the second loop.

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

This programs works in infinte number of cells. Two values are initialized in the begining with ascii values 255. The first value at the first rotation of main loop is splited to 255 cell and they are initialized with 255 each, at the second rotation of main loop the each value in 255 cells again splits up to 255*255 cells, in the same way for 255 rotation of main loop the total cells initialized will be 255^255 . The second value determines how much times the main loop is to be repeated.

>->>-[<<[<]>[[[>]>>>[>]-[<]<<<[<]>-]>]>[>>[>]>+<<[<]<-]>>[>]>-]
\$\endgroup\$
2
\$\begingroup\$

This program is almost same as my previous program , difference is that the value determining the outer loop remains fixed in a particular cell so both number of cells initialized and total steps at the end of the program can be increased

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

cells initialized at the end of program 255^255

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

cells initialized at the end of program 255^255^3

I further modified it to run for even more number of steps.

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

it initializes 255^255 cells during first rotation of main 255^(255^255*255) cells during second rotation of main loop 255^{255^(255^255*255)*255} cells during third rotation of main loop in this way loop repeats 255 times

\$\endgroup\$
  • \$\begingroup\$ Looks great! Sorry for not yet accepting an answer -- I've got to take some time to look at these and figure out order of growth. When you say "255^255*255", do you mean "255^(255*255)"? (I'd expect "255^256" otherwise.) \$\endgroup\$ – Anton Golov Feb 15 '12 at 17:19

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.