Brainfuck is an esoteric programming language that is Turing Complete, meaning you can't tell whether a given program will halt without running it. It's cell-based and has an infinite tape of cells, values containing an unsigned integer from 0 to 255, but if you give it arbitrary-size cells, just three is enough to make it Turing Complete.

But one cell isn't in either case.

The bit of brainfuck that we'll be using contains these four operations:

  • +: Increment the current cell
  • -: Decrement the current cell
  • [: Loop while the current cell is nonzero
  • ]: End a loop

You should use a single unsigned integer from 0 to 255 as the cell, wrapping round when you decrement zero or increment 255.

You may return any two distinct, consistent values to say whether it halts or not. The program will be a valid brainfuck program (balanced brackets) and only contain these four characters. You may not output by halting/not halting.


If you want to look at these in more depth, here's a good visualizer.

Falsy (doesn't halt)


Truthy (halts)


Standard rules apply.

  • 1
    \$\begingroup\$ Shouldn't +[---] halt? \$\endgroup\$
    – loopy walt
    Nov 22, 2021 at 9:07
  • 1
    \$\begingroup\$ I would suggest you add a test where the final instruction is just an unblocked (not in loop) +/- to avoid the assumption that any instruction after the initial set is in a block. \$\endgroup\$ Nov 22, 2021 at 9:25
  • 2
    \$\begingroup\$ @Tvde1: No, and it took me awhile to prove it. \$\endgroup\$
    – Joshua
    Nov 22, 2021 at 17:49
  • 1
    \$\begingroup\$ Suggested test case: [+[++]]. I can see that tripping up a potential approach. \$\endgroup\$
    – Nitrodon
    Nov 23, 2021 at 20:05
  • 1
    \$\begingroup\$ @tsh That's an interesting question to which I don't know the answer. You could askk about it on Computer Science \$\endgroup\$
    – emanresu A
    Nov 25, 2021 at 2:52

5 Answers 5


05AB1E, 36 bytes


Outputs 1 if it halts; 0 if it doesn't halt.

Try it online or verify all test cases.


0ì                 # Prepend a "0" in front of the (implicit) input-string
„+-„><‡            # Replace all "+" with ">" and all "-" with "<"
'[„₄ƒ:            '# Replace all "[" with "₄ƒ"
']"D₁Ö#N₄Qi0q}}": '# Replace all "]" with "D₁Ö#N₄Qi0q}}"
1«                 # Append a trailing "1" at the end
.V                 # Execute it as 05AB1E code
                   # (after which the result is output implicitly)

Verify all test cases without .V to see what 05AB1E programs the inputs are transformed into.

0ì                 # We start the cell at 0

„+-„><‡            # `>` increases the top of the stack by 1
                   # `<` decreases the top of the stack by 1

'[„₄ƒ:            '# `₄ƒ` loop `N` in the range [0,1000]

']"D₁Ö#N₄Qi0q}}": '# 
   D               # Duplicate the top
    ₁Ö             # Pop and check if it's divisible by 256
      #            # If this is truthy: stop the loop
       N           # Else: push the loop index `N`
        ₄Qi        # If it's equal to 1000:
           0       #  Push a 0
            q      #  And stop the entire program
                   #  (after which this 0 is output implicitly as result)
             }     # Close the if-statement
              }    # Close the loop

1«                 # Push a 1
                   # (which is output implicitly as result if we didn't halt)

JavaScript (Node.js), 116 bytes


Try it online!

JavaScript (Node.js), 135 bytes


Try it online!

  • 1
    \$\begingroup\$ Nice! You can replace both occurences of '[' with {} to save 2 bytes - During comparison, {} gets stringified to [object Object]. \$\endgroup\$
    – emanresu A
    Nov 22, 2021 at 10:19
  • \$\begingroup\$ 113 \$\endgroup\$
    – l4m2
    Jan 26, 2022 at 5:26
  • \$\begingroup\$ even catch{} to 112 \$\endgroup\$
    – l4m2
    Jan 26, 2022 at 5:28

Wolfram Language (Mathematica), 117 bytes


Try it online!

  • 4
    \$\begingroup\$ it's Mathematica, is there really no HaltingDecider built in? \$\endgroup\$
    – user253751
    Nov 22, 2021 at 18:09

Python 3, 245 bytes

for i,c in enumerate(p):
while a<len(p):
	if(a,n)in s:print();break
	if"["==q and n<1or"]"==q and n:a=m[a]

Try it online!

so idrk how the fancy string substitution solutions are working so here's my terrible attempt to just run the code instead

  • \$\begingroup\$ My kinda answer \$\endgroup\$
    – Mayube
    Nov 25, 2021 at 19:55

Charcoal, 90 88 bytes


Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. - if the program halts, nothing if not. Explanation:


Start at the beginning of the code.


Start with zero in the cell.


Start with no unmatched [s.


Repeat until either the end of the program is reached or the current state has been seen previously (i.e. an infinite loop has been detected).


Record the current state.


Switch on the next program character.


For [, if the cell is non-zero, then...


... save the current position, so it can be quickly restored when the matching ] is reached, otherwise...


... advance the current position to the matching ].


For ], jump back to the matching [, which will then test the cell value.


Otherwise, adjust the cell value modulo 256 as necessary.


Advance to the next character of the program. (In the case of [ jumping forward to its matching ], this skips past the ]. In the case of ] jumping back to its matching [, this increment has been adjusted for, so that the [ becomes the next code to execute.)


Output whether the end of the program was reached.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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