Will one-cell brainfuck halt?

Question

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 code-golf rules apply.

Answer 1

05AB1E, 36 bytes

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

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

Try it online or verify all test cases.

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)

Answer 2

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!

Answer 3

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!

Answer 4

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

Answer 5

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

≔﹪⁺Ｉ⁺§θη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.