21
\$\begingroup\$

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.

\$\endgroup\$
12
  • 1
    \$\begingroup\$ Shouldn't +[---] halt? \$\endgroup\$
    – loopy walt
    Nov 22 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 at 9:25
  • 2
    \$\begingroup\$ @Tvde1: No, and it took me awhile to prove it. \$\endgroup\$
    – Joshua
    Nov 22 at 17:49
  • 1
    \$\begingroup\$ Suggested test case: [+[++]]. I can see that tripping up a potential approach. \$\endgroup\$
    – Nitrodon
    Nov 23 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 at 2:52
5
\$\begingroup\$

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)
\$\endgroup\$
5
\$\begingroup\$

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!

\$\endgroup\$
1
  • 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 at 10:19
3
\$\begingroup\$

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!

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

Charcoal, 90 88 bytes

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

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.

W∧‹ηLθ¬№υ⟦ηζ⟧«

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

W›№…θ⊕η[⁺№…θ⊕η]Lε≦⊕η

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

]≔⊖⊟εη

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

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

»⁼ηLθ

Output whether the end of the program was reached.

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

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

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

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.