# Will one-cell brainfuck halt?

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.

## Testcases

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

### Falsy (doesn't halt)

+[]
+[++]
+[++[+]--]
+[----]
+[-]-[+[-]-]
+[[-]-[+[-]-+[++]-[+]]-[++][-]]
++[-]+[--]-


### Truthy (halts)

[+]
+
+[+]
++[+++]
+++--[++-][+][+]
+[+]-[+++]-


Standard rules apply.

• Shouldn't +[---] halt? Nov 22 '21 at 9:07
• 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. Nov 22 '21 at 9:25
• @Tvde1: No, and it took me awhile to prove it. Nov 22 '21 at 17:49
• Suggested test case: [+[++]]. I can see that tripping up a potential approach. Nov 23 '21 at 20:05
• @tsh That's an interesting question to which I don't know the answer. You could askk about it on Computer Science Nov 25 '21 at 2:52

# 05AB1E, 36 bytes

0ì„+-„><‡'[„₄ƒ:']"D₁Ö#N₄Qi0q}}":1«.V


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

Explanation:

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

s=>eval(try{${s.replace(/./g,(c,i)=>(c=='['?'for(;v;){':c>{}?'}':v=v${c}1&255)+;s[t++>>9].x;)}}catch{1},v=t=0)


Try it online!

# JavaScript (Node.js), 135 bytes

s=>(e=(p,v,b=0)=>(s[p]=='['?b|!v?++b:b:s[p]>'['?b|v?--b:b:b)?e(b>0?p+1:p-1,v,b):s[p]?e[m=[p,v]]||e(p+(e[m]=1),v+(s[p]+1|0)&255):0)(0,0)


Try it online!

• Nice! You can replace both occurences of '[' with {} to save 2 bytes - During comparison, {} gets stringified to [object Object]. Nov 22 '21 at 10:19
• 113
– l4m2
2 days ago
• even catch{} to 112
– l4m2
2 days ago

# Wolfram Language (Mathematica), 117 bytes

ToExpression[a=b=0;StringReplace[#,{"["->"Do[If[c∣a,Break[]];","]"->"i<c||(b=1),{i,c=256}];",c_:>"a"<>c<>"=1;"}]]b&


Try it online!

• it's Mathematica, is there really no HaltingDecider built in? Nov 22 '21 at 18:09

# Charcoal, 90 88 bytes

≔⁰η≔⁰ζ≔⟦⟧εＷ∧‹ηＬθ¬№υ⟦ηζ⟧«⊞υ⟦ηζ⟧≡§θη[¿ζ⊞εηＷ›№…θ⊕η[⁺№…θ⊕η]Ｌε≦⊕η]≔⊖⊟εη≔﹪⁺Ｉ⁺§θη1ζ²⁵⁶ζ≦⊕η»⁼ηＬθ


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 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.

≔﹪⁺Ｉ⁺§θη1ζ²⁵⁶ζ


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.

# Python 3, 245 bytes

p=input()
m={}
s=[]
for i,c in enumerate(p):
if"["==c:s+=[i]
if"]"==c:m[s[-1]]=i;m[i]=s.pop()
a=n=0
while a<len(p):
if(a,n)in s:print();break
s+=[(a,n)];q=p[a]
if"["==q and n<1or"]"==q and n:a=m[a]
if"+"==q:n+=1
if"-"==q:n-=1
a+=1;n%=256


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

• My kinda answer Nov 25 '21 at 19:55