# Solve the Halting Problem for Befinge

Let's define a simple 2D language, which we'll give the incredibly original name befinge. Befinge has 5 instructions:

• <>^v, as in most 2D esolangs, redirect the instruction pointer in their respective directions.
• . is a no-op.

The instruction pointer starts out at the top-left corner going right. If the instruction pointer gets to an edge, the program halts. Every Befinge program will obviously either halt or go into an infinite loop which does nothing. Here are two examples:

Halting:

>.v
..<


Non-Halting:

>....v
..v..<
..>v..
^..<..


The halting problem is not solvable for a Turing-complete language, but it is for this one. Your task is to write a program (or function) that takes as input a string representing the befinge program and returns a truthy or falsey value depending on whether it halts or not.

• You can assume that the input will consist only of these characters and will be padded with spaces to form a rectangle.
• You can use any set of five characters for the instructions (e.g. adws ).

## Test Cases

### Halting:

.


v>
>^


....v....
....>...v
.^..<....
.......v<
.......v.
....^..<.


v<>v>v^
>v^>^>v
<>>^v<v
v^<>v^<


### Non-Halting:

>..v
^..<


>v<
v<.
>v.
v<.
>.^


>.>.>.v
.><.<.<


This is , so the shortest program (in bytes) wins.

• What about 아희(Aheui)? Nov 9 '16 at 1:10
• Some test cases where not every arrow is hit would be good.
– xnor
Nov 9 '16 at 1:13
• Turing proved that the Halting problem is not solvable for any Turing-Complete language, so I had to make up a fake one that wasn't Turing complete. A language that will always eventually halt is not Turing complete. Nov 9 '16 at 1:14
• We also don't have any examples where the path makes a non-90-degree turn like >..>. or ><.
– xnor
Nov 9 '16 at 1:18
• @PyRulez Because I wanted processing directional motion to be part of the challenge. Mar 4 '18 at 2:01

# ES6 (JavaScript), 111,101 bytes

EDIT: changed output values to true and false, instead of Y and N, to shave off 10 bytes more

Golfed

F=(I,M=[...I],c=0,i)=>(i={j:v=I.search\n+1,k:-v,h:-1,l:1,q:i,0:0}[M[c]])?F(I,M,c+i+(M[c]=0),i):i!=0


Test

F=(I,M=[...I],c=0,i)=>(i={j:v=I.search\n+1,k:-v,h:-1,l:1,q:i,0:0}[M[c]])?F(I,M,c+i+(M[c]=0),i):i!=0

//Alphabet Map
tr={
'<':'h',
'>':'l',
'^':'k',
'v':'j',
'.':'q',
'\n':'\n'
};

//Test
T=(I,A)=>{
console.log({"Y":"#Halting","N":"#Non-Halting"}[A]);
console.log("I=\n",I,"\nF(I)=",O=F([...I].map(s=>tr[s]).join('')));
console.log('NY'[O*1] == A ? "OK !" : "NOT OK !");
}

//Halting
T(
>.v
..<
,'Y');

//Non-Halting
T(
>....v
..v..<
..>v..
^..<..
,'N');

//Halting
T(
.
,'Y')

//Halting
T(
v>
>^
,'Y');

//Halting
T(
....v....
....>...v
.^..<....
.......v<
.......v.
....^..<.
,'Y');

//Halting
T(
v<>v>v^
>v^>^>v
<>>^v<v
v^<>v^<
,'Y');

//Non-Halting
T(
>..v
^..<
,'N');

//Non-Halting
T(
>v<
v<.
>v.
v<.
>.^
,'N');

//Non-Halting
T(
>.>.>.v
.><.<.<
,'N');


Sample Output

#Halting
I=
>.v
..<
F(I)= true
OK !

#Non-Halting
I=
>....v
..v..<
..>v..
^..<..
F(I)= false
OK !

#Halting
I=
.
F(I)= true
OK !

#Halting
I=
v>
>^
F(I)= true
OK !

#Halting
I=
....v....
....>...v
.^..<....
.......v<
.......v.
....^..<.
F(I)= true
OK !

#Halting
I=
v<>v>v^
>v^>^>v
<>>^v<v
v^<>v^<
F(I)= true
OK !

#Non-Halting
I=
>..v
^..<
F(I)= false
OK !

#Non-Halting
I=
>v<
v<.
>v.
v<.
>.^
F(I)= false
OK !

#Non-Halting
I=
>.>.>.v
.><.<.<
F(I)= false
OK !

• You can't just use Y and N as output as in JavaScript they are both truthy. Jul 21 '18 at 15:35

# Python 2, 116 105 bytes

x=1
X=Y=y=0
H=[]
G=input()
while(X,Y,x,y)not in H:H+=[(X,Y,x,y)];C=ord(G[Y][X]);x=C%3-1;y=C%5-1;X+=x;Y+=y


Try it online!

The challenge is old, but I figured since this is the shortest Python, I will post it. Input is a list of strings, but the characters used are unusual.

> G
< B
v C
^ F
. L


For example, the third halting example turns into ['LLLLCLLLL', 'LLLLGLLLC', 'LFLLBLLLL', 'LLLLLLLCB', 'LLLLLLLCL', 'LLLLFLLBL']. Output is via exit code, 0 (success) for non-halting, and 1 (error) for halting. Any tips or tricks appreciated.

# Befunge-98 (PyFunge), 217209 200 bytes

#v10dpf1dp12dp3dpk
>#v~:a-#v_\$10dp1dg1+1dp >
v  >10dp;>0dg1dgp0dg1+0dp^;f1dp
>0dg1dgg:'^-#v_n1-v
^<v01_v#!->':<
<   >:'<-#v_01-0>   v
v^pd1+gd3gd1[:'v-#v_01>3dp2dpndg1dgp
>0dg2dg+0dp ^ @.!;>:'.-#;_


Try it online!

A befinge halting problem needs a befunge solution. Returns 0 for truthy and 1 for falsey. Puts the input on the grid starting from 1,15 and then moves on top, replacing the arrows with zeros. As soon as we hit a zero, we know it loops. Anything besides ><^v. and zero is considerd to halt the program, which includes the border of spaces we get around the program by placing it on the grid slightly offset.

One easy way to shave off a few bites would be to use numbers instead of ><^v. but I don't feel like that's worth it.

• A befinge halting problem needs a befunge solution. Precisely. +1 Sep 4 '19 at 18:32

# Turtlèd, 146 bytes

!u[*.[ r+.]l[ l]dr_+]#*#[ u]d[ (.r)(>.r{.r}@>)(v.d{.d}@v)(<.l{.l}@<)(^.u{.u}@^)(*@0' )],@1(0@0)(v' d)(<' r)(>' l)(^' d)[ u]d[ l]r[ [ r]l[ ' l]dr],


This program takes I/O differently: please terminate each line with a space, including the last one. Turtlèd doesn't like newlines, as it uses a grid for it's second dimension of characters.

### Try it online!

0 for loops forever, 1 for halts.

## General explanation:

It writes the input on the grid, then it actually follows the path the arrows make around the grid, replacing each arrow with a * as it goes, also saving the direction in the char var. If it encounters an *, an arrow it hit before, the program would not halt, so it sets the char var to 0, exit the loop. Otherwise, it will hit the end of the grid and exit the loop. It will write the char var. If it hit the end of grid, it uses the direction stored in the char var to get back to the grid, and sets the char var to 1, for halts. If the char var was actually 0, not a direction, it does not need to get back, as it is still there, and it sets it back to 0. It clears the grid off, then writes the char var, 1 for halts, else 0.

# JavaScript (Node.js), 80 bytes

f=(a,v=1,x=0,[t,...u]=a,n=1+a.search
,c=a[x])=>t?f(a,v=+c?c-2||v:c+n,x-v,u):!c


Try it online!

# JavaScript (Node.js), 86 bytes

f=(a,v=1,x=0,[t,...u]=a,n=1+a.search
,c=a[x])=>t?c>' '<=f(a,v=+c?c-2||v:c+n,x-v,u):0


Try it online!

## JavaScript (ES6), 158 127 bytes

f=(a,x=0,y=0,d=1,e=0,c=a[y]&&a[y][x])=>c<'~'?(c>'.'&&(a[y][x]='~',d=(c=='>')-(c=='<'),e=(c=='v')-(c=='^')),f(a,x+d,y+e,d,e)):!c


Takes input as a two-dimensional character array and returns true for halting and false for an infinite loop. Works by setting visited direction characters to ~s as it recursively traverses them. Edit: Saved 31 bytes by updating my direction vector before recursing.

Abusing the instruction characters (1=^ 4=< 5=. 6=> 9=v) takes me down to 101 bytes:

f=(a,x=0,y=0,d=1,e=0,c=a[y]&&a[y][x])=>+c?(c-5&&(a[y][x]='0',d=~-c%4,e=~-(c>>2)),f(a,x+d,y+e,d,e)):!c

• > Takes input as a two-dimensional character array Is a differently formatted input permitted ? (going from a flat string to an array do take bytes too). Nov 11 '16 at 14:52
• @zeppelin My belief is that this is allowed. See meta.codegolf.stackexchange.com/q/2214/17602 for instance.
– Neil
Nov 11 '16 at 21:55
• ReferenceError: f is not defined
– l4m2
Jul 23 '18 at 13:29
• @l4m2 Bah, I've done it again, I've included the f= in the byte count but not the code...
– Neil
Jul 23 '18 at 14:31

# SmileBASIC, 158 145 bytes

If the same arrow is encountered more than once, the program will never halt. When the instruction pointer passes an arrow, it's replaced with a different symbol, which will cause the function to return 0 if it's reached again. If the IP goes out of bounds, it returns 1.

DEF H P@L
C=VAL(P[Y][X])IF C>8THEN?0RETURN
IF C THEN D=C-1P[Y][X]="9
X=X+!D-(D==1)Y=Y+(D==2)-(D>2)IF X+1&&Y+1&&Y-LEN(P)&&X-LEN(P[0])GOTO@L
?1
END


Takes input as an array of strings. <any non-digit chracter>,1,2,3,4 = .,>,<,v,^

## Python 2, 182 bytes

m,v,d,x,y=input(),[],'>',0,0
try:
while 1:
if[x,y]in v:print 0;break
c=m[y][x]
if c!='.':d=c;v+=[[x,y]]
if d in'><':x+=[-1,1][d=='>']
else:y+=[-1,1][d=='v']
except:print 1


Takes a string array as input. I have to golf this more but for now it's time to stress over the election.

Ungolfed:

input = input()

visited = [  ]

dir = ">"
x=0
y=0

try:
while True:
if[x,y]in visited:print False;break
char=input[y][x]
if char!=".":
dir=char
visited+=[[x,y]]

if dir==">":
x+=1
if dir=="<":
x-=1
if dir=="v":
y+=1
if dir=="^":
x-=1
except:
print True

• hey, what if you took the main part out of the try, and put only the c=m[y][x] in a try and except? this would also allow you to replace break with 1/0, as well as reducing indents. Nov 9 '16 at 3:22
• [-1,1][d=='v'] -> 2*(d>'>')-1 and [-1,1][d=='>'] -> 2*(d>'<')-1 save a total of 6 bytes.
Nov 9 '16 at 13:59
• Wrong answer for ["<>"] Nov 9 '16 at 17:03

## Clojure, 143 bytes

#((fn[p v i s](if-let[v({\> 1\< -1\^(- s)\. v\v s}(get % p))](if(neg? i)1(recur(+ p v)v(dec i)s))))0 1 1e9(+(count(take-while(set"<>v^.")%))1))


A function with 4 state arguments: position p, velocity v, step index i and size of one line s. Returns 1 if we didn't go out of bounds in 10^9 steps and nil otherwise. Actually how many steps do we need to check to be sure, (count %)? I think it is more than that as same NOP can be traversed horizontally and vertically.

Can be called like this (takes normal strings as arguments, get returns nil when out of bounds):

(def f #( ... ))
(f ">....v\n..v..<\n..>v..\n^..<..")
(f "v>\n>^")
(f "....v....\n....>...v\n.^..<....\n.......v<\n.......v.\n....^..<.")


State transitions (+1, -1, +s, -s) are encoded in the dictionary {\> 1\< -1\^(- s)\. v\v s}.

• 4 times the number of grid characters should be enough: if the pointer comes back to the same character with the same incoming direction, then it's in an infinite loop. Jan 3 '17 at 8:55

# Python 2/3, 201 192 bytes

def f(x):
X=Y=b=0;a=1;D={}
while len(x)>Y>-1<X<len(x[Y]):
try:
a,b={'>':(1,0),'^':(0,-1),'<':(-1,0),'v':(0,1)}[x[Y][X]]
if(X,Y)in D:return 0
except:0
D[X,Y]=0;X+=a;Y+=b
return 1


Try it online!

Gives correct answer for ["<>"]

• I believe you can save several bytes by changing from a function to a full program. You can replace def f(x): with x=input() with 0 byte difference, then remove the extra indentation (-8 bytes), then replace return x with exit(x)(allowed per meta consensus), for another 2 bytes. Anyway, nice solution! Jul 21 '18 at 16:59

## Java, 477

I know that this is not winning, n=and can probably be golfed more, but it implments a similar method as to what the other answers use, but this one uses hashmap to perform lookups. The input is using the symbols ><^v and anything other than that for the no op. Input comes through args.

GOLFED

import java.util.*;interface B{static void main(String[]a){HashMap<String,Byte>h=new HashMap<>();int x,y=0;for(String s:a){x=0;for(char c:s.toCharArray()){if("><^v".indexOf(c)>-1)h.put(x+","+y,(byte)c);x++;}y++;}x=0;y=0;int d=0;int D=0;while(x>-1&&x<a[0].length()&&y<a.length&&y>-1){Byte v=h.get(x+","+y);if(v!=null){if(v==0){System.out.print(0);return;}d=(v<85)?"<>".indexOf(v)*2-1:0;D=(v>84)?"^v".indexOf(v)*2-1:0;}h.replace(x+","+y,(byte)0);x+=d;y+=D;}System.out.print(1);}}


UNGOLFED

import java.util.*;

interface B{
static void main(String a[]) {
HashMap<String, Byte> h = new HashMap<>();
int x, y = 0;
for(String s : a) {
x = 0;
for(char c : s.toCharArray()) {
if ("><^v".indexOf(c) > -1) h.put(x + "," + y, (byte) c);
x++;
}
y++;
}
x = 0;
y = 0;
int d = 0;
int D = 0;
while(x > -1 && x < a[0].length() && y < a.length && y > -1) {
Byte v = h.get(x + "," + y);
if(v != null) {
if(v == 0) {System.out.print(0); return;}
d = (v < 85) ? "<>".indexOf(v)*2-1 : 0;
D = (v > 84) ? "^v".indexOf(v)*2-1 : 0;
}
h.replace(x + "," + y, (byte) 0);
x += d;
y += D;
}
System.out.print(1);
}
}


Explanation coming soon!

• One small thing: you can change String a[] to String[]a and omit the space. Sep 10 '19 at 14:51
• You can also use var in a lot of places if you use Java 10. Sep 10 '19 at 14:53
• 410 bytes Oct 15 '19 at 19:46